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

Goedel's theorem, some questions.

  1. Sep 20, 2004 #1

    vanesch

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Hello All,

    First of all, I have to warn that I'm not a mathematician (but an engineer and physicist) so I might not know some elementary results, terminology etc...

    I remember long ago having had a course on formal logic and Goedel's theorem and so on, and recently I read a small book on the subject, which brought back some souvenirs.

    If I remember well the structure of Goedel's proof, he embeds the metamathematical statements such as "there exists a proof" etc... within an axiomatic system of the natural numbers, and expresses these metamathematical statements as properties to be satisfied by natural numbers.
    He then carefully constructs a statement about natural numbers, G, which is constructed from the metamathematical statement "there exists no proof of the statement G or of ~G". So G is a formula in the axiomatic system of which we know metamathematically that there exists no proof of it, nor of its contrary, so G is undecidable within that axiomatic system.

    So people then usually claim that although G cannot be proven within the axiomatic system, we know it is true. This by itself is not a contradiction, because our metamathematical reasoning is based on other axioms, and hence another Goedel numbering, which itself must also produce a formula G', but which is not G.

    But I now wonder: if no proof of G nor of ~G can be given, we can just as well add ~G to the axioms (and not G, as is usually done).
    So now we have a strange system of axioms of the natural numbers, which contains a statement of which we somehow "know it is false". Nevertheless, this system is consistent. In what way do we get now different mathematics for the natural numbers ?

    I mean, let's for the sake of argument say that Fermat's last theorem is such a formula G. So if Fermat's last theorem is undecidable, we can just as well add the negation to the axioms:
    "there exists numbers n>2 and x, y and z such that x^n + y^n = z^n".
    Then we can take the smallest ones, say n1, x1, y1 and z1. And from there on, we can probably deduce a lot of theorems using n1, x1 etc... These must be very strange theorems.
    How should one think then of this system of natural numbers which is consistent, contains all the "basic" ingredients of the natural numbers, and which also contains a "false axiom" ?

    cheers,
    patrick.
     
  2. jcsd
  3. Sep 20, 2004 #2
    This is called a nonstandard model of the integers. It satisfies the integer axioms but it contains more than the true integers 1,2,3... . The supernatural numbers are one such model. Unfortunately there isn't much on the web about such non-standard models. If you do a search for "Tennenbaum's theorem" you will get an idea of what is happening in the subject.
     
  4. Sep 20, 2004 #3

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    "So people then usually claim that although G cannot be proven within the axiomatic system, we know it is true. "

    No, we don't. There is no absolute truth in mathematics. Consider all the axioms of geometry except the parallel postulate. We know the PP is independent of the others since we may add it or a contradictory statement to the axioms and get models for the new system (euclidean, spherical, hyperbolic). In what sense then is the parallel postulate "true"?

    There is no such thing as a false axiom. Or even a "false" axiom. Whether we choose to add the axiom or a negation is largely a matter of what seems right. For instance the axiom of choice is independent of ZF set theory; some people add it in some people reject it. There are good arguments for both, as well as, say, for the axiom of constructibility.
     
  5. Sep 20, 2004 #4

    vanesch

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Yes, I understand that of course. Only, the metamathematical statement in Goedel's theorem says that G should be true (in that indeed, that G, as a property of natural numbers, is undecidable within the axiomatic set chosen) within a larger set of rules of inference which are used as metamathematics to guide the theorem in the first place. These axioms (although not made formally explicit) seem reasonable, so it is weird that we can have a consistent system of natural numbers which contradicts these metamathematical axioms. If you deny the "reasonableness" of the metamathematical axioms, you also destroy Goedel's proof.

    The way I saw things, was as follows:
    we have a set of metamathematical axioms, M. They are essentially rules of inference, the way Goedel uses them, together with one or other set of axioms for the integers, rich enough to be able to talk about goedel numbers.
    Usually M is not written out as a formal language.

    We have a formal language and axioms A of the integers and inference rules which is our formal system under study. Using M, we arrive at the metamathematical statement "formula G is not decidable in A" which translates as a formula in A exactly by G.
    However, the statement "formula G is not decidable in A" is decidable and true within M (that's Goedel's proof!).
    Now let us construct the formal system B = {A + ~G}. The difficulty is that if we still consider M (unchanged), we have of course still the conclusion that G is undecidable within A but true in M. And it is false in B. So how can we reconcile M and B ?? Remember that B is a consistent axiom set for the natural numbers, just richer than A.

    Thanks! I never heard of that, but it must be something I'm alluding to. It must be something like non-standard analysis. But I have more conceptual problems with something like non-standard integers ; after all (this is probably naive on my part) if we have a set of supernatural integers, we can take the smallest one, and that one should have a precise value in that it is equal to a finite number of successors to 1.
    You should be able to write it down in base 10 ! Or is that where I'm missing things ?

    Still, it doesn't solve my initial problem...

    cheers,
    Patrick.
     
  6. Sep 20, 2004 #5

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    "We have a formal language and axioms A of the integers and inference rules which is our formal system under study. Using M, we arrive at the metamathematical statement "formula G is not decidable in A" which translates as a formula in A exactly by G.
    However, the statement "formula G is not decidable in A" is decidable and true within M (that's Goedel's proof!).
    Now let us construct the formal system B = {A + ~G}. The difficulty is that if we still consider M (unchanged), we have of course still the conclusion that G is undecidable within A but true in M. And it is false in B. So how can we reconcile M and B ?? Remember that B is a consistent axiom set for the natural numbers, just richer than A."

    but we have added another axiom, so the original metaproof is no longer valid in the extended system.

    The statement G undecidable in A is still true *in A*, but we are no longer in A, we are in A+~G.

    there is nothing problematic there. consider the integers, then there is no x satisfying 2x=1, we extend to the richer set of the rationals and there is a solution, but that doesn't mean there is a solution in the 'smaller' set.
     
    Last edited: Sep 20, 2004
  7. Sep 20, 2004 #6

    vanesch

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Sorry to insist, but I'm affraid we're talking next to eachother (or I don't see your point). Yes, I know that the statement "G is undecidable" is only valid in A. But at the same time, in M, we derived that G is indeed true. So G must be a property of integers which is true within M.
    But now we have defined a new axiomatic set of the integers which is consistent, and where G is explicitly denied (as the new axiom). So how can M (in which we derived G, as a statement about integers) say that G is true, and have a consistent system, B, in which G (also as a statement about numbers) is false. The only way to accept this is to say that M and B are not compatible. But M was the basis of our metamathematical reasoning! Why shouldn't it be valid anymore for B, while it was valid for A ??

    In reply to your remark, I understand of course that the G we derived, as a metamathematical statement, pertains only to the formal system A. But as a property of numbers, it can still remain a property of numbers, in ANY system that is a superset of A. In such a new system it looses of course its significance as the statement that "G is undecidable", but it remains a formula about integers. That's exactly what we did with the definition of B: it is A, and the negation of G.
    And that's where I don't understand the clash with M.

    cheers,
    Patrick.
     
  8. Sep 20, 2004 #7

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    You've not derived G to be true from the axioms, A, you've derived a statement about G to be true. If you've derived G to be true then it follows from the axioms, and is not independend of them and is hence not undecidable.
     
    Last edited: Sep 20, 2004
  9. Sep 20, 2004 #8

    vanesch

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Ok, I'm missing something. Of course I've not derived G from A. I've derived that G cannot be derived from A, but using M (by M I mean the not formalized axioms Goedel uses in his proof - so NOT the formal system A we're studying), I can derive G as a metamathematical statement, and HENCE also as a statement about integers, formulated in the language of A (which has an image in M). That statement about integers is then true in M on the same footing as the statement that G is not decidable in A is true in M.

    Let us take that the numerical transcription of G in A takes on the form:
    "For all n, there exist two prime numbers p and q such that p+q = 2n."
    (of course I realise that the statement of G as a number property must be way more complicated, but take this as an example).
    Using our metamathematical reasoning, it means:
    the statement "for all n, there exist two prime numbers..." is undecidable in A".
    Goedel proves (using M) that this statement is indeed undecidable.
    So the statement "for all n, there exist two prime numbers..." must be true from the point of view of M.
    But we also know that we can construct a formal system B where exactly this statement is denied (namely all axioms of A, and the negation of the above statement). My problem is in the clash between this consistent formal system B about integers, and the non-formal axioms M that form the basis of the reasoning in Goedel's theorem.
    From M we prove that all even numbers are the sum of two primes, and B proves the inverse (trivially, because it is an axiom in B). But M is normally not depending on the exact formal system A or B we're studying, because otherwise whether or not the reasoning in Goedel's theorem is valid would depend on exactly what object it is studying.

    Is it wrong to assume that the statement G (which has two faces, namely a metamathematical statement, namely "G is undecidable in A", on one hand, and on the other hand a statement about integers) is also a statement about integers in M ? Because this is the way it is usually formulated:
    within A, G is undecidable, but that means that G is true (exactly because G means "G is undecidable"). True on the same level as all statements in Goedel's theorem, not true on the level of the formal system A. I symbolised the informal axiomatic content of the machinery used by Goedel as "M".

    cheers,
    patrick.
     
  10. Sep 20, 2004 #9

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    "So the statement "for all n, there exist two prime numbers..." must be true from the point of view of M."

    I'm sorry (Goedel isn't 'my thing) but I don't see why this follows, but I'm not familiar with this logic theory way of dealing with things.

    If that is true, then surely the statement saying it is undecidable is false, but we know that that statement is true.

    and what do you mean by true anyway? the only things that are true are those that are deducible from the axioms, and thus depends on what axioms you are adopting.

    Let me give an example

    Suppose A is the set of axioms of geometry without the parallel postulate (PP). and M the statements we make about objects "in A"

    Then i can form the statement, G: given a line and a point there is a line through the point not intersecting the other line.

    this is demonstrably unprovable by giving models where it is true and where it is false,

    at no point does G actually 'become' true in M.
     
    Last edited: Sep 20, 2004
  11. Sep 20, 2004 #10

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Perhaps I'm missing something, but the "parallel postulate" certainly is a statement you can make about object "in A". G "becomes true" if you add PP to A.

    If I remember correctly (I never read Goedel in the original German), Goedel used the word true ("treu" in German?) to mean specifically "provable". He never claimed that there were "true" statements that could not be proved. He claimed that, in any system of axioms large enough to encompass the natural numbers, if the axioms are consistent, there must exist statements that neither be proven nor disproven: are "undecidable".
     
  12. Sep 20, 2004 #11

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    But vanesch appears to be arguing that PP, in this analogy, at some point is true *without* adding it in, and this is where i'm confused at his confusion: the whole "must be true from the point of view of M (statements made about geometry)" this is the bit i don't get: the truth or otherwise of a statement in the "class of statments about the axioms" depends on the axioms we choose.
     
  13. Sep 20, 2004 #12
    What I think vanesch is saying is that:

    Suppose we have a system A, and a statement G within that system. Then, you have a larger framework M that you use to show that

    1) G is undecidable in A
    2) G can be proven from the axioms of M

    So what happens if you take A+~G?
     
  14. Sep 20, 2004 #13

    vanesch

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Yes !

    You could now simply conclude that B = A+(~G) is not compatible with M, but that's where I'm having difficulties in this specific case, because the larger framework M is supposed to be accepted (otherwise Goedel's theorem is not valid - I never heard people say that they consider sometimes Goedel's theorem as not valid). M is supposed to contain *SOME* axiom system concerning the integers (it could be a copy of A, but also something else) in such a way that it is rich enough to be able to talk about Goedel numbers (prime numbers, powers, products etc) and quantor logic.

    cheers,
    Patrick.
     
  15. Sep 21, 2004 #14

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    OK, now I understand what you're saying, but I don't understand why it is that A+~G needs to be compatible with M.
    All this does is show that there is an extension of A in which the undecidable (in A) statement is true. By symmetry there is an extension of A in which G is false. And?
    What is perhaps surprising is that Goedel's theorem is always true, but then it is based upon a certain set of axioms.
     
  16. Sep 21, 2004 #15

    vanesch

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member


    Ah, we're converging :smile:

    Let me explain why I find the incompatibility between M and (A+~G) disturbing.
    What is usually said as a comment to Goedel's theorem goes like this:
    We assume M to be true (the thing that was at the basis of Goedel's theorem in the first place).
    We study A. We find that G is undecidable in A, and true in M.
    So arithmetic as axiomatised in A is not complete. No big deal you say, it is just that we forgot a few axioms. Let's add them.
    Usually, people then say: as we know that G is true (in M), we construct C=(A+G). But now we can repeat Goedel's proof (again in M) on the formal system C. So we will find again another undecidable statement G2 in C (but which is true in M). Etc... hence arithmetic is fundamentally undecidable because no matter how many axioms (understood to be true in M) we add to our initial formal system A, we always (by applying Goedel's reasoning in M) we find an undecidable formula G_n in (A+G+G2+...+G(n-1)).

    But now I'm being nasty, and I don't add G but ~G to A. Hence my problem. Because if B=(A+~G) is a formal system that has all the nice properties of integers we want, if it is incompatible with M we cannot apply Goedel's reasoning anymore ; or because we have to abandon M, or because arithmetic statements which we know are true in M (such as G) are not true in B, so our projection of metamathematical statements into B will not work.
    The conclusion then seems bizarre: we've found a formal system B of arithmetic on which Goedel's theorem doesn't work. :confused: :confused:

    cheers,
    Patrick.
     
  17. Sep 21, 2004 #16

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    On a side note, Goedel's incompleteness theorem assumes there are only a finite number of axioms. It can fail if you have infinite axioms.
     
  18. Sep 21, 2004 #17

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    No, we've not found a system on which Goedel's method doesn't work, since you've M is not a consistent system that contains A+~G as true statements, the M we must use here will be different since it must be compatible with the "smaller" set of axioms. That isn't a problem, we could equally form M as a system where we declare ~G to be true, surely, I'd want to know when you must pick M, and its true statements in comparison with A ie, given A, we then pick M. or are you saying that Goedel states there is a universal M for all A? Well, obviously that can't be true as your reasoning shows.

    And for, Hurkyl, can we have a countable set of axioms and stil have Goedel's theorem true, or even a set of axioms, as opposed to a proper class of of axioms.
     
  19. Sep 21, 2004 #18

    selfAdjoint

    User Avatar
    Staff Emeritus
    Gold Member
    Dearly Missed

    Tarski proved that Goedel's method does not work on geometry. The "BSS Machine" discovered a large class of algebraic systems over the reals for which it doesn't work. I gave links to this work here a long time ago.
     
  20. Sep 21, 2004 #19

    vanesch

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Ok, let me push this a bit further.
    So we have:
    M (which includes A) as an informal system, and we talk about formal system A. In M we show that the formula G in A is undecidable, but is true in M.

    Let us remember that G is a formula, using the elementary symbols of A (which have of course a counterpart in M), expressing a property of integers.

    Now we would like to move on to apply a Goedel reasoning to formal system B=(A+~G). You say that we now need a different M, say N, as informal system to reason in. This might indeed be the thing I've been overlooking. But it is clear that N cannot be M+~G !! That is an inconsistent system, because G follows from M. So what is N ???

    cheers,
    Patrick.
     
  21. Sep 21, 2004 #20

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    I didn't say N would be M+~G,

    the simple way to think of it is N is M but with the truth of all the statements deduced from G switched, if you'll allow me to state it like that. I think this *is* the nub of the issue: there need not be a universal M for all A, can't be in fact, and although you say "what is N???" an equally good question is "what is M???" how have you picked M out for the first set of Axioms, A?

    It's a little like an epsilon delta proof in analysis, given e there is a d, and it needn't be the same d for every e.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Goedel's theorem, some questions.
Loading...