Goedel's theorem, some questions.

[vanesch]

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.

 

[chronon]

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.

 

[matt grime]

"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.

 

[vanesch]

"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.

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.

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.

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.

 

[matt grime]

"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.

 

[vanesch]

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.

Sorry to insist, but I'm affraid we're talking next to each other (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.

 

[matt grime]

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.

 

[vanesch]

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.

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 realize 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.

 

[matt grime]

"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.

 

[HallsofIvy]

"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.

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".

 

[matt grime]

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 statements about the axioms" depends on the axioms we choose.

 

[master_coda]

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?

 

[vanesch]

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?

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.

 

[matt grime]

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.

 

[vanesch]

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.

Ah, we're converging

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.

cheers,
Patrick.

 

[Hurkyl]

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.

 

[matt grime]

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.

 

[selfAdjoint]

No, we've not found a system on which Goedel's method doesn't work

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.

 

[vanesch]

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.

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.

 

[matt grime]

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.

 

[vanesch]

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.

Yes, of course. The "trick" of Goedel is of course that a formal system is a mapping from any finite subset of the natural numbers into a finite symbol set, and that, in the case you're studying a formal system about the natural numbers, you can map statements ABOUT the formal system into expressions WITHIN the formal system. If we wouldn't do mathematics by writing a finite number of symbols on a row, we'd do quite different mathematics (hehe :tongue2: )

cheers,
Patrick.

 

[vanesch]

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?

Well, M is not so "unclear". You need all the axioms of integers that are necessary to have prime numbers, to have the theorem that all natural numbers can be written in a unique way as a product of prime numbers, you need all the axioms of logic and inference rules that are necessary to have all the reasoning schemes in the proof by Goedel to be valid, AND THAT'S IT, except for one detail: you need also to have that the axioms of the formal system A need to be reflected by true statements (axioms or theorems) in M.
And that's where things go wrong: G IS a theorem in M. So we cannot add ~G to it. But apparently M is "minimal" in that if you REMOVE axioms from M, then you cannot work out Goedel's proof anymore. I don't see easily how we could switch to a completely different "M" and still keep Goedel's proof.
Do you see my problem ?

cheers,
patrick.

 

[matt grime]

I see why you're having a problem, but M is picked based upon A (you omitted to mention that all the axioms of A must be true in M, which I presume is true, though i may be misremembering something), and there is obviously no reason why that M should be the M required if you apply goedel's argument to A+~G, or any other set of axioms.

 

[metacristi]

I've read only the beginning,from what I've seen matt grime has already 'solved the case'.Indeed an axiom is by definition a statement accepted as true without proof,the construct 'false axiom' is an oxymoron.Though a certain statement G or ~G (undecidable in a certain system L) remain unprovable in L' (constructed by adding G-or ~G-to the existing axioms) it is nonwithstanding true because of its axiomatic status.In fact all axioms of a formal system are accepted without demonstration being a subset of the set of all formulas (theorems) of a logical system which at its turn is a subset of all valid syntactically enunciations in that formal system.Semantically we can talk of the truth of a certain statement within a system if it is an axiom of the system or can be deduced from the axioms using the rules of inference defined in the system.

 

[vanesch]

I see why you're having a problem, but M is picked based upon A (you omitted to mention that all the axioms of A must be true in M, which I presume is true, though i may be misremembering something), and there is obviously no reason why that M should be the M required if you apply goedel's argument to A+~G, or any other set of axioms.

Yes, I see what you mean: M is depending on the formal system under study. But there I have the problem I mentioned. Let's push it still further:
We have formal system A, and M, and Goedel's proof, and G as undecidable in A but true in M. The the axioms in A are also truths in M.
Next we construct a formal system B = (A+~G) and, well, for sake of argument, an informal system N which is rich enough to apply Goedel's reasoning, and in which A and ~G are truths.
There is nothing that stops me from considering N as my informal system to study formal system A: N is rich enough to have Goedel's theorem applied, and the axioms of only A are truths in N. But Goedel's reasoning applied to pure A gives me G as a truth also in N as a framework, because N is rich enough to apply that reasoning, just as M was. This implies that N is inconsistent...

cheers,
Patrick.

 

[matt grime]

Correct, you could have studied A with N, and you'd have a system where ~G is true and (there is no proof of G or ~G) is true. However, it depends on "how" N or M must depend on A, and you're the one whose read the proof about this so you should be explaining it to me. Perhaps when we pick M we must specify certain things - you've already given us some of the things it must satisfy.

Can I rewrite the theorem abusing notation:

Given an finitely axiomatic system A which is strong enough to describe the natural numbers, there exists a system M depending on A, that contains A as a proper subsystem, and a statement G again dependent on A that is true in M and is undecidable from the axioms of A.

M may be unique for any given A (in which case your new problem vanishes). Or the construction of G in M may depend on M in some way which also makes your new problem go away. So there *is* something stopping you using N and assuming that G would be the same statement in either case.

 

[vanesch]

Correct, you could have studied A with N, and you'd have a system where ~G is true and (there is no proof of G or ~G) is true. However, it depends on "how" N or M must depend on A, and you're the one whose read the proof about this so you should be explaining it to me. Perhaps when we pick M we must specify certain things - you've already given us some of the things it must satisfy.

The funny thing is that Goedel, in his proof, does not talk about M. He just starts off reasoning (just as any mathematician would do in another domain) about how to number the symbols in the character set of A, how to number the formulas etc... as if all he uses to do so is self-evident (which it seems to be, when you read it !)
I think I'll go through Goedel's original article (which I have in a French translation) again. But it is long, with a lot of technicalities !
I would think, from the structure of the proof, that M itself doesn't intervene in the construction of his undecidable formula G: it just depends (I think) on the alphabet of A, the inference rules, the syntactic rules and so on ; things that are fixed when A is given.
But I'm sure I must be wrong somewhere! It would be too silly.

cheers,
patrick.

 

[matt grime]

But just remember that it states there is *an* extension of A, not that every extension of A will do, and the structure of M must be relevant to the construction of G (since G is a true statement in M)

 

[vanesch]

But just remember that it states there is *an* extension of A, not that every extension of A will do, and the structure of M must be relevant to the construction of G (since G is a true statement in M)

Let me write down the essential part of Goedel's proof:
The truth of G in M is deduced from its metamathematical interpretation: G is on one hand a formula about integers, but on the other hand it has the metamathematical interpretation: "G is undecidable", or, in more detail:
"For all Goedel numbers P of proofs in A, the proof which has Goedel number P is not a proof for G."

It is the very fact that Goedel arrived at simply CONSTRUCTING this expression, that makes one conclude that G is undecidable. Imagine that G is provable in A with proof with Goedel number P1, then it would contradict its own metamathematical meaning. Imagine that ~G is provable in A, then it's metamathematical meaning is that there exists a Goedel number P2 of a proof of G. So the only way for A to be consistent is that G is not decidable in A.
But we now just proved that there is no proof of G in A, which is exactly what G states (metamathematically). So G must be true (in our own reasoning scheme which I called "M").
Now, not speaking metamathematically, G is just a formula about integers, which thus must be true in M.

This is the crux of Goedel's proof.

I will go through the whole article again to see if somehow M (which Goedel doesn't even mention) plays a role in the construction of G.

cheers,
patrick.