Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Godel - Completeness of axiomatic systems

  1. Jul 22, 2004 #1
    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
     
  2. jcsd
  3. Jul 22, 2004 #2
    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.
     
  4. Jul 22, 2004 #3
    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
     
  5. Jul 22, 2004 #4
    The real numbers are consistent and complete; I believe this is known as Tarski's theorem.
     
  6. Jul 22, 2004 #5

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  7. Jul 23, 2004 #6
    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?
     
  8. Jul 23, 2004 #7

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  9. Jul 24, 2004 #8
    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?
     
  10. Jul 24, 2004 #9
    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.
     
  11. Jul 24, 2004 #10
    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 ?
     
  12. Jul 24, 2004 #11
    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.
     
  13. Jul 24, 2004 #12
    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 [itex] sin(\pi x)=0[/itex]) and so would not be complete.
     
  14. Jul 24, 2004 #13
    Is completeness of a formal axiomatic system only meaningful in those sytems 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.
     
  15. Jul 24, 2004 #14

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.



    I'm not sure that is true; I don't think you'll have the axiom of induction.
     
    Last edited: Jul 24, 2004
  16. Jul 24, 2004 #15
    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 [itex]\pi[/itex] 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)
     
  17. Jul 24, 2004 #16
    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.
     
  18. Jul 27, 2004 #17
    I realised 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.
     
  19. Jul 27, 2004 #18
    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!
     
  20. Jul 27, 2004 #19
    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.

    No. If this were really the case then physics would be much easier.:approve: 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 lets you make statements about polynomial equations, not the differential equations of physics (hence my post above).
     
  21. Jul 27, 2004 #20
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Godel - Completeness of axiomatic systems
  1. Non-axiomatic systems (Replies: 6)

  2. Godel again (Replies: 2)

  3. Godel Numbers (Replies: 3)

Loading...