Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The theory of natural numbers (such as Peano axioms) is incomplete due to Gödel's incompleteness theorem. But, I heard that the theory of real numbers is complete (edit: not in the sense of Cauchy-sequences, but in terms of statements about real numbers). Does any one have a reference for this?

share|improve this question
1  
Maybe you are confusing different types of Completeness? Algebraic Completeness means that every cauchy sequence converges. Logical completeness means that every "true" statement is provable. en.wikipedia.org/wiki/Completeness_of_the_real_numbers en.wikipedia.org/wiki/Completeness_(logic)#Logical_completeness –  Ravi Donepudi Mar 8 '12 at 14:44
    
It doesn't look to me as if the poster was confusing different kinds of completeness. But if you want to list different kinds, why not also completeness in the sense of Dedekind? –  Michael Hardy Mar 8 '12 at 16:35
    
@MichaelHardy That and several others are listed in the second link I posted . But you are correct. It appears that I was the confused one, not the OP :) –  Ravi Donepudi Mar 8 '12 at 16:50
    
Found a related question from mathoverflow mathoverflow.net/questions/65112/… –  Memming Mar 17 '12 at 21:13
add comment

1 Answer

up vote 9 down vote accepted

In mathematical logic you have to be very careful how you phrase things. The "theory of the real numbers" is complete almost by definition, since it is the set of sentences in the language of fields which hold true in $\mathbb{R}$. (Moreover, in this sense the theory of $\mathbb{N}$ is also complete!)

What you want is that the theory of real numbers is decidable, i.e., there is an algorithm to determine whether a given sentence in the language of fields holds in $\mathbb{R}$. This follows from the completeness of the theory of real closed fields, which is a celebrated result of Tarski. Most introductions to model theory discuss this result and give a proof, including these lecture notes of mine: please see $\S 3.8$.

Added: A primary source is

A. Tarski, A Decision Method for Elementary Algebra and Geometry. RAND Corporation, Santa Monica, Calif., 1948.

share|improve this answer
2  
For a discussion purely for analysts, you want to read on the Tarski-Seidenberg theorem that projections of real semi-algebraic sets are semi-algebraic. (In logical terms, this says that the theory of real-closed fields admits quantifier elimination); see ch. in Gårding's "Some points of analysis and their history". It is this result that gives us completeness and decidability. In modern terms, it is also responsible for the o-minimality of the theory, that allows us to do real algebraic geometry in a purely logical setting; see van den Dries's "Tame topology and o-minimal structures". –  Andres Caicedo Mar 8 '12 at 15:04
    
@Andres: right on. In my notes, the proof of completeness of RCF is via quantifier elimination in RCOF (as usual...). –  Pete L. Clark Mar 8 '12 at 15:18
    
Also, if one is interested in effective algorithms, search on "cylindrical algebraic decomposition" (George Collins' CAD algorithm) –  Bill Dubuque Mar 8 '12 at 15:26
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.