FOM: second-order logic is a myth

[Robert Black]

Steve writes:
>I for one am ignorant of mereology.  If you think mereology is
>relevant to the discussion, why not describe it briefly?

I'm sure there are lots of people on the FOM list much more competent to do
this than I am, but roughly, mereology is the 'logic' of the part-whole
relation, which unlike the membership relation is transitive - parts of
parts of X are parts of X.  For any objects you take, they have a 'fusion',
the unique object of which they are all parts and which is a part of any
other object of which they are all parts.  If you were talking about space
(or spacetime) for example, regions of space would be not sets but rather
fusions of all their points (or their subregions).  By 'unrestricted'
mereology I mean when we allow ourselves to talk about arbitrary fusions -
i.e. in this case arbitrary regions of space.  This is pretty obviously
second-order logic in sheep's clothing, but with the advantage (as some see
it) of avoiding abstract objects (if regions of space are concrete but sets
abstract).  Despite being born in Australia I'm not personally frightened
by abstract objects - perhaps I've lived too long in England - but there
are quite a lot of people who think mereology important.  Most interesting
here is David Lewis's 'Mathematics is megethology', _Philosophia
Mathematica_ 1993, reprinted in Lewis's _Papers in Philosophical Logic_,
where Lewis extracts something very like ZF from a mixture of mereology and
plural quantification.  But that is beginning to take us a bit far afield
...

> > assuming that resistence to second-order logic comes from what
> > Boolos calls its 'staggering' undecidability.

>I don't think undecidability of second-order logic (staggering or
>otherwise) is the worst thing about second-order logic.  What's really
>bad about second-order logic is that it isn't a logic at all: it
>doesn't provide a model of reasoning.  See also Harvey's posting of 24
>Feb 1999 20:08:49.

But surely the reason it doesn't provide a model of reasoning is precisely
its undecidability - the fact that premises can entail a conclusion in
second-order logic without there being any earthly way of our discovering
that this is the case.  I agree with everything Harvey said in that
posting, but do you?  for example you replied to me:

> > We are agreed that operating in first-order logic is the sensible
> > way of *studying* sets, but I still think that we *conceptualize*
> > sets using second-order notions - and that for example it's our
> > acceptance of second-order separation that justifies our adoption
> > of the (weaker) first-order schema.
>
>You seem to be making a subtle distinction between `studying topic X'
>and `conceptualizing topic X'.  I don't understand this.  Our basic
>method of studying a topic is to conceptualize it.  By studying topic
>X in the framework of first-order logic, we are forced to make all our
>assumptions about X explicit.

All I'm saying is what I take Harvey to be saying in the following:

>Both first order and second order logic provide languages for the
>expression of mathematical statements.
>First order logic is, in addition, a model for reasoning. And formal
>systems based on first order logic also provide models for various kinds of
>mathematical reasoning.
>Second order logic is not itself a model for reasoning. And it cannot be
>augmented to provide models for mathematical reasoning.
>When it appears that second order logic is used as a model for reasoning,
>what is really going on is that an associated system of first order logic
>is constructed ...  a system based on first order logic which is
>associated with the
>ideas of second order logic.

Harvey will no doubt say if I've misunderstood him, but this is all
compatible with, for example, the idea that in arithmetic we have a
radically non-effective characterization of arithmetical truth - a sentence
of arithmetic is true iff entailed by the (full-blooded, with standard
sematics) second-order Peano axioms - but to *investigate* the truths of
arithemetic we operate in first order logic, initially just with
first-order PA (replacing the induction axiom by the schema 'associated'
with it [Harvey's phrase]), but then with more powerful first-order
theories - non-full-blooded 'second-order arithmetic' with Henkin
semantics, first-order ZF, first-order ZF plus high cardinal axioms, or
whatever.

> > What is built in to second-order logic is not the hierarchy
> > generated by transfinite iteration of the power set operation, but
> > rather just the principle of separation.
>
>No, this is incorrect.  A great deal of the transfinite cumulative
>hierarchy is built into second-order logic...
>
>For example, there is a simple translation of an arbitrary sentence S
>in the language of ZF set theory into a sentence S' in the language of
>pure second-order logic, such that S is true in V_Omega if and only if
>S' is valid under the `standard' semantics.  Here V_Omega is the
>cumulative hierarchy obtained by iterating the power set operation up
>to Omega, the first uncountable ordinal.  We could also replace Omega
>by much bigger ordinals, for instance the first inaccessible cardinal,
>the first measurable cardinal, etc.

Of course this is true - the 'Loewenheim number' of second-order logic is
grotesquely large - but it doesn't conflict with what I said (or at any
rate with what I meant by the admittedly vague phrase 'built in').  The
metatheory of second-order logic is indeed wildly set-theoretic, way way
over the metatheory of first-order logic for which we only need aleph_null
(though since second-order validity is at least definable in set theory,
set theoretic truth can't be reduced to second-order validity).  But in
pure second-order logic the only set whose existence one might be said to
prove is the empty set - one can't even prove that there's a set with two
members, because 'for some X for some yz (Xy & Xz & y‚z)' isn't
second-order valid.  All one is actually talking about when one is talking
in (for simplicity monadic) second-order logic is the members of the domain
of discourse and the (arbitrary) subsets of the domain.  So far as I can
see, the point you're making here really just amounts to repetition of the
point, with which I wholly agree, that second-order logic is staggeringly
undecidable, which is why we can't use it directly as a tool for proof
(though we can use it indirectly to suggest first-order axioms, such as the
induction schema).

>By the way, in your posting of 8 Mar 1999 19:14:37 you said that
>Shapiro has published a reply to his critics in the current issue of
>`Philosophia Mathematica'.  That journal is not easily available to me
>and may not be available to all FOM subscribers.  Could you please
>summarize Shapiro's reply here on FOM?

I don't mind trying to summarize George Boolos, who is alas no longer with
us to correct me, but I don't have the chutzpah to summarize Stewart, who
may well be silently following this debate!  Lean on your librarian -
there's been lots of good stuff in _Philosophia Mathematica_.

Robert

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

tel. 0115-951 5845