[FOM] Do the integers exist?

[Jack]

Do the integers exist?
The unknowability of arithmetic consistency.

by Jack Schwartz
Courant Institute of Mathematical Sciences
New York University


It is an article of faith for most mathematicians that Peano's axioms
for arithmetic are consistent, perhaps because (in a kind of 'Platonist'
view) they
simply state truths concerning a set of objects, the integers, that
somehow exist, even though they constitute an infinite collection. A
well-known (but
extreme) statement of this point of view is Kurt Goedel's 1961 'The
modern development of the foundations of mathematics in the light of
philosophy',
see his Collected Works, Volume III, Oxford University Press, 1981.
Taken in an extreme form, the opposed 'nominalist' position holds that,
since we
can have no direct physical experience with any such infinite
collection, or even with its remoter members, the most that can be said
is that extensive
work with these axioms, including studies of their relationship to other
axiom families considered likely to be consistent, demonstrates their
consistency
experimentally. If this latter position is accepted wholeheartedly, one
ought to ask how thorough the search for an inconsistency implicit in
this work
really is, how it can be made more thorough, and how thorough a search
might be possible in the best of cases. This paper will argue that truly

comprehensive search for an inconsistency in any set of axioms is
impossible. This will be done by demonstrating that an assumption
distinctly weaker
than the assumption of absolute consistency accounts for all the logical
and practical experience with integers that we have had or can have.

Either of two kinds of work with integers, reasoning or computation,
might lead to detection of an inconsistency in Peano's axioms. We might
find such
an inconsistency either (1) by some chain of reasoning from the Peano
axioms that proves a pair of statements which directly negate each
other, or (2)
by running a computer program of which some property (e.g. non-halting)
has been proved using Peano's axioms, and finding that it fails to have
this
property (e.g. halts.)

In considering case (1), it is useful to measure the complexity of
proofs in a slightly unusual way. A proof is simply a set of statements
S, each of
which is either an axiom, a definition, or a consequence of some finite
collection of prior statements (S_1, S_2,... S_n) by some rule of
inference. Call
the statements (S_1, S_2,... S_n) needed to prove each step S its basis.
As a proof, possibly a very long one, develops, one must retain a
statement S
appearing in it only as long as S is needed as the basis for some
subsequent inference step. Once S has been used in the last such step,
it can be thrown
away. In practice this means that to prove even a relatively 'advanced'
theorem T, one need only retain the chain of definitions and prior
theorems leading
up to T, plus the statements belonging to the proof of whatever theorem
T' in the chain of reasoning is currently being demonstrated. Once a
theorem
has been proved, the statements used to prove it can be thrown away. The
proof can therefore be conducted without ever having to remember more
than
some amount A of intermediate text at any one point. For each theorem T,
take the proof which minimizes this A, and call the minimum of all such
A the
memory size Mem_size(T) of T. In this sense, we can speak of theorems of
memory size 5 pages, 10 pages, 20 pages, etc.

The author's work with a proof verifier indicates that Mem_size(T) is
not likely to be very large for any theorem T in the published
mathematical
literature. For example, statement and proof of the Cauchy integral
theorem should require retention (at any moment) of no more than 20
pages of
theorems and definitions, and no proof longer than 600 lines, i.e. 10
pages, should be needed. Thus we estimate the memory size of this
theorem to be
no more than 30 pages, and probably a good deal less. This should be
true of any theorem in the mathematical literature. So it is not
unreasonable to
assume that no theorem of memory size greater than, let us say, 100
pages has ever been published, or even worked out in detail by its
discoverer.

We can therefore say that all our mathematical experience to date is
consistent with the assumption that the Peano axioms are inconsistent,
but that the
size of the minimal inconsistency is more than, let us say, 100 pages.
If this is the case, then mathematicians reasoning from such axioms will
never
encounter an inconsistency, since an infeasibly long and intricate proof
would be needed to establish it. Shorter proofs, which is to say all the
proofs
that have thus far appeared or are likely to appear in the mathematical
literature, could never do so. It is easily understood that in this
assumed situation
the community of mathematicians, noting that the language which they
have been able to use confidently and consistently for centuries, might
grow to
assume that the objects assumed in the language had some real (though
necessarily abstract) existence, and that the axioms were consistent
because at
bottom they simply asserted truths about these objects.

How, if at all, can we tell that we do not find ourselves in this
assumed situation?

Note that there must certainly exist theorems of arbitrarily large
memory size. For it is a well-known consequence of the unsolvability of
the decision
problem that the size of a theorem's proof cannot be bounded by any
recursive function of the size of its statement. On the other hand, if
the memory
size Mem_size(T) of a theorem is B (in bits), the number of
configurations that can enter into any of its inferences is at most 2^B,
and so (if for
convenience we assume that the inference rule to be used at each step
and the location of the statements referenced is held as part of this
configuration)
at most 2^B distinct proof steps are possible within memory size B. But
in a non-redundant proof the same configuration will never recur twice,
since it
contains all the information carried forward in the course of the proof,
i.e. between two occurrences of the same configuration no progress will
have
been made. Thus the maximum length of the minimal proof of a theorem T
of memory size Mem_size(T) is at most 2^Mem_size(T), from which it
follows that Mem_size(T) cannot be bounded by any recursive function of
the size of the statement of T. This leaves open the possibility that
the
memory size of even a very small provable statement, for example
'false', should be quite large, which is the possibility considered
above.

It would seem therefore that the collective intellectual work of
mathematicians cannot be regarded as constituting a comprehensive search
for an
inconsistency in Peano's axioms. Indeed, we can characterize whatever
such search there has been as rather causal. In the first place, the
assumption that
something does not exist is poor psychological ground for mounting an
extensive and challenging search for that thing. Secondly we can be
quite
certain that only a microscopic part of the enormous space of proofs of
memory size (let us say) 10 pages has till now been explored.

Note also that prior discussion of this point may often have involved an
implicit assumption that the proof of a contradiction, if one exists,
should be
relatively short. The best-known previous example of this sort of thing
is Russell's well-known observation that Frege's initial axiomatization
of set
theory was inconsistent. Concerning this the Stanford Encyclopedia of
Philosophy website remarks: "Russell wrote to Gottlob Frege  with news
of his
paradox on June 16, 1902. The paradox was of significance to Frege's
logical work since, in effect, it showed that the axioms Frege was using
to
formalize his logic were inconsistent...Immediately appreciating the
difficulty the paradox posed, Frege added to the Grundgesetze a hastily
composed
appendix discussing Russell's discovery. In the appendix Frege observes
that the consequences of Russell's paradox are not immediately clear.
For
example, 'Is it always permissible to speak of the extension of a
concept, of a class? And if not, how do we recognize the exceptional
cases? Can we
always infer from the extension of one concept's coinciding with that of
a second, that every object which falls under the first concept also
falls under
the second? These are the questions,' Frege notes, 'raised by Mr
Russell's communication.'  Because of these worries, Frege eventually
felt forced to
abandon many of his views about logic and mathematics." In this
particular case it would seem that the restrictions on set formation
embodied in
standard Zermelo-Fraenkel set theory remove the contradiction that
troubled Frege. But Russell's proof of a contradiction is very short.
Can we be
certain that a system modification which removes this very direct,
relatively obvious contradiction removes all others, no matter how
intricate their proof
might be?

Could the failure of computational rather than deductive search for an
inconsistency yield stronger evidence that the Peano axioms are
consistent? To
find an inconsistency in this way, execution of a computer program which
has been proved correct but then fails to behave as it provably must
would
reveal a contradiction. However it is easy to see that a strengthened
version of the supposition advanced above can also rule out
comprehensive
discovery of such cases. Execution of a computer program, if conducted
in perfect physical agreement with a binary model of a computer of known

instruction set, can be viewed as mechanical evaluation of some
recursive function f (the computer code) for some integer value n (the
input), followed
by evaluation of some recursive predicate P for which the value P(f(n))
is provably 'true', i.e. (FORALL n | P(f(n))) can be proved. Discovery
of any
actual integer n_0 for which P(f(n_0)) is then actually 'false' then
constitutes an inconsistency found by computation. A simple example
might for
example  be discovery of an integer (perhaps one having a binary
representation more than 30 pages long) for which n^2 mod 11 evaluated
to 10. This
is a bit different from the situation considered above, since such a
code, together with its input, can easily be longer than the memory size
of the largest
feasible proof. But in fact few computer programs have actually been
proved correct, and fewer still have then be tested at all
comprehensively.
Moreover if we extend our preceding supposition to cover texts too large
to be held in the physical memory of any computer, the skeptical
argument
given previously still applies.

Note that consideration of extreme cases which might behave differently
from the way in which ordinary experience suggests is commonplace in
physics, even though heretical in mathematics. No one would argue that
the complete absence from daily experience of black holes means that
none
exist, or that the vanishingly small effect of relativistic laws on
objects moving at ordinary speeds means that such effects are
fictitious.

We now turn to examination of a very distinguished view directly opposed
to that advanced above, namely the 'Realist; or 'Platonist' view
maintained by
Goedel in the article already cited. Goedel begins by arranging
foundational opinions in a roughly linear arrangement running from
extreme versions of
what we have called the 'Platonist' viewpoint to various more or less
radical kinds of nominalism: "I believe that the most fruitful principle
for gaining an
overall view of the possible world-views will be to divide them up
according to the degree and the manner of their affinity to or,
respectively, turning
away from metaphysics (or religion). In this way we immediately obtain a
division into two groups: scepticism, materialism and positivism stand
on one
side, spiritualism, idealism and theology on the other... the
development of philosophy since the Renaissance has by and large gone
from right to left ...
Particularly in physics, this development has reached a peak in our own
time, in that, to a large extent, the possibility of knowledge of the
objectivisable
states of affairs is denied, and it is asserted that we must be content
to predict results of observations. This is really the end of all
theoretical science in
the usual sense (although this predicting can be completely sufficient
for practical purposes such as making television sets or atom
bombs)...It would
truly be a miracle if this (I would like to say rabid) development had
not also begun to make itself felt in the conception of mathematics." In
these
remarks Goedel clearly positions himself somewhere toward the Platonist
end of his scale, in opposition to the presumably misguided 'Zeitgeist',
noting
that "...mathematics, by its nature as an a priori science, always has,
in and of itself, an inclination toward the right, and, for this reason,
has long
withstood the spirit of the time [Zeitgeist] that has ruled since the
Renaissance
" He views the skeptical attitude toward the actual
existence of even
transfinite sets as an instance of this same lamentable empiricism:
"...Finally
 its hour struck: in particular, it was the antinomies of
set theory,
contradictions that allegedly appeared within mathematics, whose
significance was exaggerated by sceptics and empiricists and which were
employed as
a pretext for the leftward upheaval. I say "allegedly" and "exaggerated"
because, in the first place, these contradictions did not appear within
mathematics but near its outermost boundary toward philosophy, and
secondly, they have been resolved in a manner that is completely
satisfactory...Such arguments are, however, of no use against the spirit
of the time, and so ... many or most mathematicians denied that
mathematics, as it
had developed previously, represents a system of truths; rather, they
acknowledged this only for a part of mathematics (larger or smaller,
according to
their temperament) and retained the rest at best in a hypothetical sense
namely, one in which the theory properly asserts only that from certain
assumptions (not themselves to be justified), we can justifiably draw
certain conclusions. They thereby flattered themselves that everything
essential had
really been retained..."

"Now one may view the whole development of empirical science as a
systematic and conscious extension of what the child does when it
develops in the
first direction. The success of this procedure is indeed astonishing and
far greater than one would expect a priori: after all, it leads to the
entire
technological development of recent times...it turns out that in the
systematic establishment of the axioms of mathematics, new axioms, which
do not
follow by formal logic from those previously established, again and
again become evident. It is not at all excluded by the negative results
mentioned
earlier that nevertheless every clearly posed mathematical yes-or-no
question is solvable in this way..."

Though occasionally obscure, these remarks seem to rely on the idea that
human reason is and of itself can serve as an engine capable of
establishing at
least mathematical truths definitively, and that these truths can be
recognized, at least by judges having Goedel's level of acuity, by the
feeling that they
are 'completely satisfactory'. But this traditional view separates
reason from the biological limitations of the real brains which actually
support it. Many
observations, of which the figure found at
http://www.essex.ac.uk/psychology/visual/cafewall.html
is an amusing but trenchant example, show the insupportability of this
position. On viewing this figure, the
visual brain, arguably a part of the human mind which is particularly
well adapted to reality, sees it wrongly. A definite and stable
perception of slant is
experienced. But if a straight edge is held against the apparently
slanted lines in the figure, it is readily seen that they are perfectly
horizontal. This
misperception seems to be common to all, or at any rate the great
majority of the human population, and would seem to be a genetically
specified fault in
the human visual system. If vision can misbehave in this way, it is hard
to believe that refined judgments concerning infinite cardinalities, or
for that
matter very large integers, are to be trusted.