[FOM] Ultrafinitist notion of "open problem"

[Timothy Y. Chow]

The late Edward Nelson regarded the consistency of PA as being an "open 
problem."  I have been trying to understand exactly what he meant by this 
claim.  Unfortunately, of course, Nelson is no longer with us.  However, 
since there are others (perhaps even some readers of FOM) who seem to 
agree with Nelson on this point, maybe they can address some of the points 
I make below, if not on Nelson's behalf then from their own point of view.
  I will use "Nelson" hereafter to refer synecdochially to those whose 
beliefs are sufficiently similar to Nelson's (or what I think are 
Nelson's).

To begin with, it is important to distinguish between a mathematical 
statement S and the statement

    (1) There exists a proof of "S" in the formal system T

where "S" is some formal counterpart of S.  As I understand it, when 
someone actually exhibits a formal proof of "S" in T (or at least gives a 
convincing argument that we could actually instantiate such a proof 
physically in some way), then Nelson is happy to affirm (1).  So in 
particular, Nelson would gladly affirm

    (2) There exists a proof of Con(PA) in ZFC

On the other hand, Nelson would not affirm that PA is consistent.

For some S, Nelson might not even regard S as directly meaningful.  An 
example that comes to mind is S = CH, the continuum hypothesis.  However, 
"PA is consistent" looks like the sort of mathematical statement that 
Nelson seems to regard as directly meaningful, even if not (yet) proved or 
disproved.  Certainly, if someone were to exhibit an explicit 
contradiction in PA, then surely Nelson would affirm

    (3) There exists a proof of "0=1" in PA

as not only meaningful but true.  But does this necessarily mean that 
Nelson regards "PA is consistent" as directly meaningful?

Naively, one might assume that "PA is consistent" can be obtained from (3) 
by simple negation, viz.,

    (4) There does not exist a proof of "0=1" in PA

However, there are at least two ways to interpret (4).  One way is what we 
might call the "Platonic" interpretation, which is that in the eternally 
existing Platonic world that contains all possible theorems of PA, the 
statement "0=1" is nowhere to be found.  But another interpretation is the 
prosaic observation that at the moment, the mathematical community lacks 
any concrete proof of "0=1" from the axioms of PA.

Given Nelson's distaste for Platonism, I hesitate to ascribe the former 
interpretation to him, even though that is what I myself instinctively 
think of when I hear the statement, "PA is consistent."  On the other 
hand, the prosaic interpretation does not seem like a plausible 
understanding of what Nelson means by "PA is consistent" either.  In 
particular, the prosaic interpretation is not the sort of thing that 
anyone would normally call an "open problem."  All I have to do to settle 
*this* question is make a few inquiries to convince myself that nobody 
currently has a proof of "0=1" in PA.

This is the point where I start to fumble around a bit.  Maybe by "PA is 
consistent" Nelson means something like this?

    (5) The mathematical community will never find a proof of "0=1"
        from the axioms of PA.

This seems closer, although there is an obvious problem: (5) depends 
heavily on the idiosyncrasies of the mathematical community.  Maybe we're 
all just too dumb and a smarter group of people would find a PA-proof of 
"0=1" in the twinkling of an eye.  Still, (5) seems closer than (4).

A tempting possibility is the following: Perhaps there is some specific 
formal system T with the property that if we were to find a proof of 
Con(PA) in T, then Nelson would affirm that PA is consistent, and (a 
fortiori?) affirm (5) as well.  This wouldn't tell us exactly what "PA is 
consistent" *means* (to Nelson), but it would at least give us sufficient 
conditions for affirming it.  Some kind of philosophical leap would have 
to be made here, since it's not immediately clear why the existence of 
some kind of finite object (namely, a proof of Con(PA) in T) would imply 
some kind of physical claim such as (5), but this is the kind of leap that 
classical mathematicians are accustomed to making all the time anyway, so 
why we should deny Nelson the right to make a similar leap?

On this reading, "the consistency of PA is an open problem" could be 
approximated as, "there is currently no [known] proof or disproof of 
Con(PA) in T," where T is some specific formal system (that, we may 
assume, is at least strong enough to formalize explicit derivations of 
"0=1" from the axioms of PA).

If we accept this gloss, then the next question I have is, is the 
consistency of PA an open problem of the type that can be settled only in 
one direction?  That is, an explicit proof of "0=1" from the axioms of PA 
would certainly settle the consistency of PA negatively, but perhaps there 
is nothing that would convince Nelson that PA is consistent?

Certainly if T is taken to be some standard candidate such as PRA, then we 
(as classical mathematicians) have Goedelian reasons to believe that 
nobody will ever prove Con(PA) from T.  I'm wondering, though, whether 
there are more fundamental reasons why many, perhaps most, "open problems" 
can, for Nelson, only be settled in one direction.

Consider the following statement:

   There exists a positive integer s such that for all positive integers n,
   there exists a two-coloring of the edges of the complete graph K_n with
   no monochromatic K_s.

Is this an open problem?  Classically, of course, the answer is "no, this 
is not an open problem."  Ramsey's theorem implies that there is no such 
positive integer s.  This theorem can be formalized in weak systems.  But 
is the existence of a formal proof of Ramsey's theorem in such a weak 
system enough to convince Nelson that it is "true"?  The theorem asserts 
the *nonexistence* of an integer s with certain properties, much like the 
consistency of PA asserts the nonexistence of a certain integer with 
certain properties, so it is not directly witnessed by a specific feasible 
object.  Furthermore, we know (as classical mathematicians, at least) that 
there is an exponential lower bound on the Ramsey number R(s,s).  Since 
exponentiating a feasible integer does not always produce a feasible 
integer, Nelson has expressed some skepticism about classical assumptions 
about exponentiation.  So the possibility apparently arises that for 
Nelson, not only is the consistency of PA an open problem, but so also are 
plenty of ordinary mathematical statements such as Ramsey's theorem.

Perhaps Nelson would accept some form of bounded arithmetic for the base 
theory T.  Even then, though, I wonder if *arbitrary polynomials* grow too 
fast for Nelson's comfort.

Tim