# incompleteness in real analysis

Godel's theorem tells us that any sufficiently powerful consistent formal theory of the integers is incomplete; but what about formal theories of the real numbers? More precisely, what about theories of the real numbers that are categorical (i.e. have only one model)? One such theory is given by the ordered field axioms plus the least upper bound axiom (every non-empty set of reals that is bounded above has a least upper bound). Note that the usual Archimedean property is not the kind of axiom we can include in a theory of the reals if we want it to be a complete theory, because then we'll need axioms that explain what an integer is, and these will cause us to fall prey to Godel's theorem.

Tarski's decision procedure for real-closed fields is somewhat relevant, but note that it does not answer my question, since the field of real numbers is not the only real-closed field.

Incompleteness is a slippery subject, and I'm glossing over important technicalities (I suspect that a logician would say I should be more specific about what I mean by "every non-empty set of reals"), so experts should feel free to edit my post if it's clear to them that my question is based on some misapprehension (as long as it's also clear to said experts how I would ask the question once my misapprehension were cleared up!).

UPDATE: Maybe my question should have been something more like: Is there a meta-theorem that guarantees that all the questions that are likely to arise in a real analysis course are decidable? Or: Is there a decision-procedure for an interesting fragment of real analysis that includes all the standard theorems from a first course in real analysis? Perhaps the right context for this question would be some first-order theory that has the set of subsets of the reals and the set of functions from the reals to itself as primitives, with enough (but not too many!) axioms.

• From the title I was expecting a different meaning of the term "incompleteness". – KConrad May 16 '11 at 5:40
• @Zen: depending on what your axioms are you may not be able to talk about the integers. For example, the theory of real-closed fields is decidable, so does not let you distinguish a copy of the integers (because otherwise you could use it to pose Diophantine equations, which are undecidable). – Qiaochu Yuan May 16 '11 at 5:57
• More precisely, there is no sentence in the first-order theory of real-closed fields which is satisfied precisely by the subring generated by $1$ in such a field. – Qiaochu Yuan May 16 '11 at 5:58
• Answering the question as interpreted by @paseman: The first order theory of the reals (as an ordered field) is recursive (=decidable), by Tarski's result. But it is not omega-categorical. If you add exponentiation, the (now expanded) theory is still decidable (Macintyre and Wilkie, see MR1481447), assuming Schanuel's conjecture. If you add sine or cosine, you get a first order definition of the natural numbers, hence undecidability. – Goldstern May 16 '11 at 10:21
• This is implicit in Martin Goldstern's answer, but I want to extract it for emphasis: You worry that the Archimedian axiom requires knowing what the integers are. You should also worry that the l.u.b. axiom requires knowing what sets are. In fact, the latter should be more of a worry, because, once one knows what sets are, it's rather easy to define "integer" (as "a member of the smallest set containing 0 and closed under adding and subtracting 1"). – Andreas Blass May 16 '11 at 13:37

There is a philosophical current running through parts of descriptive set theory, and this includes anything that might be described as classical real analysis, to the effect that the realm of Borel mathematics is comparatively immune to the chaos of independence. On this view, one regards the Borel functions, relations and objects as being the most explicitly given, and the land of the Borel is the land of explicit mathematics.

For example, an important emerging field is the theory of equivalence relations under Borel reducibility, arising out of the observation that many of the most natural equivalence relations arising in other parts of mathematics, such as isomorphism relations on classes of algebraic structures, turn out to be Borel equivalence relations on a standard Borel space. Set-theorists seek to understand the comparative difficulty of the corresponding classification problems for these relations by considering the relations under Borel reducibility. This concept provides us with a precise way to measure the comparative difficulty of two classification problems, which then assemble themselves into a complex hiearchy, increasingly revealed to us. To give one example, it falls out of this theory that there can be no Borel classification of the finitely generated groups up to isomorphism by means of countable objects (this relation is not "smooth").

This theory has been largely immune from the independence phenomenon, for several reasons. Perhaps the best explanation of this is the fact that Borel assertions have complexity $\Delta^1_1$, which lies below the Shoenfield absoluteness theorem.

Theorem(Shoenfield Absoluteness) Any statement of complexity $\Sigma^1_2$ is absolute between any two models of set theory with the same ordinals.

In particular, this implies that the method of forcing is completely unable to affect existence assertions about Borel objects, since such assertions would have complexity $\Sigma^1_1$, as well as more complex assertions. Because forcing is one of the principal tools by which set-theorists have come to exhibit independence, this means that Borel mathematics is completely immune from the forcing technology.

Furthermore, when there are sufficient large cardinals, then one can attain an even greater degree of absoluteness in various senses. For example, in the presence of large cardinals there are various strong senses in which the theory of $L(\mathbb{R})$ is invariant by forcing. Thus, even the realm of projective mathematics ($\Sigma^1_n$ for any $n$) is unaffected by forcing, when there are sufficient large cardinals.

At the same time, we know that it isn't strictly true even that Borel mathematics is immune from independence, since the $\Delta^1_1$ level of complexity includes all of arithmetic, which therefore admits the Gödel incompleteness phenomenon. But because the method of forcing is struck down, however, none of the more spectacular independence results in the realm of analysis, such as the independence results concerning CH and cardinal invariants, arise at the Borel level of complexity. Thus, I believe that the realm of Borel mathematics may be the best, although imperfect, answer to your updated question.

At the same time, it must be said that although the method of forcing is ruled out as a means of proving independence for Borel existence assertions, we have no meta-theorem that says that there will not be some future method that is able to establish independence for such assertions. Surely a major lesson of logic over the past century is the pervasiveness of the independence phenomenon, and I believe that it is only a matter of time for such methods to arise.

I think you are asking several questions, so there are several answers:

1. It is important to distinguish between first order theories and higher order theories.

2. A first order theory (as long as it has an infinite model) is never categorical, by the Löwenheim-Skolem theorem.

3. For example, the first order theory of the reals as an orderd field has models in every infinite cardinality. The smallest model is the set of real algebraic numbers. You cannot formulate the least upper bound property in this theory, and you cannot formulate the property "is a natural number". On the plus side, the theory has a nice set of axioms, and it is categorical in every uncountable cardinality. (I.e., there is a unique model of size kappa, for each uncountable kappa.) [Edit: This is not correct, as pointed out by Chris Eagle below. The first order theory of the complex field is uncountably categorical.]

4. If you talk about second order theories, then the theory of the reals is categorical, and so is the theory of integers. (Also, in second order, the integers are definable within the reals.) In fact there is a finite set of second order statements (including "second order induction"; e.g. in the form "every nonempty set has a least element) characterizing the integers. (Or a single second order statement.)

5. There is no canonical concept of "second order provability". More precisely, the set of second order consequences (or even the set of first order consequences) of a second order axiom is in general not recursively enumerable (=not computably enumerable). This is one reason why proofs that are intended to be second order are usually formulated as first order proofs in set theory. (For example, my claim that "the second order theory of the reals is categorical" is provable in first order set theory. Of course, first order set theory cannot tell you explicitly what this second order theory is, by incompleteness)

• The first-order theory of the real ordered field is not categorical in any uncountable cardinal. Such theories are $\omega$-stable, and hence can never define an infinite total order. – Chris Eagle May 16 '11 at 14:02
• Thanks for pointing out this terrible mistake. Sorry. I must have been thinking of algebraically closed fields when I wrote this. – Goldstern May 16 '11 at 14:28
• I don't follow point 2. One can try to characterize {\bf Z} as a subset of {\bf R} using some version of the induction property, but I don't see how the ordinary axioms of real analysis will guarantee that a subset of {\bf R} satisfying this characterization exists. – James Propp May 16 '11 at 20:38
• This has meanwhile been answered by Chris Eagle, in his comment to Emil Jerabek's answer: (a) The second order predicate "For every unary relation R which holds at 0 and is closed under successors, R(x) holds", when interpreted in the reals, will hold exactly for the natural numbers. The question whether this set "exists" does not really appear; we can talk about it using the formula given, and we can show (practically from the definition) that it will satisfy Peano's induction axiom. (b) The sentence (a) is provable in first order ZF. – Goldstern May 20 '11 at 13:30
• Concerning your updated question: The "language of a first course in analysis" is typically a many-sorted (and higher-order) language, which talks about integers and reals, so incompleteness applies in principle. And even if you restrict to a one-sorted and first-order language, the integers sneak in through the use of the sine function. – Goldstern May 20 '11 at 13:33

Some points which I missed in goldstern’s answer:

• A categorical theory is always complete. In particular, the second-order theory of the reals with the least upper bound axioms as you defined it in the question is complete.

• The question is sort of self-contradictory, because the least upper bound axiom implies the Archimedean property.

• In order to fall prey to Gödel’s theorem, the theory needs not only to define integers, but also to be recursively enumerable. The latter never holds for second-order theories, but it can fail even for first-order theories. For example, the set of all valid statements in the standard model of first-order arithmetic is complete despite containing integer arithmetic.

• I know that the least upper bound axiom implies the Archimedean property if one has a predicate "... is a natural number" and suitable axioms for the properties of natural numbers (e.g., if $n$ is a natural number, so is $2n$). And since the real numbers must contain a copy of the integers (whether or not a particular theory of the real numbers is capable of talking about them), any ordered field satisfying the LUB axiom must be Archimedean. But this doesn't mean that the theory can express the Archimedean property. (Unless there's some clever second-order way to define "$x$-is-an-integer".) – James Propp May 16 '11 at 20:45
• @Jim: My gut-reaction to that is that I suspect I used to know some second-order way to express that predicate, but it's been a while since I've thought about that. But that's just a gut-reaction. More later maybe........ – Michael Hardy May 16 '11 at 21:53
• Once you've got quantification over sets, it's easy to define the integers. "$x$ is an integer" means "$x$ is in every subset of $\mathbb{R}$ containing $0$, $1$ and $-1$ and closed under addition". – Chris Eagle May 17 '11 at 14:04