[FOM] Three quick comments.

Vaughan Pratt pratt at cs.stanford.edu
Tue Oct 23 19:05:08 EDT 2007

Bill Taylor wrote:
> 1:  An enquiry to Vaughn Pratt:
> I greatly enjoyed your parable of Alice, Bob, Cathy, David and Eve; however,
> their concerns seemed to be mostly generated by the conflation of...
> (a) what it means to be a theorem, or to be true;                   with
> (b) what it means for us to know a statement is a theorem, or true.
> What would be your response to this comment?

Excellent question.  My interpretation of Arnon's suggestion that 
doubters are only fooling themselves was that, at least on the face of 
it, this conflation was already present there.  Of the five, Cathy (r.e. 
vs. recursive) is the only one I see as falling clearly under (b), and 
she'd be the ideal poster logician for Arnon to start with in clarifying 
that of course he had only (a) in mind and obviously not (b), which we 
should have gleaned from between the lines.

The other four however I see as being all type (a) doubters, even Eve 
whose case might seem weakest.

David (who replaces the part of PA he doesn't use with a contradictory 
T) is surely the clearest case here: for him the more esoteric parts of 
PA are indisputably false for anyone who believes T, which David must 
since he finds T not only true but useful.  Granted he must replace 
modus ponens by rules more sensitive to proof size, but only those with 
an overly narrow conception of the scope of logic should find that 
objectionable.  What T?  Well, as a naive example say those theorems of 
PA provable with a stack of fewer than a hundred omegas together with 
the negations of all theorems of PA requiring at least a thousand 
omegas.  How could that possibly be useful?  Well, David runs a hedge 
fund and finds that betting against the conventional wisdom gives him an 
edge when the conventional wisdom includes propositions whose proofs are 
so long as to make them irrelevant to any aspect of the real world. 
This could happen even when both David and the conventional wisdom are 
computer programs betting against each other, with or without human 
traders in the same arena.

The question in Alice's case (who understands PA proofs but not any 
proof of consistency of PA) is whether she is fooling herself.  Those 
for whom the consistency of PA is obvious will also surely accept 
Cathy's concern while making the reasonable point that Cathy is merely a 
type (b) doubter and not someone who is fooling herself or anyone else. 
  They might then try to apply the type (b) label to Alice.  But whereas 
Cathy merely observes correctly that none of us can ever *know* every 
theorem, Alice's doubt concerns not the *impossibility* of our complete 
knowledge of PA but the *possibility* of inconsistency of PA, a fact 
about PA itself rather than our knowledge about its theorems and hence a 
type (a) doubt.  Saying that Alice is merely fooling herself is as 
unreasonable as rich people telling homeless people that they are just 
fooling themselves about their inability to house themselves.  But even 
without this analogy there remains the nice question that has been 
debated elsewhere on this list, as to whether one is entitled to one's 
doubts about proofs inaccessible to the doubter that have nonetheless 
received the community's imprimatur.  The heart of this question would 
seem to be, when to trust the conventional wisdom and when to question 
it like Descartes.  As long as the conventional wisdom includes a 
nucleus of clear-thinking honest judges one should presumably trust it, 
but who judges the judges?  This is not an easy question by any means, 
and I wouldn't want to accuse Alice outright of being guilty of merely 
"fooling herself."  Alice is an *honest* type (a) doubter.

Bob adapts the hill-of-beans paradox to argue that our unquestioning 
acceptance of the whole of PA is predicated on the same faulty logic by 
which one proves by induction that there is no hill of beans.  We accept 
the axioms of PA as infallible, and likewise the proof rules, from which 
follows that all of PA is infallible.  Bob argues that those who believe 
in the infallibility of all of PA are treating fallibility as an 
all-or-nothing thing when to Bob even the very meaning of sufficiently 
esoteric regions of PA is up for grabs.  David takes Bob's argument one 
step further by constructively showing how to make actual money out of 
that lack of any real meaning, but even without David's constructive 
demonstration the hill-of-beans paradox already reveals a weakness in 
the dogma that all of PA is equally infallible.  Wigner's "unreasonable 
efficacy of mathematics" is all very well for theorems with short 
proofs, says Bob, but why should it obtain equally for those theorems 
with arbitrarily long proofs, whose truth or falsity may be of no 
relevance to anyone but the most extreme idealists?

Eve (who was bothered by the "tangled web" of ordinals below epsilon_0) 
argues to the same conclusion as Bob, but whereas Bob argues by reductio 
ad absurdum Eve's argument is a more constructive objection to the 
demonstrably chaotic complexity of PA proofs.  The difference is rather 
like the difference between Cantor's constructive theorem that 2^X is 
bigger than X and Russell's paradoxical set of all sets not members of 
themselves.  Cantor's theorem and Eve's complaint are like the frog in 
the gradually heated pot---somehow we're able to tolerate the 
never-ending increase so long as we're not exposed to all of it at once. 
  Russell and Bob just drop their frog into boiling water and it gets 
the memo right away.  Either way the frog is eventually boiled, but the 
slow-boiled frog is tougher to digest.

Vaughan Pratt

More information about the FOM mailing list