[FOM] Certainty in mathematical proofs, part 2

Vaughan Pratt pratt at cs.stanford.edu
Sun Oct 21 23:26:49 EDT 2007

Arnon Avron wrote:
> everything that assumes the existence without any restriction
> of P(R) cannot be taken as absolutely certain, while everything
> provable in PA *is* absolutely certain (I simply  find it 
> hard to believe someone who denies the latter. I think
> that s/he is fooling herself/himself).

Arnon, here are five people who according to you are fooling themselves.

Alice is a pretty good mathematician who is homeless on account of her 
inability to persuade anyone to hire her.  She can follow every proof of 
PA but has been unable thus far to follow any proof of its consistency 
and is therefore uncertain as to the soundness of the PA proofs she can 
follow.  Those living in fine homes tell her she is just fooling herself 
about her ability to find housing, while those who have no trouble 
seeing how to prove the consistency of PA tell her that she is just 
fooling herself about her doubts about PA.  She is not persuaded by 
either.  She does however accept that if PA is consistent then so is ZF, 
which she can clearly see is merely an article of faith for everyone and 
not a mathematical insight that she needs to feel bad about not 
possessing---the rich may have a better home than the poor but not a 
better god.

Bob is on top of the consistency of PA, and moreover has no complaints 
about short PA proofs, but sees long ones as a can of worms.   Bob's 
boss tells him that every sentence in the language of PA is either a 
theorem of PA or not.  In reply Bob makes the comparison to a hill of 
beans: take away one bean and it is still a hill of beans.  One bean is 
not a hill of beans, therefore by induction no finite set of beans can 
be a hill of beans.  Likewise a one-line proof is not a can of worms, 
and modus ponens does not create a can of worms from a non-can, 
therefore by induction no finite proof can be a can of worms.  Here 
boss, let me show you a can of worms, says Bob, I have grave doubts 
about this thousand-page proof.

Cathy points out that PA is r.e. but not recursive: however well-defined 
PA might be, it is inaccessible to us mere mortals, who must remain 
forever uncertain about infinitely much of it.  Maybe someone's god can 
be absolutely certain of every theorem in PA, but you can't, and I 
can't, says Cathy.

David finds PA very useful in his work, but he also depends on another 
theory T that is consistent with the part of PA he needs but not with 
all of PA.  In particular T contradicts some of those conclusions of PA 
whose shortest proofs are coded with ordinals greater than a stack of a 
hundred omegas (not as generous a bound as intuition about transfinite 
ordinals might suggest given its representability by a finite tree with 
only 101 vertices).  David reconciles T with the part of PA he needs by 
replacing plain modus ponens with more nuanced rules of inference that 
avoid what for David is the problematic region of PA, which as far as he 
is concerned is not merely uncertain but just plain false in parts.

Eve has her doubts about the structure of PA proofs.  She grants that 
each individual proof, when coded as a finite rooted tree representing 
an ordinal less than epsilon_0, is an easily grasped concept.  Where 
doubts set in for her is in the well-ordering of those proofs, which she 
acknowledges as being merely a linear order while nevertheless 
perceiving it as an obscurely tangled web of those trees, however easily 
grasped the individual trees might be.  To Eve, tangled webs are not 
conducive even to confidence, let alone certainty.

Alice, Bob, Cathy, David, and Eve have no doubts about their doubts, in 
fact they have teamed up to teach the five principles of Peano 
uncertainty to the world.  How would you go about saving the world from 
these charlatans who are fooling everyone including themselves?

Vaughan Pratt

More information about the FOM mailing list