Gödel vs Goldbach: Truth but Not Provability?

[pgimeno]

I was once told that Goldbach's conjecture could perhaps fall into Gödel's first incompleteness theorem, and be true but not provable. Is that really the case?

I mean, if Goldbach's conjecture were false it would be easily provable, as it would mean that an even number exists that is not the sum of two primes. Just take the counterexample and check with every prime less than that number.

But if it were true, would that be a change in the possibility to prove it? If so, what difference does it make? Are propositions of non-existence within an infinite set specially prone to be subject to Gödel's theorem, so that they are true but not provable?

 

[micromass]

Well, you'll need to be a bit careful with the notions of "true" and "provable".

We all have an intuitive idea of what natural numbers are. We can all work with them easily, and we know what kind of properties should hold for them. So Goldbach's conjecture being true, means that it is true for our intuitive notion of natural numbers.

Sadly, mathematics doesn't work with intuition. A mathematical theory needs axioms. So we try to axiomatize the natural numbers. But what axioms do we consider? We consider axioms which appear obvious and which allow us to reconstruct facts which are obviously true.
But nobody says that we have enough axioms! In our axiomatization, we might have given an axiom system which corresponds to our intuition, but maybe there are more axioms needed to completely describe the natural numbers.

And this is where Godel comes in. Godel has shown that there is NO axiom system that completely describes the natural numbers. Thus there may be statements which are true in our intuitive notion of natural numbers, but for which our axiom system is to weak to prove it.

One of these statements is (maybe) Goldbach: it may be true or false in our intuitive notion of natural numbers, but our axiom system may be to weak to show it. So, a possible answer is to extend the axiom system of the natural numbers, such that Goldbach does yield a positive or negative answer.

Something else I which to get to attention is Goodstein's theorem. This is a theorem about natural numbers which is true. But our axiom system turns out to be too weak to prove it. So to be able to prove Goodstein's theorem, they extended the axioms of natural numbers. This allowed a proof.
But note that there may be other extensions of the axioms such that Goodstein's theorem is false! But these axiom systems do not correspond to our intuition, and will not be interesting to consider for most mathematicians...

 

[D H]

I mean, if Goldbach's conjecture were false it would be easily provable, as it would mean that an even number exists that is not the sum of two primes. Just take the counterexample and check with every prime less than that number.

That is assuming that the counterexample can be found.

Suppose some mathematician proves that the counterexample, if it exists, must necessarily be greater than Graham's number, g₆₄. This will not prove the theorem is false, or true. All it will do is show that disproof by counterexample is out of reach. Suppose some other mathematician refines this proof and shows that the counterexample, if it exists, must be greater than A(g₆₄,g₆₄), where A(m,n) is the Ackermann function. This still will not prove the theorem to be true. While A(g₆₄,g₆₄) is unimaginably large, it is still finite. Goldbach's conjecture, if true, holds for all integers, including the rather large set of integers that are larger than A(g₆₄,g₆₄).

Disproof by counterexample is a very powerful tool, but only if you can find a counterexample.

 

[AlephZero]

Godel's theorem can not apply to this. Suppose it did apply. Then you could extend the axioms of mathematics in a consistent way by either adding the axiom that the Goldbach conjecture was true, or that it was false.

If you add the axiom that Goldbach is false, then there exists a finite even integer G which is not the sum of two primes.

If you assume Goldbach is true, the same integer G is the sum of two primes.

Even if G is so large that there is no practical way (at present) to check whether G is the sum of two primes or not, it can be checked in principle, in a finite time, by enumerating all the primes less than G.

So only one of the two assumptions is consistent with the other axioms of arithmetic, even if (today) we don't know how to tell which one is consistent. That contradicts Godel's theorem.

 

[micromass]

Godel's theorem can not apply to this. Suppose it did apply. Then you could extend the axioms of mathematics in a consistent way by either adding the axiom that the Goldbach conjecture was true, or that it was false.

If you add the axiom that Goldbach is false, then there exists a finite even integer G which is not the sum of two primes.

If you assume Goldbach is true, the same integer G is the sum of two primes.

Even if G is so large that there is no practical way (at present) to check whether G is the sum of two primes or not, it can be checked in principle, in a finite time, by enumerating all the primes less than G.

So only one of the two assumptions is consistent with the other axioms of arithmetic, even if (today) we don't know how to tell which one is consistent. That contradicts Godel's theorem.

That's not the point. Of course, if Goldbach were false, then there would be a counterexample. But the point is that the counterexample might not be described by the current axiom system.
Peano arithmetic is incomplete, thus there might be statement such a Goldbach that are unprovable. This simply means that the axioms are to weak to prove Goldbach. And thus that possible counterexamples can never be described formally.

Compare the situation by considering the existence of an inaccessible ordinal. The existence of such an ordinal does not follow from the axiom system, since it is to weak to prove anything. But, like in the integers, we have induction and recursion available...

 

[AlephZero]

The point I was trying to make was that the two systems
Peano + "Goldbach is true"
and
Peano + "Goldbach is false"
can not both be consistent. If we assume they are both consistent, we get a contradiction about a finite integer.

As I understand it, if Goldbach were an example of "incompleteness" in the Godel sense, then both of the above systems would have to be consistent.

Whether or not it is possible to prove or disprove Goldbach from Peano's axioms is a different question. I don't think Godel's proof claims to account for every possible unprovable statement in an axiomatic system.

 

[micromass]

But you got the same situation with

Peano + "Goodstein's theorem is true" and
Peano + "Goodstein's theorem is false"

They are both consistent, and we still wouldn't get a contradiction about a finite integers. My point is simply that we don't know the integers well enough to assume that we don't have any unprovable statements!

 

[pgimeno]

Thank you all for your replies.

Of course, if Goldbach were false, then there would be a counterexample. But the point is that the counterexample might not be described by the current axiom system.

This is right at the heart of my question.

So, if Goldbach's conjecture was indeed unprovable within Peano, and we add its negation to the axioms, what we would have is a finite natural number whose value can't be determined, that we can't write as an ordinary sequence of digits. A number that is in a kind of 'limbo' between the finite and the infinite numbers.

The conclusion I've reached after looking up Goodstein's theorem is that a counterexample, should it exist (within Peano), would fall into that 'limbo' category.

I'd be happy, however, to accept that if a finite number can't be described with Peano arithmetic, then it doesn't exist. Which means that if Goldbach's conjecture is found to be unprovable, it's basically true for all I care.

 

[AlephZero]

I'd be happy, however, to accept that if a finite number can't be described with Peano arithmetic, then it doesn't exist.

That is exactly the problem I am having with Micromass's objection to my logic.

I admit it is a long time (several decades!) since I first studied this stuff, but from what I remember, Peano's axioms and Godel's proof were both presented as being about the countable set of integers we are all familiar with. So was Goldbach's conjecture, unless somebody has changed its meaning after he made it.

So either we have some "definition creep" or mathematical revisionism going on, or (which is quite possible!) I'm not being too smart here...

 

[micromass]

Hmm, I did some more research, and it appears that AlephZero is indeed correct. It is still possible that the Goldbach conjecture is unproveable, but according to some theorems of logic, this would imply that the Goldbach conjecture is true.

Thus if somebody gives a proof that Goldbach conjecture is unproveable, then this implies that the Goldbach conjecture is true (although it wouldn't be a proof that it is true...)

I was thinking of nonstandard models of arithmetic ( http://en.wikipedia.org/wiki/Non-standard_model_of_arithmetic ), but it appears that it doesn't apply to Goldbach's conjecture. So I'm sorry if I confused anybody!

 

[pgimeno]

Hmm, I did some more research, and it appears that AlephZero is indeed correct. It is still possible that the Goldbach conjecture is unproveable, but according to some theorems of logic, this would imply that the Goldbach conjecture is true.

Thanks for clearing it up. Could you please point me to these theorems? I'd like to understand why the same can't be applied to "not Goldbach", i.e. by your sentence, if the proposition "Goldbach is false" is unprovable, then it's true, therefore Goldbach is false. Since it can't be both, there must be something in particular that I'm missing related to the contents of the conjecture, and I'd like to know what.

 

[micromass]

The difference is that Goldbach's conjencture is a "universal" statement. That is, the statement of Goldbach's conjecture is "FOR ALL natural numbers ...". And it can be proven in mathematical logic, that any universal statement that is unproveable, is true.

The negation of Goldbach, on the other hand, is an "existential" statement. That is, it is "THERE EXISTS a natural number ..." And this is not a universal statement.

More information, and a brief explanation on why this is true, see: http://mathforum.org/kb/thread.jspa?forumID=193&threadID=435233&messageID=1376382

 

[pgimeno]

Ahh, thanks! That finally settles my question in the OP: indeed, propositions of existence (and therefore also propositions of non-existence) are special, because of that property called "Sigma-1 completeness", which is what I invoked unknowingly when I said to take the counterexample and check.

So, we have the paradox that if Goldbach is shown to be unprovable, then it will be proved. Delicious. Well, that happened with Goodstein's theorem too.