FOM: second-order logic is a myth

[Robert Black]

What I'm arguing for is the tenability (not even the truth, though I'm
tempted to think it's true) of a certain realist approach to mathematics
which takes second-order logic seriously for the expression of mathematical
theories.  (I say 'realist' rather than 'platonist' because I think the key
issue is one of whether statements like the continuum hypothesis should be
regarded as having objective unknown truth-values, and the word 'platonist'
tends to lead off into discussions about the status of abstract objects, or
- much worse - associations with mystical realms of intelligibilia.)

To show this, one has to show how the various technical results of logic
and set theory are to be accommodated from this point of view.  So I'm
asking Steve to suspend disbelief and see how things are going to then look.

>From this point of view, second-order logic is an essential tool for the
*expression* of mathematical theories.  It can do this, and first-order
logic can't, because only in second-order logic can you have categorical
theories with infinite models.  (And note here that for the realist, it's
not just that you can prove in first-order ZF that, say, second-order
arithmetic is categorical, but that it really *is* categorical - i.e.
determines a unique model, not just one for each model of first-order ZF.)
On the other hand, second-order logic is (and here I agree with Steve)
useless for the business of nuts-and-bolts *deduction*, because
completeness fails - and fails radically.

In *that* sense, I agree that second-order logic is, in Steve's words, 'not
a model of reasoning: it doesn't provide any method for moving from
premises to conclusions'.  I do think, however (and I'm a little surprised
that Steve hasn't taken me up on this one) that it is active in providing
the premises from which we then reason in first-order logic.  For example,
I think the intuitive justification of the induction schema in first-order
PA is the induction axiom of second-order PA, and I think the intuitive
justification of the separation schema in first-order ZF is given by the
second-order separation axiom.

Steve takes issue with my easy association of 'undecidability' with
undiscoverability. I'd have thought that what I meant here is pretty clear,
but let me spell it out.  The set of (Goedel numbers of) validities of
first-order logic is (not of course recursive but) recursively enumerable.
Now (assuming Steve will let me help myself to Church's thesis) that simply
*is* the claim that there is a formal system in which all first-order
validities are discoverable.  But the set of (Goedel numbers of) validities
in second-order logic is not only not r.e., it's not even arithmetic, nor
for any n definable in nth-order arithmetic, nor ... (I'm sure Steve is in
a better position than I am to continue this list).  In other words there's
not only a gap between validity and proof, there's a very large gap. So
even with quite relaxed requirements on a 'model of reasoning'.
second-order logic is not going to be such.  Here I expect no disagreement
whatever.

Now let's talk about set theory.  Second-order ZF is quasi-categorical,
that is to say, it doesn't fix the height of the universe, but it does fix
the width all the way up.  More precisely, given any two models of
second-order ZF, one is isomorphic to an initial segment of the other.
>From the realist point of view, that is because at each level of the
hierarchy, second-order separation immediately inserts 'every' set which
'ought' to be there, a task which the first-order schema is radically
incapable of.  So, for example, second-order logic 'decides' the continuum
hypothesis.  (But of course I agree with Harvey that it would be idiotic to
conclude from this that the independence results for first-order ZF are
insignificant, because the fact that CH is 'decided' in second-order ZF is
no help at all in telling whether it's true or not.)

Furthermore, second-order theories are capable of insisting that their
models be very large.  The 'Loewenheim number' (I thought this was a
standard expression) is a measure of how large.  More precisely, the
Loewenheim number of L is the smallest cardinal such that any sentence of L
which has a model at all has a model of at most that cardinality.  The
Loewenheim number of first-order logic is of course aleph_null whereas the
Loewenheim number of second-order logic is stratospheric (though at least
it does exist!).

Unless I'm misunderstanding something (I'm a philosopher, not a
set-theorist), it's the combination of the quasicategoricity of
second-order ZF with the high Loewenheim number of second-order logic which
leads to the results Steve quotes about how there is a sentence of
second-order logic which is valid iff [put in your favourite
set-theoretical claim restricted to V_something-or-other].  This means that
the *meta-*theory of second-order logic makes enormous demands on set
theory.  Because of the Skolem-Loewenheim theorem, the metatheory of
first-order logic makes much, much weaker demands.

Now Steve seems to want to argue that because the *meta-*theory of
second-order logic makes heavy demands on set theory, second-order logic is
strong set theory in disguise. Well, you can say this if you like, but then
be consistent: the metatheory of first-order logic makes much weaker
demands on set theory, so first-order logic is weak set theory in disguise.
That's roughly what John Mayberry has been saying, and it would be OK with
me, but I didn't think Steve wanted to say this.

Robert

Robert Black
Dept of Philosophy
University of Nottingham
Nottingham NG7 2RD

tel. 0115-951 5845