FOM: second-order logic is a myth

[Stephen G Simpson]

Robert Black 16 Mar 1999 23:36:50 writes:

 > I say that second-order logic is an essential tool for the
 > expression of mathematical theories, because only in second-order
 > logic can you have categorical theories with infinite models.
 > Steve says this is 'very odd, if not absurd'.

Wait a minute, that's not what I said.  I wasn't criticizing any
assertion of yours about second-order logic.  What I was criticizing
is your statement that first-order logic can't express certain
mathematical theories.  The statement in question was:

 > second-order logic is an essential tool for the *expression* of
 > mathematical theories.  It can do this, and first-order logic
 > can't, ...

That statement is indeed very odd, if not absurd, because it overlooks
the fact that mathematics is formalizable in ZFC.

 > The point is that the *non*-realist can give a much weaker meaning
 > to the claim that second-order arithmetic is categorical, namely
 > that each model of ZF determines a unique model of arithmetic
 > (though different models of ZF may determine different models of
 > arithmetic).

OK, good, I accept that explanation, provided by `model of
second-order arithmetic' you mean a model isomorphic to the standard
model (omega,P(omega),+,x,0,1,<,=,epsilon).

 > [I] see Steve as conceding my point, but insisting on replacing the
 > word 'second-order' by 'naive (i.e. informal)'.

That is not what I intended.  I said and meant `naive
(i.e. informal)', not `second-order'.  There is a big difference
between `naive (i.e. informal)' and `second-order'.

 > I read [Steve's] 'any set' and 'any class' as the intended range of
 > the second-order variables.

That is not what I intended.  Informal reasoning about sets and
classes is a very different thing from second-order logic.  In the
first place, second-order logic is formal, not informal.  In the
second place, when we reason informally about sets and classes in a
mathematical context, we are viewing them as just another kind of
mathematical object.  They are topic-specific and not part of any
underlying logic.

Let me try again to give you my view of how PA and ZF are motivated.

In the case of PA, the induction scheme is motivated by an informal
picture involving sets: the least element principle for arbitrary
subsets of N.  Despite this, the axioms of PA don't mention sets.
They can't, because sets aren't in the language of PA.  However, the
axioms of PA capture the idea of the least element principle for all
sets describable in the language of PA.  Thus sets play a role in
motivating PA but they are absent from the final formulation.
Similarly, in the case of ZF, the separation and replacement schemes
are motivated by an informal picture involving classes.  The axioms of
ZF don't mention classes.  They can't, because classes aren't in the
language of ZF.  However, the axioms of ZF capture the idea of
separation and replacement for all classes describable in the language
of ZF.  Thus classes play a role in motivating ZF but they are absent
from the final formulation.

Note that second-order logic (neither formal nor informal) plays no
role in the above description of how PA and ZF are motivated.

 > Frege had created second-order logic precisely for the purpose!

Wait a minute.  You say that Frege's system includes second-order
logic.  I recently had occasion to reread the Begriffschrift, and I
agree with you in a sense.  But let's be precise here.  Following
Shapiro, we need to ask, is Frege's system a species of `second-order
logic with standard semantics', or is it a species of `second-order
logic with Henkin semantics'?  I think it's more like the latter,
because Frege presents axioms and rules of inference, and the axioms
and rules that Frege presents are somewhat similar to the Henkin
axioms and rules.  In other words, according to the modern
understanding of this, Frege's system is really a first-order system!

Also, it's worth mentioning that Frege's system turned out to be
inconsistent.

 > Of course this is all at a time when no-one made any distinction
 > between first-order and second-order logic, but it's obvious that
 > it is what we now think of as the second-order notions that were
 > being used.

That is not so obvious to me.  There are difficulties of
interpretation, and the early history can be read so as to support
varying points of view.

I think it's fair to say that 1890's ideas about sets and classes are
very different from our current ones.  Then, people tended to view
sets and classes as logical notions.  Now, as a result of progress and
clarification in axiomatic set theory, we have a more sophisticated
view.  We now treat sets and classes as simply another kind of
mathematical object.  This is reflected in the distinction that we
make between the logical axioms and rules of ZF and the set-theoretic
(`non-logical') axioms of ZF.
 
 > I am a bit astonished at the following passage from Steve's reply
 > to John Mayberry:
 > 
 > >I don't think non-r.e.ness of validities *on its own* precludes
 > >so-called `second-order logic' from being a logic.  For instance, the
 > >validities of `omega-logic' and `weak-second-order logic' are also
 > >non-r.e., but unlike so-called `second-order logic' these `logics'
 > >have at least some claim to being called logics, because they are
 > >defined by certain logical axioms and rules of inference (albeit
 > >infinitary ones).

Maybe instead of `precludes' I should have said `completely
precludes'.

 > Now I may have a swollen head, but I don't have an infinite mind.
 > So I can't use infinitary rules of inference

I agree with you that infinitary rules such as the omega-rule are
highly suspect qua rules of inference.  However, some people have made
a (weak) case that rules such as the omega-rule *are* rules of
inference (I think Detlefsen was talking this way a while back) or at
least behave something like conventional rules of inference.  And this
setup is certainly more logic-like than so-called `second-order logic
with standard semantics'.  The latter has no rules at all.

The minute you write down rules for second-order logic, you are in the
realm of first-order logic (`Henkin semantics').  That's why I say
that second-order logic is a myth -- it isn't really logic, or to put
the point another way, to the extent that it *is* logic, it's
first-order logic.

 > I'm signing off from this debate for a month, because for the next
 > ten days I'm too busy, and then for three weeks I'm out of e-mail
 > contact.

OK, too bad.  I think we have made some progress toward clarifying
various issues.

-- Steve