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.