Gödel's incompleteness theorem and real closed fields

I am familiar with the result of Gödel's incompleteness theorem. I find it hard though, to convince myself that when we replace normal number arithmetic with real closed fields, that there is an axiomatic system that is complete. After all, $\mathbb{N} \subset \mathbb{R}$, so why can't we use the more 'general' system for arithmetic? I know other people also struggle with this. Is there a more intuitive explantion as to why this result is possible and not contradictory to the incompleteness theorem?

Solution 1:

The reason that the result does not contradict the Incompleteness Theorem is that the natural numbers are not definable over the theory of real-closed fields. Roughly speaking, this means that there is no formula $F(x)$ of our language such that $F(a)$ is true in the reals if and only if $a$ is a natural number.

If there were such a formula, your intuition would be correct, and we could translate any problem about the integers under addition and multiplication into a problem about the reals. Then the theory of real-closed fields, since it is recursively axiomatizable, could not be complete.

We can produce a formula in the language of real-closed fields that "says" $x=1$. We can also produce a formula that says $x=2$, and a formula that says $x=3$, and so on. Then we can say also $x=1$, $2$, or $3$. But there is no single formula that says that $x$ is a natural number. (We cannot use infinitely long formulas.) There is, by the way, also no formula that says that $x$ is rational.

There is a similar phenomenon in the theory of algebraically closed fields of characteristic $0$. The theory is complete. From the fact of completeness we can immediately deduce, from the Incompleteness Theorem, that the natural numbers are not definable in the theory.

Added: There is a complete (in the informal sense!) classification of the sets that are definable over the theory of real-closed fields. The idea has been used to establish connections between algebraic geometry and model theory. A number of important recent results come from exploiting that connection.

Solution 2:

As has been mentioned, one cannot apply the theory of real-closed fields to solve Diophantine problems since $\rm\:\mathbb Z\:$ is not definable in the elementary language of real-closed fields. However, unless you have studied model theory, such an answer will probably lend little intuition on the matter. Towards such, consider the following remarks.

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 inequations - 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 pick a point $\rm\:r_0\:$ in each interval and test if $\rm\ f(r_0)>0\ \Rightarrow\ g(r_0)>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 innate 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.