[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:
OBJECTIVELY,
> 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