# 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?

-
The point is that there is no first-order sentence in the theory of real closed fields which is satisfied only by the subring generated by $1$ in a real closed field, so we can't talk about the natural numbers. –  Qiaochu Yuan Jul 1 '11 at 19:01

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.

-
Is there any reference for the classification in the addition - or good place to read about it? –  Mark Bennet Jul 1 '11 at 20:55
@Mark Bennet: The major figure is Ehud Hrushovski. There is a book about his methods. Other important figures are Zil'ber, Wilkie, MacIntyre, Dickmann. There are many others, it is a very lively field. –  André Nicolas Jul 1 '11 at 21:10
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.
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.