Godel - Completeness of axiomatic systems

[Adam Mclean]

I am aware of Godel's proof of the incompleteness of formal systems that allow for defining the natural numbers.

I noted recently in the Wikipedia entry for Godel's Incompleteness Theorem

"that both the real numbers and complex numbers have complete axiomizations".

Is this true?

Can anyone point me to any papers which provide a proof for this ?


Thanks,

Adam McLean

 

[chronon]

This is somewhat puzzling. If the writer is saying that moving from the integers to the reals gets rid of the incompleteness, then that is false. It may be that moving to a larger system doesn't introduce any more incompleteness (a sort of relative completeness), but I find that hard to believe in this case - think of the continuum problem.

I note that in the article on the reals there is a lot about their completeness, but this refers to a completely different concept - the convergence of Cauchy Sequences. It's possible (but I hope unlikely) that the writer might have got them confused.

 

[Adam Mclean]

Yes there is the Axiom of Completeness in the formal system of real numbers, which is as you say about Cauchy sequences. This is a different concept than that of the completeness of an axiomatic system which was explored by Godel.

Adam McLean

 

[master_coda]

The real numbers are consistent and complete; I believe this is known as Tarski's theorem.

 

[Hurkyl]

The trick is that the term "integer" cannot be defined in the theory of real numbers. Thus, while the real numbers contains the integers, the theory of real numbers does not contain the theory of integers.

 

[quartodeciman]

That is an interesting statement, Hurkyl. Does it have to do with an inherent ambiguity of the power set of the real numbers as axiomatized? In other words, there is ambiguity about what subsets of the real numbers are actually acceptable? Does that also influence the scope of a completeness axiom for real numbers?

 

[Hurkyl]

In other words, there is ambiguity about what subsets of the real numbers are actually acceptable?

Kinda...

the trick is that the theory of real numbers doesn't contain a set theory, but you can kind of mimic it with systems of equations like "x*y > 1 and x + y < 10". The theory of natural numbers doesn't have a set theory either, but the principle of mathematical induction is a very strong tool.

The (topological) completeness of the "real numbers" does depend on the "sets" you're allowed to use; the algebraic numbers, real numbers, and hyperreal numbers all satisfy the axioms of the theory of real numbers... despite the fact that once set theory is involved, the real numbers are the only ones that work.

 

[chronon]

I'm still puzzled. So we have

1) 1st order integer arithmetic. We have the axiom of induction, which you would think of as very useful in proving theorems . However, not all statements can be proved true or false.

2) 1st order real arithmetic. No axiom of induction, but in this case all statements can be proved true or false.

It seems counterintuitive somehow, especially as we tend to think of the reals as a much larger system that the integers. (Of course, since this is 1st order, there is a countable model of the reals) Is the problem that most things we say about the integers are 1st order, while for the reals we generally require higher order statements?

 

[Adam Mclean]

Although it may appear to our minds that the natural numbers are a subset of the set of real numbers, in fact they are not defined by the axioms of the real number system as special numbers and the idea of succession (as in the Peano axioms for natural numbers) will not be defined in the reals.

As I remember Godel's proof of the incompleteness used the idea of representing the statements of the formal system that defined natural numbers as a unique number using succession for the assignment of symbols to successive numbers and using prime numbers to create a unique factorisation, so one could uniquely go from the number back to the formula or statement.
As prime numbers will not be defined within real numbers, I suppose this also means that Godel's method could not be applied to the reals. I suspect there are other proofs of Godel's theorem that go down other routes but if they use this Godel numbering this will not be applicable to the reals.

Thus the formal system of real numbers does not inherit the incompleteness of systems that can define natural number arithmetic. It is our minds that cannot immediately separate what appears as the natural numbers in the reals from formally defined natural numbers.

I am beginning to understand this now.

 

[Adam Mclean]

It appears that many familiar mathematical systems are undecidable.

These include - groups, rings, fields, lattices, commutative rings, and ordered rings.

Does undecidability of a formal mathematical system imply incompleteness of its axiomatisation ?

 

[chronon]

The (topological) completeness of the "real numbers" does depend on the "sets" you're allowed to use; the algebraic numbers, real numbers, and hyperreal numbers all satisfy the axioms of the theory of real numbers...

Shouldn't we really say "the real numbers don't have a 1st order axiomatization". I'm happy that some systems have non-standard models, but not that the algebraic numbers can be thought of as a non-standard model of the reals.

Does anyone have a reference to the axiomatization we are talking about. If you just take out the (non-1st order) completeness axiom then, as I understand, the rest of the real number axioms are satisfied by the rationals. So presumably there is some other axiom to put in its place.

 

[chronon]

Shouldn't we really say "the real numbers don't have a 1st order axiomatization".

Actually, I don't think we should say that. Presumably we could add 1st order axioms which allow us to make sense of functions like sin(x), (although they wouldn't be defined as limits), which would get a lot closer to encapsulating what we mean by the reals. Such an axiomatizatiuon would allow you to define the integers (as roots of sin(\pi x)=0) and so would not be complete.

 

[Adam Mclean]

Is completeness of a formal axiomatic system only meaningful in those systems that use a first-order logic ?

Is the completeness of the real numbers merely a corollary of the fact that axiomatisation of real numbers requires a second-order logic ?


Sorry for all these questions. It is over 30 years since I studied this problem. For some strange reason it has suddenly pushed itself to the front of my brain and I somehow now immediately want to understand again what all this means.

 

[Hurkyl]

My algebra text is eluding me at the moment, so this is from memory;

The particular theory with which I'm familiar is that of real closed fields. A real closed field is an ordered field that has the additional properties:

If x is positive, then it has a square root.
Odd degree polynomials have a root.


My text proves Tarski's theorem in this form; if any first order statement is true in one model of a real closed field, then it is true in all models.

For example, any first order instance of the completeness axiom is true in the real numbers, and thus it is true in any real closed field.



To help swallow why it's okay for the algebraic numbers to be a model, consider this; the reason the completeness axiom normally fails is because of cuts generated by transcendental numbers. e.g. take A = {x | x < pi} and B = {x | x > pi} However, pi can be described algebraically, and the theory of real numbers isn't equipped with a way to build pi iteratively, such as by a power series.

such an axiomatizatiuon would allow you to define the integers (as roots of sin(pi x)) and so would not be complete.

I'm not sure that is true; I don't think you'll have the axiom of induction.

 

[chronon]

One of the ideas I've been toying around with is whether you could go beyond the algebraic numbers and define a system of numbers based on the roots of solutions of differential equations. In that case you could make sense of numbers like \pi and functions like sin(x), and still deal with a countable set.

I don't think that not having the axiom of induction matters, as this helps you to prove more things. It more a question of what you add that increases the number of things you can say in a theory (which then have to be proved or disproved)

Of course I could simply add to the real closed field axioms one saying that for every number x there is a number known as sin(x). This would be horribly incomplete, as there would no way of proving or disproving most statements involving sin(x)

 

[quartodeciman]

Probably 99.99% of students get the real number field presented in all its glory during first term calculus, where typically the least-upper bound version of completeness gets used, leaving the issue of subsets completely up in the air. Soon after, the theory of function limits is attacked with both feet. The object, of course, is getting to the "good" stuff (continuity, differentiability, integrability) and milking those particular cows.

 

[Adam Mclean]

I realized I failed to understand that

1 (real) is not equal to 1 (natural number)

These are different mathematical objects. Thus Godel incompleteness is not inherited by the Reals from the Natural numbers.

Thus all the agonising by philosophers of physics about
the implications for the incompleteness of formal
mathematical systems (as articulated by Godel)
for modern physics is pointless, as it seems that all of the
relevant mathematics used in contemporary physics
involves real and complex numbers and thus incompleteness
does not apply there.

 

[quartodeciman]

The real number 1 and the unsigned integer 1 are constructed differently. But there is an embedding isomorphism to carry a minimal ring of real numbers generated by 0 and 1 onto the signed integers. This entails the equivalent of a least upper bound postulate, which everyone who enfranchises basic real calculus insists upon. Since physicists are in this group of math users, then the supposed "problem" has returned.

But scientists like physicists are users of math, not slaves to it. The Gödel undecidability/incompleteness theorems don't really pose a problem, except to those who are obsessed with all the talk of some Theory Of Everything from which absolutely every true statement can be derived. That is silly. If the physicist can't find a convenient result, a good unkosher "trick" can do the job. Remember, producing scientific information is the goal, not working out all the deductive consequences. Despite all the TOE talk, physics (yes, theoretical physics!) remains a practical enterprise.
---
Thomas Edison waited while one of his lab assistants tried to calculate the inner volume of an oddly-shaped container using integral calculus. Finally, Edison's patience was lost. He swore and grabbed the container, filled it full of water and poured it into a graduated cylinder. Now that is science!

 

[chronon]

1 (real) is not equal to 1 (natural number)

I would say that they are the same (i.e. any philosophising about their differences is irrelevant). The reason incompleteness doesn't follow through is that there is no way to say anything about a general integer in real closed field theory.

Thus all the agonising by philosophers of physics about
the implications for the incompleteness of formal
mathematical systems (as articulated by Godel)
for modern physics is pointless, as it seems that all of the
relevant mathematics used in contemporary physics
involves real and complex numbers and thus incompleteness
does not apply there.

No. If this were really the case then physics would be much easier. Do black holes lose information?: You've got the equations, so just do the calculation. Does string theory predict the mass of the electron? - you could just work it out. Real closed field theory only let's you make statements about polynomial equations, not the differential equations of physics (hence my post above).

 

[master_coda]

No. If this were really the case then physics would be much easier. Do black holes lose information?: You've got the equations, so just do the calculation. Does string theory predict the mass of the electron? - you could just work it out. Real closed field theory only let's you make statements about polynomial equations, not the differential equations of physics (hence my post above).

Of course, just because you have completeness, and even an algorithm for determining if any given statement in the system is true or false, it doesn't necessarily follow that problems are now easy to solve. The elation of proving something is solvable quickly fades when it is proven that it will take a trillion years to compute the solution.

 

[Adam Mclean]

But there is an embedding isomorphism to carry a minimal ring of real numbers generated by 0 and 1 onto the signed integers. This entails the equivalent of a least upper bound postulate, which everyone who enfranchises basic real calculus insists upon. Since physicists are in this group of math users, then the supposed "problem" has returned.

I am not sure I understand this. Surely a least upper bound postulate requires a second-order logic, and thus
immunises us from incompleteness problems.
Can such an isomorphism bring with it the problems of formal systems that Godel discovered?

Can you please explain this further?

 

[Adam Mclean]

The elation of proving something is solvable quickly fades when it is proven that it will take a trillion years to compute the solution.

The undecidability of a formal system is very different from the decidability of particular propositions that may take a trillion years. After all, to a mathematician as opposed to a physicist, a trillion years is as far removed from infinity as the few seconds it would take to calculate 1 + 1 on a calculator.

 

[master_coda]

The undecidability of a formal system is very different from the decidability of particular propositions that may take a trillion years. After all, to a mathematician as opposed to a physicist, a trillion years is as far removed from infinity as the few seconds it would take to calculate 1 + 1 on a calculator.

Of course, I never said that decidability wasn't a good thing. Just that it isn't necessarily very useful for physics -> I was replying to a remark that completeness would make physics much easier.

If you actually need to solve a problem, and not just show that it is solvable, then the fact that the problem is solvable given an unlimited amount of time isn't good enough. It would be nice to be able to solve a problem before the end of all life in the universe.

 

[quartodeciman]

Surely a least upper bound postulate requires a second-order logic, and thus immunises us from incompleteness problems.

Or else it requires an uncountable axiomatic basis.

I don't know that it avoids undecidability/incompleteness. There just isn't a clean demonstration of them in the calculus real number system AFAIK.

Can such an isomorphism bring with it the problems of formal systems that Godel discovered?

Maybe we never do get rid of obstacles to a perfect computational/noncomputational scheme. But I don't think any of this holds up the natural development of physical thought. By the time anyone has answered something like this the theorist has moved on to complex, quaternion, octonion and other more elaborate and expansive (and maybe even more specialized) logistical systems.

 

[Adam Mclean]

Maybe we never do get rid of obstacles to a perfect computational/noncomputational scheme. But I don't think any of this holds up the natural development of physical thought. By the time anyone has answered something like this the theorist has moved on to complex, quaternion, octonion and other more elaborate and expansive (and maybe even more specialized) logistical systems.

I think that the complex numbers, quaternions, octonions, and so on, are merely defined as extensions of the real numbers, with additional axioms which define the i, j, k and the way of doing additions and multiplication of complex numbers or quaternions. Thus they will not change the completeness of the reals. As I recall quaternion multiplication is non-commutative, but this does not impact upon the real number addition. When dealing with complex numbers or quaternions one has to be aware that the operations + and * for these additional numbers to the system are not the same as + and * for adding or multiplying reals. The system of the complex numbers as well as the quaternions includes the real, numbers merely adding an extra layer of structure to it. As far as I understand this extra layer of structure will require second order logic - thus one can create the equivalent of cauchy sequences in these additional layers. Thus they do not import a first order logic layer that could create Godel incompleteness.

Perhaps there are other mathematical systems that can be defined on top of the axioms of the real numbers that can introduce Godel incompleteness. I have not studied Lie Groups but they seem to stitch together reals or complex numbers with groups. Groups are defined through a first order logic so are capable of exhibiting Godel incompleteness. Could this incompleteness be imported from groups into this extension of the reals that is a Lie Group. Or am I way off beam here ?

 

[Hurkyl]

Any statement you make about the complex numbers or quaternions (and presumably the octonions) can be rephrased as a statement about real numbers. For example:

If x is a nonzero complex number, then there is a complex number y such that x * y = 1.

vs

If the real numbers m and n are not both zero, then there exist real numbers p and q such that (m * p - n * q) = 1 and (m * q + n * p) = 0.

(The correspondence is x <-> m + ni and y <-> p + qi)

 

[quartodeciman]

The property that any polynomial function of degree > 0 over the complex field possesses at least one value from the same field that assigns that function a value of 0 does not easily translate to a corresponding property of the real field.

 

[Hurkyl]

It may not easily translate, but the point is that it does translate, and in a straightforward manner.

 

[quartodeciman]

?

Something like two polynomial functions over the real field coordinated so as to guarantee real field solutions for each of their corresponding equations? I don't recall seeing this being exploited to demonstrate the fundamental theorem of algebra.

 

[Hurkyl]

I can't imagine how knowing completeness would assist in proving that any complex polynomial has a root. However, completeness does assist in proving that, say, any hypercomplex polynomial has a root, as follows:

The complex numbers and the hypercomplex numbers are both models of a complete theory.
Every complex polynomial has a root.
Therefore, every hypercomplex polynomial has a root.

 

[DrMatrix]

The real number 1 and the unsigned integer 1 are constructed differently.

The reals and the integers are not constructed. The real numbers is a set which has certain properties. The set of integers is a set with certain other properties. You can construct a model for the integers using set theory. You can construct a model for the real numbers from the integers. The constructed model for the reals contains a model for the integers.

 

[DrMatrix]

The real numbers form a complete ordered field. This use of complete is not the complete used by Godel. The axioms of the real numbers are not complete in the sense Godel uses the word complete.

 

[Hurkyl]

Actually, I've been somewhat misleading: the theory of the real numbers is complete, not because of Tarski's theorem, but because of Godel's completeness theorem: first-order logic is complete.

Tarski's theorem is that the theory of real numbers is decidable.


edit: nevermind

 

[master_coda]

Actually, I've been somewhat misleading: the theory of the real numbers is complete, not because of Tarski's theorem, but because of Godel's completeness theorem: first-order logic is complete.

Tarski's theorem is that the theory of real numbers is decidable.

When referring to a theory, completeness and decidablility are the same thing. When referring to a logic, completeness means something different. The completeness of a theory does not follow from the fact that it is expressed using a logic that is complete, because those are two different concepts of completeness.

 

[Adam Mclean]

You can construct a model for the integers using set theory. You can construct a model for the real numbers from the integers. The constructed model for the reals contains a model for the integers.

Can I ask how one can construct a model for the real numbers from the integers ?

For real numbers there is no concept of the successor of a number, whereas this is the key concept for the integers. Indeed the idea of successor is one of the Peano axioms for the integers.

It seems to me that it is this idea of a number having a unique successor that is at the root of the incompleteness of a formal system. Godel's proof of his theorem rests on the idea of the successor of a number, as this allows one to assign a unique Godel number to a formal proposition in the system, and be able to read back from a unique Godel number to the string of symbols of the proposition.

Without being able to articulate in the formal language of an axiomatic system the idea of a unique successor (such as with the real numbers) then surely Godel's Incompleteness theorem cannot be proven nor even adequately expressed.

 

[Adam Mclean]

Actually, I've been somewhat misleading: the theory of the real numbers is complete, not because of Tarski's theorem, but because of Godel's completeness theorem: first-order logic is complete.

Tarski's theorem is that the theory of real numbers is decidable.

Does not the decidability of a formal axiomatic system imply the completeness of the axioms ?

 

[master_coda]

Can I ask how one can construct a model for the real numbers from the integers ?

A standard way of constructing a model of the reals using the integers is to first construct a model of the rationals using the integers, and then to construct a model of the reals using the rationals.


Of course, many people intepret this the wrong way. There seems to be this idea that if you can construct a theory of the reals from a theory of integers, then the theory of the reals must be the theory of integers with something added - therefore the theory of integers is contained in the theory of reals.

Except that interpretation is completely backwards. Constructing the reals using the integers proves that the theory of the reals is contained in the theory of the integers. Not the other way around.

It seems to me that it is this idea of a number having a unique successor that is at the root of the incompleteness of a formal system

What about the Presburger arithmetic? Presburger arithmetic is a theory of the natural numbers without multiplication - and it's complete and consistent. Despite the fact that it contains the concept of having a successor.

 

[Adam Mclean]

A standard way of constructing a model of the reals using the integers is to first construct a model of the rationals using the integers, and then to construct a model of the reals using the rationals.

Constructing the reals using the integers proves that the theory of the reals is contained in the theory of the integers. Not the other way around.
QUOTE]

I cannot quite understand this. The positive rationals can be modeled in the integers using Cantor's diagonalization which can establish a one-to-one correspondence. Thus each rational can be mapped uniquely onto an integer through the ordered pair (n,m) ~ n/m. The special property of rationals, that division can be defined for each rational number, could be described as a property of two ordered pairs (n,m) and (p,q) that is

n/m divided by p/q = (n*p)/(m*q) or the ordered pair of integers (n*p,m*q)

Thus division which is well defined for rationals can be modeled in integers even though it is not well defined for integers themselves.

Such a process is surely not possible for the special properties of the reals which go well beyond division. Can one model the limits of cauchy sequences (the main way to describe real numbers) in the integers ?

One can only model the reals using the rationals by abandoning first order logic, as the concept of limit as far as I understand cannot be understood without second-order logic.

Am I correct in this?

 

[master_coda]

Such a process is surely not possible for the special properties of the reals which go well beyond division. Can one model the limits of cauchy sequences (the main way to describe real numbers) in the integers ?

One can only model the reals using the rationals by abandoning first order logic, as the concept of limit as far as I understand cannot be understood without second-order logic.

Am I correct in this?

Well, obviously if you want to take advantage of the properties of the real numbers that can only be expressed using second-order logic then you have to start using second-order logic.

I should have been more accurate and stated that the first-order theory of the reals is contained in the first-order theory of the integers. If you want to reason using second order statements then you have to move beyond first order logic, but that's true for any first-order theory, not just theories of the reals.

 

[Adam Mclean]

What about the Presburger arithmetic? Presburger arithmetic is a theory of the natural numbers without multiplication - and it's complete and consistent. Despite the fact that it contains the concept of having a successor.

You are right. By this counter-example, the defining of unique successor does not lead to incompleteness. Although not a sufficient condition it could still be a necessary condition for incompleteness.

We can also see that Presburger arithmetic as it does not define multiplication has no fundamental theorem of arithmetic which is another of the key elements needed for Godel's proof.

 

[Hurkyl]

When referring to a theory, completeness and decidablility are the same thing. When referring to a logic, completeness means something different. The completeness of a theory does not follow from the fact that it is expressed using a logic that is complete, because those are two different concepts of completeness.

Aha! Now I understand why this always confuses me!

 

[Adam Mclean]

First-order logic is complete - Gödel's completeness theorem
Formal system of arithmetic is incomplete - Gödel's Incompleteness theorem.
Arithmetic is undecidable - Church's Theorem or Thesis (not yet proven)
Theory of real numbers is decidable - Tarski's theorem

Have I got that right ?

 

[master_coda]

First-order logic is complete - Gödel's completeness theorem
Formal system of arithmetic is incomplete - Gödel's Incompleteness theorem.
Arithmetic is undecidable - Church's Theorem or Thesis (not yet proven)
Theory of real numbers is decidable - Tarski's theorem

Have I got that right ?

The fact that arithmetic is undecidable is a consequence of the fact that it is incomplete - when referring to a formal system, completeness and decidablity are equivalent.

Church's theorem is that there is no general procedure that can decide first-order logic. Note that when referring to a logic and not a formal system, completeness and decidability are not the same thing. Also note that just because first-order logic is undecidable in general, it does not mean that we cannot come up with a way for deciding individual formal systems expressed using first-order logic.


Church's thesis is that anything that can be computed can be computed using the lambda calculus. Or Turing's version, that anything that can be computed can be computed using a Turing machine. This is not proven, and probably never will be (although it could be proven wrong).

 

[Adam Mclean]

Note that when referring to a logic and not a formal system, completeness and decidability are not the same thing.

Could I please intrude further on your generosity by asking you to explain this a little further, or perhaps point to a book or web page that might help me understand this point.

 

[master_coda]

When referring to a formal system such as arithmetic, you basically have three things:

1) the rules and symbols of the logic you are using
2) additional symbols used by your system (arithmetic uses 0,1,+,* and =)
3) a set of axioms (statements within the system that are asserted to be true)

We then say that the system is complete if for every statement within the system, either the statement can be infered from the axioms or its negation can be. In other words, the system is complete if every statement can be proven to be either true or false. This concept is also commonly referred to as decidability.

This is the meaning of completeness that is talked about by Godel's incompleteness theorem. It refers to the fact that any system that is powerful enough to formulate arithmetic is not complete -> there will be statements within that system that cannot be proven or disproven from the axioms of the system.


When referring to a logic, you generally just have:

1) symbols used by the logic
2) a set of rules for making inferences about statements made using the logic

We say that the logic is complete if for every formal system expressed using that logic, when there is a statement that is true in every model of that system, then that statement can be proven true from the axioms of the system.

For example, consider the theory of a field, expressed using first-order logic. We know of several common models that satisfy the axioms of a field - the rationals Q, the reals R and the complex numbers C. The fact that first-order logic is complete tells us that if something is true in every model of a field (every model, not just those three) then it must be provable from the axioms of a field.

Consider \forall x,x+x=x\Rightarrow x=0. This statement is true in every model of a field, so we should be able to prove it using the axioms of a field (and we can).

But consider \exists x,x\cdot x=-1. This statement is true for C, but false for Q and R. Which is why this statement is undecidable in the theory of fields. So the theory of fields is not complete.

This means that despite the fact that first-order logic is complete, we still can express statements in first order logic that are not decidable. So for a logic, completeness and decidability mean two different things.


Of course, this overloading of the word completeness is very confusing. When you first hear Godel's completeness and incompleteness theorems you generally assume that they are talking about the same concept of completeness, but they aren't. The completeness theorem is referring to the completeness of a logic - it proves that first-order logic is complete. The incompleteness theorem is referring to the completeness of a formal system - it proves that arithmetic is not complete.

 

[Ethereal]

Church's thesis is that anything that can be computed can be computed using the lambda calculus. Or Turing's version, that anything that can be computed can be computed using a Turing machine. This is not proven, and probably never will be (although it could be proven wrong).

Can you give an explanation of what it means for something to be "computable"? Also, it has been proven that whatever can be computed with the lambda calculus can be computed on Turing machines, is it not?

 

[master_coda]

Can you give an explanation of what it means for something to be "computable"? Also, it has been proven that whatever can be computed with the lambda calculus can be computed on Turing machines, is it not?

Well, in a more general sense a problem is computable if we have a mechanical process that can always correctly solve the problem. In other words, a problem is computable if an algorithm exists to solve it.

A mechanical process is generally assumed to be:
1) finite (it has a finite number of instructions and symbols, and always produces a result in a finite number of steps)
2) can be carried out by a human being with only the intelligence required to understand and execute the instructions

The Church-Turing thesis is just that such algorithm that exists can be implemented on a Turing machine (or using the lambda calculus, since they are equivalent).

 

[DrMatrix]

Without being able to articulate in the formal language of an axiomatic system the idea of a unique successor (such as with the real numbers) then surely Godel's Incompleteness theorem cannot be proven nor even adequately expressed.

Godel showed how to translate statements about a formal system into statements about integers. The formal system can be the integers or the reals. The translation does not depend upon the idea of a successor in the system being modeled. Godel's Incompleteness Theorem applies to any formal system large enough to contain arithmetic.

A standard way of constructing a model of the reals using the integers is to first construct a model of the rationals using the integers, and then to construct a model of the reals using the rationals.


Of course, many people intepret this the wrong way. There seems to be this idea that if you can construct a theory of the reals from a theory of integers, then the theory of the reals must be the theory of integers with something added - therefore the theory of integers is contained in the theory of reals.

Except that interpretation is completely backwards. Constructing the reals using the integers proves that the theory of the reals is contained in the theory of the integers. Not the other way around.

I'm not sure what you mean by "contained in". The issue is consistency. Godel showed that we cannot prove an axiomatic system is consistent. (Actually, what he showed is that if we can prove a system is consistent, then it is not consistent. So we hope we cannot prove the integers, for example, are consistent.) By showing we can construct a model for the reals from the integers, we show "If the integers are consistent, then the reals are consistent." The fact that the reals contain a subset that has the properties of the integers shows that "If the reals are consistent, then the integers are consistent." This tells us that the integers are consistent iff the reals are consistent.

 

[master_coda]

The fact that the reals contain a subset that has the properties of the integers shows that "If the reals are consistent, then the integers are consistent." This tells us that the integers are consistent iff the reals are consistent.

This is not true. Given only the axioms of the reals, we cannot find a subset of the reals that satisfies the axioms of the integers. Which is why the fact that the theory of the reals is consistent does not contradict the fact that the theory of the integers cannot be proven to be consistent.

 

[DrMatrix]

Are you sure about that? We have zero and one, the additive and multiplicative identities. Using 1 and addition, we can define a successor function, f(x) = x+1. We can define N as the smallest set that contains 0 and for every n in N, we also find n+1 in N.

I'm pretty sure that we cannot prove that the reals are consistent.