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

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$.


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.