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

A confusion about Godel theorem and real numbers

  1. Oct 9, 2014 #1

    Demystifier

    User Avatar
    Science Advisor

    I am confused, since some claims about the first Godel incompleteness theorem and real numbers seem mutually contradictory. In essence, from one point of view it seems that the Godel theorem applies to real numbers, while from another point of view it seems that the Godel theorem does not apply to real numbers.

    1. point of view:
    The Godel theorem applies to arithmetic of natural numbers, as well as to any axiomatic system that contains the axioms of natural numbers plus some additional axioms. Real numbers can be axiomatized in that way: First one defines rational numbers as ordered pairs of natural numbers, and then one defines real numbers in terms of rational numbers, either in terms of Cauchy sequences or Dedekind cuts. Therefore the Godel theorem must apply to real numbers.

    2. point of view:
    But real numbers can also be axiomatized in a different way, without reference to natural numbers. As shown by Tarski
    http://en.wikipedia.org/wiki/Real_closed_field#Model_theory:_decidability_and_quantifier_elimination
    in such an axiomatization of real numbers it is possible to eliminate all quantifiers, which implies that the theory is decidable: any claim can be either proved or disproved.

    The contradiction between the two points of view:
    According to the Godel theorem and 1. point of view (and assuming consistency), in the theory of real numbers there is a claim ("This claim cannot be proved.") which can neither be proved nor disproved. According to the 2. point of view, there is no such a claim.

    Perhaps this might mean that two approaches to real numbers are not equivalent, but there is a claim that the two approaches are equivalent. To quote from http://en.wikipedia.org/wiki/Real_number :
    "The currently standard axiomatic definition is that real numbers form the unique Archimedean complete totally ordered field (R ; + ; · ; <), up to an isomorphism,[1] whereas popular constructive definitions of real numbers include declaring them as equivalence classes of Cauchy sequences of rational numbers, Dedekind cuts, or certain infinite "decimal representations", together with precise interpretations for the arithmetic operations and the order relation. These definitions are equivalent in the realm of classical mathematics."

    So which point of view (if any) is right, and what exactly is wrong with the wrong one? I am sure I misunderstood something, but I don't see what exactly would that be.
     
  2. jcsd
  3. Oct 9, 2014 #2

    ShayanJ

    User Avatar
    Gold Member

    I'm not good at this but from some introductory knowledge I have about mathematical logic, I think the first point of view can't be correct. Because a formal system is consisted of a language and some inference rules. The language is only a set of symbols which can be attached to each other in certain ways. To me, the way the language is defined, means that you can't use them to form layers(the way you explained in 1, rational numbers don't seem a problem to me but the way you defined real numbers, makes me doubt it) and go up and have a new language with same inference rules. At least if you can do such a thing, I don't think the system on the top of those layers can be connected to the base system so much that you can say "if Godel's theorem applies to the base system, so it should apply to the system on the top too!". I'm not sure about this but I think at least its not a trivial thing that 1) There can be such a layering consistent with mathematical logic and 2) If such a layering can be consistent with mathematical logic, then there is that much of a connection between the base system and the derived system.
     
    Last edited: Oct 9, 2014
  4. Oct 9, 2014 #3
    I don't want to get too much into details, but the short of it is that the standard first-order model-theoretic axiomatIzation of the real numbers as a real-closed field - your second "point of view" - is not strong enough to say things about natural numbers. It is also not equivalent to the axiomatizations described in the wiki article in that it cannot express the fact that the real field is Archimedian.
     
  5. Oct 10, 2014 #4

    Demystifier

    User Avatar
    Science Advisor

    Thanks for the concise but clear answer. But to be completely explicit, can I conclude that wikipedia is wrong when it says that the two definitions are equivalent?
     
  6. Oct 10, 2014 #5
    The part of the wikipedia article that you are referencing is not claiming that the characterization of the Reals as a real-closed field is equivalent to other characterizations. It is claiming that the various constructions of reals numbers; as Dedekind cuts of the rationals, equivalence classes of Cauchy sequences of rationals, certain kinds of decimals; are all Archimedian complete totally ordered fields (and thus isomorphic) once equipped with the "right" arithmetic and order.
     
  7. Oct 13, 2014 #6

    Demystifier

    User Avatar
    Science Advisor

    Thanks! :)
     
  8. Oct 14, 2014 #7

    Demystifier

    User Avatar
    Science Advisor

    This also answers the following question. If the Tarski axiomatization of real numbers is decidable, then why it can not decide whether the continuum hypothesis it true or false? The answer is: because the continuum hypothesis says something about a relation between natural and real numbers, while such an axiomatization cannot even talk about natural numbers.
     
  9. Oct 14, 2014 #8

    Erland

    User Avatar
    Science Advisor

    The problem is that in the theory of real closed fields, it is not possible to define a predicate N(x) which holds for an element a (in the interpretation R) if and only if a is a natural number. This means that this theory does not contain all arithmetic.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: A confusion about Godel theorem and real numbers
  1. On Godel theorem (Replies: 38)

  2. Godel Numbers (Replies: 3)

Loading...