# Tarski's decidability proof on real closed field and Peano arithmetic

It seems very confusing that real closed field (which also can be used as the theory of real number) is decidable, while Peano arithmetic, which seems to be a subset of real closed field is undecidable.

What am I getting wrong?

-

As William pointed out in his answer, Peano Arithmetic is a certain first-order theory which describes properties of $\mathbb{N}$, the natural numbers (that is, $\mathbb{N}\models\text{PA}$). However, it is incomplete (as shown by Gödel), and hence it is not equal to the complete theory of the natural numbers, denoted $\text{Th}(\mathbb{N})$, which consists of all first-order statements true of $\mathbb{N}$. The situation is different with the theory of real closed fields - this is a complete theory, and $\mathbb{R}\models \text{RCF}$, so $\text{RCF} = \text{Th}(\mathbb{R})$.

Your main confusion, however, seems to be about how $\text{Th}(\mathbb{N})$ can be so much more complicated than $\text{Th}(\mathbb{R})$, despite the fact that $\mathbb{N}\subset \mathbb{R}$. If $\text{Th}(\mathbb{R})$ is decidable, why can't we use the decision procedure to decide all questions about $\mathbb{N}$?

This phenomenon is possible because there is no single first-order formula (in our language $\{0,1,+,\cdot\}$) which picks out the natural numbers as a subset of the reals. To decide whether a sentence is true about $\mathbb{N}$ by asking a question about $\mathbb{R}$, we would have to somehow ensure that all quantifiers talk only about the integers.

To illustrate the difficulty, consider the sentence $\phi:\forall x\,\exists y\, (y+y = x)$. $\phi$ is certainly false in $\mathbb{N}$. But to use the decidability of $\text{Th}(\mathbb{R})$ to see this, we would need to be able to express that for all natural numbers $x$ there is a natural number $y$ such that $y+y = x$, which we cannot do. Allowing the variables to range over $\mathbb{R}$, $\phi$ is true.

Intuitively, it is questions about divisibility like this one which make $\text{Th}(\mathbb{N})$ so much more complicated than $\text{Th}(\mathbb{R})$. The formula $\psi(x,y):\exists z (x = y\cdot z)$, expressing that $y|x$, gives access to all the complexity of the prime numbers. By contrast, the reals are extremely homogeneous: $\psi(x,y)$ is true of a pair of reals $(a,b)$ whenever $b\neq 0$.

-
I have constructed the set of natural numbers from the ordered field axioms, and derived the equivalent of the Peano Axioms. See: dcproof.com/DerivingPA.htm Do I not have a first-order formula here which picks out the natural numbers? –  Dan Christensen Jun 4 '12 at 8:25
I am told that it is only the first-order version of complete ordered field theory (i.e. with no quantification over sets) that is complete and decidable. Oh, well. –  Dan Christensen Jun 4 '12 at 13:27
Exactly - your definition of $\mathbb{N}$ inside $\mathbb{R}$ as the smallest subset containing $1$ and closed under $+1$ is explicitly second-order. –  Alex Kruckman Jun 4 '12 at 17:33
You can't have anything like the least-upper-bound axiom in a first-order language because such an axiom quantifies over sets of numbers. As such, you cannot have any first-order theory of complete ordered fields (the real numbers). –  Dan Christensen Jun 5 '12 at 5:56

The primary reason that the first-order theory of the reals proves to be much simpler than Diophantine (integer) analogs is that the associated geometry is much simpler. Namely, the sets that are definable by real-polynomial (in)equations - so-called semi-algebraic sets - can be decomposed into a finite number of cells (e.g. cylinders) where, on each cell, every defining polynomial has constant sign. Therefore testing the truth of a first-order statement reduces to a finite number of tests on constant-sign cells, which is trivially decided by simply evaluating the polynomials at any point in the cell. This yields an algorithm for deciding the truth of first order statements about the reals - the so-called cylindrical algebraic decomposition (CAD) algorithm (an effective realization of Tarski's famous method of quantifier elimination for the reals).

For example, in the one-dimensional case the sets definable in the first-order language of $\rm\:\mathbb R\:$ are simply finite unions of intervals. So, e.g. to test if $\rm\ f(x) > 0\ \Rightarrow g(x) > 0\$ we can employ Sturm's Theorem to partition $\:\mathbb R\:$ by the finite number of roots of $\rm\:f,\:g\:,\:$ and then choose a point $\rm\:r\:$ in each interval and test if $\rm\ f(r)>0\ \Rightarrow\ g(r)>0\:.\:$ The CAD algorithm works analogously in higher dimensions, by projecting higher-dimensional cells down to lower dimensions. The key property is a result of Tarski and Seidenberg that semi-algebraic sets are preserved by projections. The essential structure has been generalized in model-theoretic study of o-minimal structures.

Contrast this to the study of (first-order) Diophantine equations. Anyone who has studied number theory quickly appreciates the immense complexity of the structure of solution sets of integer polynomial equations, e.g. Pell equations, elliptic curves, etc. Undecidability results imply that there can be no simple uniform recursive decision procedure like that for the reals. Each leap into a higher dimension may require completely novel ideas. But this shouldn't be viewed as a detriment. Rather, it yields an unending source of rich problems that will constantly challenge our ingenuity.

-

When you talk about decidability in this context, you mean the decidability of the theory, not any particular model.

The theory of real closed fields and peano's arithmetics are different theories. The axiom of real closed fields include all the ring axioms. Peano arithmetics does not. Peano's arithmetics include induction whereas the axiom of real closed fields do not. As theories, i.e. sets of formulas, Peano Arithmetics and Real closed fields are just different. To say one is a subset of another does not even make sense.

You may be confusing the concept of models with the theory. The real numbers may be a model of real closed fields and the natural number is a model of peano arithmetics within it. However, formulas of real closed fields are decidable. In particular in these formula, the quantifier ranges over the domain of the real closed fields. For example, real closed field may decide whether there exists a solution to some equation; however, the quantifiers range over the domain of the real closed fields. You do not know anything about whether these solution lie in the natural numbers, for instance.

-

As others point out, the main reason for this seemingly paradoxical situation (all natural numbers are real numbers but the theory of the first one is much more complicated than the second one) is because natural numbers are not definable in the language of RCF.

We can use the same language to talk about them, say $\{0,1,+,\cdot\}$ and natural numbers are a substructure of real numbers. However being a subsructure doesn't make things simpler. Take for example prime numbers, do you expect that their theory in the same language is simpler than the theory of natural numbers? It doesn't need to be the case. The main issue as others have point out is quantification. Quantification over natural numbers can generate very complicated sets (arithmetical hierarchy) where as quantification over reals does not, in fact if we simply add order to the language then every quantified formula is equivalent formula with no quantifiers for reals, i.e. quantifiers do not increase the complexity of sets we consider for reals and can be eliminated (and that is how it is proven that RCF is decidable). We can show that this is not possible for natural numbers, quantifiers can increase the complexity of sets. The undecidability follow essentially from the fact that we can talk about computation of machines in the theories like PA and much weaker theories about natural numbers.

It might be helpful to look at something in between: consider integers. We can define natural numbers by using the fact that every natural number is equivalent to sum of four squares. Therefore they are going to be as complex as natural numbers. Another more tricky set in the middle: consider rational numbers. Their theory is similarly undecidable, however showing that we can define natural numbers in the their theory is much more complicated (this nice result is originally due to Julia Robinson). Another example: consider complex numbers. Their theory ACF is kind of even simpler than real numbers.

To make it even more clear, if we just add a predicate to the language that tells us which real numbers are natural numbers, then theory of real numbers with this predicate becomes undecidable. The main issue is that without such predicate natural numbers are indistinguishable from other real numbers in the language.

-