[FOM] On "ruling out" non-standard models of first order arithmetic
Aatu Koskensilta
aatu.koskensilta at xortec.fi
Wed Nov 1 06:30:21 EST 2006
One of the perennial "puzzles" concerning certain results about first
order logic that I personally regard as totally wrongheaded has been
subject of much discussion on this list lately, namely how come we are
able to refer to the structure of natural numbers unambiguously, given
that it cannot be characterised by saying that it satisfies some set of
first order sentences. This question pops up every now and then in
different guises, in whatever forum logic, foundations or philosophy of
mathematics are discussed. For what it's worth here are my thoughts and
observations on the subject, as trivial and unoriginal as they might be.
As is obvious, much of what I say below I have shamelessly stolen from
various remarks by Torkel Franzén, both in the news and in his books.
Now, how do we come to know what the natural numbers are? Certainly by
some very complex process of indoctrination, innate cognitive
inclinations, mechanical practice, reflection, education and so forth.
Of that process I have very little to say, developmental psychology and
such like not being my forte. A plausible "rational reconstruction" can
be offered, though. The basic idea or conceptual picture we have in mind
is a never ending sequence of things obtained from 0 by repeatedly
adding 1 - perhaps pictorially in the form of appending a stroke to a
sequence of strokes - or, in formal mode should we wish to sound
professional, obtained from 0 by repeatedly applying the successor
function. For some strange reason a qualifier "for a finite number of
times" is often added to "repeatedly applying the successor function",
as if applying any operation an infinite number of times to anything
made some sense in this context. Reflecting on this - not that is
something a single individual does, but rather a long historical
development - we come to realize that the fundamental idea behind this
picture is captured by the induction principle
Whatever determinate property of natural numbers P is, if 0 has P, and
x+1 has P whenever x has P, all natural numbers have the property P
I have intentionally avoided using any logical symbolism, because this
is an informal principle, not a sentence in some first order language,
or in second order language, or what you have; it is just a piece of
ordinary language, as vague or crystal-clear as any such piece. Of
course, what applications this principle has depends on what properties
we regard as determinate - in the way "if a person has x hairs he's
bald" is not - and intelligible. In any case, it seems that properties
that are expressible using similar concepts as those used in framing the
theorems we prove, or conjectures we wonder about count. Similarly, for
any interpreted formal language we regard as meaningful, the principle
immediately yields induction for that language, which we might express
schematically, or by going second order and postulating comprehension
for the relevant language, or by any such device.
So far so good - I don't expect the above to be particularly
controversial. Now, enter the basic results about first order logic -
incompleteness, the true theory of naturals having non-isomorphic
models, Löwenheim-Skolem, pick your favourite. By any of these, the
structure of natural numbers can not be characterized by any set of
first order sentences (axiomatizable or not). The conundrum then is,
supposedly, how can we successfully and unambiguously refer to the
structure of natural numbers? Must it be that we're using second order
logic? Because all the non-standard models are non-recursive? Or perhaps
we can't, and it's all just an illusion? And so forth. Before trying to
pick the answer, let's pause for a moment and have a closer look at what
the supposed conundrum is. The obvious question to ask is why should a
mathematical result about first order logic be at all relevant to how
mathematical language works, how we refer to mathematical structures,
how we come to learn what naturals are - or what sets are, for that
matter. It appears that the picture (or a model, if you like that word
better) giving rise to the conundrum is of us somehow being presented
with an array of structures, one of which we must pick by providing some
sort of description for it, the way we might be presented with 100
chairs one of which we want to identify. If all we know of a given
structure is what first order sentences it satisfies, the mathematical
results tell us that we simply cannot pick the correct structure, expect
by chance, if all we are allowed to know about it is some set of first
order sentences it satisfies. Ok. But the picture is totally implausible
- there is simply no reason to suppose our understanding of anything,
let alone mathematical structures, is obtained or mediated that way. We
simply aren't "given" any mathematical structures, be it ones where
non-standard numbers might secretly be hiding or not. Rather, if we
consider some array of structures, it is by means of some set of
concepts, some set of mathematical ideas and ways of describing
structures. And then we can unproblematically say that the standard ones
are those for which induction holds - in the form of the informal
principle - and in particular that if induction fails for some structure
living in the mathematical world envisioned in terms of those concepts
and ideas, it is non-standard. As our only access to these structures
are as parts of the mathematical pictures or stories we come up, we
simply cannot "accidentally" think some structure is standard while, in
fact, it is not - for we can't directly pick a structure x and assert of
it that it is or is not standard, we can only refer to them using our
mathematical concepts and ideas, as parts of mathematical worlds we
fantasize, discover or invent, however that works. (Of course, one might
refer to some structure in this way of which we simply don't know
whether it is standard or not, e.g. by saying that we're considering a
structure in which the axioms of PA hold but the Goldbach conjecture
doesn't).
It is sometimes suggested that we manage to "rule out non-standard
models" by using second order logic. I'm not sure what that means
exactly; second order logic is a mathematical system, and it's not
obvious how to "use" it in any interesting sense. Of course, it's
possible to use second order logic for all sorts of purposed in the
ordinary mathematical sense, e.g. specifying which structure we're
talking about - by saying that it's the structure satisfying this or
that set of second order sentences, not in any sense relevant to the
conundrums here - and so forth. But it seems something more substantial
is meant, and I haven't really seen that spelled out anywhere, and as
Tim Chow already pointed out any worries we might have about the
naturals extend to pretty much all mathematics - without falling prey to
circularity there seems to be no way to use any piece of mathematics to
support the idea that we really do understand what we mean when we talk
about naturals, as if that needed *any* support to begin with. Now,
there is a *honest* way to question the standard picture of naturals,
which is to question its coherence, or the induction principle applied
to logically complex properties, or something on those lines. Such
questions are not, however, based on any result of mathematical logic,
but rather on conceptual considerations that might or might not lead to
interesting mathematics e.g. in the hands of competent ultra-finitists
and ultra-intuitionists. Who knows, perhaps some conception of
ultra-finitistic naturals or several systems of natural numbers proves
to be as rich as the hierarchy of large cardinals, say? Not that I'm
holding my breath...
As to first order logic and its role in foundations, I'm in total
agreement with Harvey's assertion that it is fundamental. The relevant
observation here is not that we "use" first order logic in contrast to
second order logic, but rather that the completeness theorem and a few
conceptual reflections a la Kreisel show that the first order
consequence relation correctly captures our informal notion of something
being provable on basis of something else. Thus to determine what
follows from what, what does not follow from what, what is the relation
of this sets of principles to that set of principles, and so forth,
first order logic is the tool of choice. For all sorts of mathematical
purposes higher-order logics, infinitary languages, exotic subsystems of
first order logic, all are useful and interesting, but they do not have
the same sort of a fundamental relation to our basic conception of
mathematics as first order logic. That said, most of the results about
first order logic are purely mathematical and do not necessarily have
any philosophical significance, at least with some special argument to
that effect.
Aatu Koskensilta (aatu.koskensilta at xortec.fi)
"Wovon man nicht sprechen kann, daruber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus
More information about the FOM
mailing list