Undecidability of the theory of multiplication with order

50 Views Asked by At

In her paper, "The Theory of Integer Multiplication with Order Restricted to Primes is Decidable" Françoise Maurin claims the following

On the other hand, J. Robinson shows in [12] that the theory of the integer multiplication with usual order < is not decidable.

The citation is to Robinson's paper "Definability and decision problems in arithmetic".

From which facts of [12] does the undecidability result follow?

1

There are 1 best solutions below

0
On BEST ANSWER

Theorem 1.1 of Robinson's paper says that $+$ is definable in the structure $(\mathbb{N},\times,<)$. It follows by Gödel's Theorem that the complete theory of this structure is undecidable.

See Section 4 (pp. 110-113) for more on undecidability.