FOM: second-order logic is a myth

[Stephen G Simpson]

John Mayberry 14 Mar 1999 12:58:33 writes:
 > 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. 
 ...  
 > 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.

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).  Ditto for the `admissible logics' that were popular
in the 1960's and 1970's.

 > No doubt this position is defensible, but he has not defended it:
 > he has merely asserted it.

My defense would be that you cannot call X logic unless X exhibits the
essential features of what has been called logic in the past.  The
principal feature that I have in mind is a formal method of moving
from premises to conclusions.  Historically, this is what logic has
always been:

  `logic: a science that deals with the principles and criteria of
  validity of inference and demonstration: the science of the formal
  principles of reasoning' (Webster on-line dictionary, definition
  1a).

This is really a burden-of-proof issue.  If you claim that X is logic,
then it's up to you to exhibit the axioms and rules of inference of X.
In the case of X = so-called `second-order logic', nobody has done
this.  Without this, to claim that `second-order logic' is logic is to
rewrite the dictionary.

[ 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.
Advocates of second-order logic frequently ambiguate on this important
distinction. ]

-- Steve