[FOM] Ultrafinitist notion of "open problem"
Timothy Y. Chow
tchow at alum.mit.edu
Mon May 25 18:17:19 EDT 2015
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
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.
More information about the FOM