FOM: Second order logic
John Mayberry
J.P.Mayberry at bristol.ac.uk
Sun Mar 14 07:58:33 EST 1999
In his reply to Robert Black, Steve Simpson summarises his
position by saying that (1) second order logic isn't logic at all, and
(2) second order logic hides a lot of set-theoretic difficulties.
Ad (1) ("Second order logic isn't logic at all"). This claim seems to
rest on the following fact: since the set of universally valid formulas
of 2nd order logic is not r.e., there cannot be a complete system of
proof procedures for second order logic that anyone can actually use.
No one disputes this, indeed, no one *can* dispute this: it is a
mathematical fact and can be proved. What *is* in dispute is the
conclusion that Steve Simpson draws from this fact, namely that, on its
own, it precludes our regarding 2d order logic as a genuine logic. No
doubt this position is defensible, but he has not defended it: he has
merely asserted it. In particular, he has not addressed what I think is
the central point, namely, that (a) the basic semantic definitions of
satisfiability (in a particular structure - Tarski's definition),
universal validity, logical consequence, and logical consistency are
exactly parallel in the 2nd order case to the corresponding definitions
in the 1st order case, and (b) these definitions are *logically prior*
to the proof that, in the 1st order case, the notions of universal
validity, logical consequence, and logical consistency can be
characterised in terms of formal proof.
Ad(2) ("Second order logic hides a lot of set theoretical
difficulties") It seems to me that this is just wrong. Far from hiding
set-theoretical difficulties, second order logic is precisely what
reveals the extent of those difficulties to us. Surely this is obvious
in the cases of natural number arithmetic and real analysis. In set
theory itself, the contrast between the 1st and 2nd order versions
raises acute difficulties about what axiomatic set theory is and how it
can be interpreted. There is a good discussion of these difficulties in
Shapiro's book. Kreisel has also discussed them at length in his
classic paper "Informal rigour and completeness proofs".
One further point: the Lowenheim number of second order logic is, as
the name suggests, the smallest cardinal k such that any formula of
that logic that has a model has a model of cardinality at most k. This
definition is given and its relevance to the foundations of set theory
is discussed with admirable clarity in Stuart Shapiro's book (Section
6.4, p. 147ff).
John Mayberry
School of Mathematics
University of Bristol
-----------------------------
John Mayberry
J.P.Mayberry at bristol.ac.uk
-----------------------------
More information about the FOM
mailing list