FOM: second-order logic is a myth

[Stephen G Simpson]

Robert Black 11 Mar 1999 14:08:31 writes:

 > 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.

Why do you call this `undecidability'?  This is not standard
terminology.  Normally and standardly, a theory T (i.e. a set of
formulas closed under logical consequence) is said to be undecidable
if its corrsponding set of G"odel numbers is non-recursive, i.e.,
non-computable.  By extension one could say that T is `staggeringly
undecidable' if the Turing degree (i.e., degree of unsolvability) of
the corresponding set of G"odel numbers is very high.  But this is a
different matter from the lack of discoverability that you mention.

Anyway, putting aside the terminological confusion, my point was as
follows: Second-order logic isn't properly called logic, because it's
not a model of reasoning: it doesn't provide any method for moving
from premises to conclusions.

[ Throughout this posting, when I say second-order logic, I am
referring to second-order logic with `standard' rather than Henkin
semantics.  My remarks do not apply at all to second-order logic with
Henkin semantics, which is really a system of first-order logic. ]

 > I agree with everything Harvey said in that posting, but do you?

Yes.

 > >No, this is incorrect.  A great deal of the transfinite cumulative
 > >hierarchy is built into second-order logic ...
 ...
 > Of course this is true - the 'Loewenheim number' of second-order
 > logic is grotesquely large ...

I didn't mention the Loewenheim number, whatever that may be, and I
didn't intend to refer to it at all.  My point was that all facts
about the transfinite cumulative hierarchy up to very high levels
(e.g., the first measurable cardinal, if it exists) are built into
second-order logic.  This is part of why second-order logic is so bad:
it conceals massive set-theoretic difficulties.

 > 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.

Does this have any bearing on my point?

 > 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,

No, I am saying more than that.  I am saying (1) second-order logic
isn't a logic at all, (2) second-order logic hides a lot of
set-theoretic difficulties.

 > Lean on your librarian - there's been lots of good stuff in
 > _Philosophia Mathematica_.

The library that I normally use has Philosophia Mathematica up to
date, but the library that I have access to this semester discontinued
it in the 1980's.  I would really appreciate a summary of Shapiro's
reply to his critics.

-- Steve