From: hal@finney.org
Date: Tue Apr 03 2001 - 00:30:16 MDT
Lee writes:
> Here is a puzzle that I formulated on this subject that's fun.
> A great mathematician is at a party, and two students come
> up to him. One says, "I have found a proof that Goldbach's
> Conjecture is unprovable!". The mathematician snorts, "Go
> away, you crackpot". Then the other student says, "I have
> found a proof that whether or not there exist infinitely
> many prime pairs is unprovable!", and the mathematician's
> eyes light up and he says "Oh, really!? Please tell me
> more!". Why was the mathematician eager to hear out the
> second student, but not the first?
I'll give what I think is the answer, but then I'll give a counter-
argument.
Goldbach's Conjecture is that every even number is the sum of two primes.
If it is false, there must be an even number which is not the sum of
two primes. If such a number exists, then by showing it we could show
that GC is false and GC would not be unprovable (that is, it would be
provably false). For GC to be unprovable, therefore, would mean that
no such number exists. But this is simply the statement of GC itself,
so to show it to be unprovable (undecidable) is to show it to be true.
Hence you can't show GC to be unprovable.
Now here's my counter-argument. When we speak of provability, it is
in the context of a certain set of axioms. Mathematicians have agreed
upon a set of axioms which characterizes the behavior of the integers.
The question of GC provability is then in the context of this set of
axioms.
However we can imagine a weaker set of axioms, one which does not allow
us to make all the proofs we have now. I don't know enough mathematics
to give a specific example, but by analogy think of Euclidean geometry
without the parallel postulate. You can still make a lot of proofs,
just not all of them.
It's conceivable that in this weaker axiom system, we could show that
GC is unprovable. In fact we might be able to show that a number of
well-established theorems are unprovable. I know this is possible in
geometry; for one thing, you can show that the parallel postulate itself
is unprovable (and hence independent) from the other axioms.
Since we can conceive of this, it's also possible to imagine that
GC can be shown to be unprovable even in the full axiom system.
It's possible that an even stronger axiom system would be needed to
prove the GC.
Now, how does this fit with the original argument above, which seemed
sound? Again, think of the analogy to Euclidean geometry minus the
parallel postulate. For a long time it was thought that this set of
axioms might fully characterize the plane, and people spent years trying
to derive the parallel postulate from the others. However it turned out
that this was wrong; this truncated geometry does not fully characterize
the plane. There are non-planar systems which satisfy the remaining
axioms but which behave differently with respect to parallel lines.
The truncated axiom system leaves a certain ambiguity with respect to
certain kinds of questions.
Applying this analogy to the integers, for GC to be proven undecideable we
would have to find that there was some class of numbers which satisfies
the postulates of arithmetic, but for which GC was indeterminate.
For example, perhaps we could extend the integers with a new class of
numbers that was intermediate between the countables and the infinites.
These numbers could perhaps be able to satisfy the axioms of arithmetic,
but to leave some ambiguity about whether they could be said to be the
sum of two primes. Depending on how we interpreted the applicability
of the axioms to these new numbers, we might get different results with
regard to the truth of GC. Then we could say that we had shown that GC
is unprovable.
Admittedly, it seems unlikely that such an ambiguity could exist in
such an old and well studied a field as arithmetic. However our minds
are only of finite power and it's possible that there are subtle ways
in which the integers could be extended and still satisfy the axioms.
After all, intelligent men for centuries still thought that the parallel
postulate might follow from the others. We could be making a similar
mistake about the completeness of our arithemetical axiom systems.
Hal
This archive was generated by hypermail 2.1.5 : Sat Nov 02 2002 - 08:06:48 MST