[FOM] Are the proofs of con(PA) circular?
Daniel Mehkeri
dmehkeri at gmail.com
Thu May 19 22:34:18 EDT 2011
Timothy Chow writes:
> If we offer up Gentzen's proof, we have to explain what epsilon-0
> induction is. This is even less familiar. Is it going to give the
> mathematician warm fuzzies? Probably not. The validity of epsilon-0
> induction is not likely to seem more "self-evident" than the existence
> of N.
Well, here's why I think it could do just that.
The point that statements like "Gentzen proved induction over omega
using induction over epsilon_0" ignore is that we don't need full
epsilon-0 induction, just a restricted form of it. In fact it can be
stated without induction, or talk of well-foundedness, ordinals, or
arbitrary sequences.
Specifically, to prove the 1-consistency of PA, it is sufficient to
believe that, for some structure of order type epsilon-0 (and see what
Vaughan Pratt has written about these), every elementary recursive
descending sequence terminates.
I say that's a hugely important distinction. Consider:
(1) If a certain collection contains 0, and for each n it contains, it
also contains n+1, then that collection contains all the natural numbers.
Even though this is usually called the "second-order" induction axiom,
it actually doesn't imply the first-order induction axiom scheme of PA
or HA. You also need something like:
(2) every predicate of first-order arithmetic actually defines a
coherent collection.
If what you are in doubt of is (2), then Gentzen's proof could be
immensely valuable. In fact it can be proved without even propositional
logic. (Wikipedia's article on PRA discusses Goodstein's logic-free
system. Add to this system function definition by descent recursion.)
Daniel Mehkeri
More information about the FOM
mailing list