2005-06-04

Who knows? Maybe nonstandard arithmetic is just unavoidable

Gödel's Proof is usually taken to mean that Peano arithmetic is radically incomplete; that one has the choice of adding one of two new axioms, G and ~G, and when that is done, one can construct a new statement G' and then has the choice of adding G' or ~G', and so on forever, splitting arithmetic into an infinite tree of theories.

Assuming G, G', G'', ... produces standard arithmetic; assuming one or more of ~G, ~G', ~G'' ... produces various kinds of nonstandard arithmetic, in which the natural numbers are supplemented by entirely novel nonstandard numbers. (The reciprocals of nonstandard numbers are the infinitesimals of nonstandard analysis.)

But although Gödel showed by a metamathematical argument that there can be no proof of G within Peano arithmetic, he did not show that there is no finite proof of ~G. Which means that in principle there might be one. And that would mean that there is only one kind of arithmetic, and that nonstandard numbers exist, period. Shocking.

Here's a proof sketch:

Let x be the Gödel number of a Peano-arithmetic (PA) proof, and y the Gödel number of a (purported) PA theorem. Let PRF(x, y) be true iff y is the Gödel number of the theorem proved by the proof whose Gödel number is x.

Then ∃y PRF(x, y) means (meta-mathematically) that x has a PA proof. G then is the formula that asserts (again, meta-mathematically) that "G has no PA proof"; contrariwise, ~G asserts "G has a PA proof".

Assume that G has a proof whose Gödel number is k. Then PRF(G, k) is true, contrary to G's assertion that G has no proof. In that case, given the proof of G, we have found a proof of ~G as well, so PA is inconsistent.

But the alternative, that there is a proof of ~G, is not symmetrical with the preceding case. If there is a proof of ~G, then there is a proof of ∃y PRF(g, y), but it does not follow that if we attempt to prove for each k (a natural number) a proof of ~PRF(G, k), that we will necessarily find a proof of G. We might not.

The result is very bizarre, but not necessarily a direct contradiction; "for each k, there is a proof of ~PRF(G, k)" does not amount to a proof of ∀y PRF(G, y). This is callled ω-inconsistency, and although semantically related to ordinary inconsistency ("G and ~G"), it's not the same.

Assuming G has a proof, then PA is inconsistent, but assuming ~G has a proof, then PA is either inconsistent or ω-inconsistent, we don't know which.

Since we have no proof of G (and can't have one), we can assume ~G as an axiom. Since we have no proof of ~G either, we can assume G as an axiom. However, if a proof for ~G were actually found, then PA would be inescapably ω-inconsistent.

~G (which says "G has a proof") is consistent with PA, but only at the cost of making PA + ~G ω-inconsistent: ∃y PRF(y) is true, but each of PRF(G, k) is false for each natural number k. It must therefore be true of something other than the natural numbers. Hence, theories which postulate ~G necessarily have nonstandard numbers.

If there did turn out to be a proof of G in PA itself, though, then PA would be inescapably ω-inconsistent, and nonstandard numbers would exist in every PA-compatible number theory.

I am leaning here on Podnieks, who provides a lot more detail.

1 comment:

Anonymous said...

I know this is an old entry for you (I just came across it in a Google search), but I was quite confused by your claim here. You say, "But although Gödel showed by a metamathematical argument that there can be no proof of G within Peano arithmetic, he did not show that there is no finite proof of ~G. Which means that in principle there might be one."

Assume for a moment that PA is indeed consistent. If PA proves ~G, then PA+G cannot possibly be consistent (since ~G and G would both be true in PA+G). This contradicts Gödel's First Incompleteness Theorem, which shows that the consistency of PA implies the consistency of PA+G.

So PA cannot prove ~G. Am I missing something?