[FOM] On "ruling out" non-standard models of first order arithmetic

[Aatu Koskensilta]

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