# FOM: 2nd-order logic

A.P. Hazen a.hazen at philosophy.unimelb.edu.au
Thu Mar 15 22:41:37 EST 2001

This string started with a question about  "some form of quantification"
which extended First-Order Logic (giving it the power of Second-Order
Logic), but which did not involve variables ranging over
sets/classes/properties/concepts and which Quine alledgedly felt overcame
his objections to Second-Order Logic (that it was "set theory in sheep's
clothing").
So far the favored candidate seems to be the logic of branching
quantifiers, which is odd, since Quine's published conclusion (in his
"Philosophy of Logic," and at maybe a bit greater length in the paper
"Logic and Quantification" in his "Ontological Relativity") was that this
WASN'T logic, because it lacked a complete proof procedure.  (Note that
this objection will extend automatically to ANY "logic" with the full
expressive power of Second-Order Logic.)
Branching quantifiers are not the only way of extending First-Order Logic
without using set(/whatever) variables.  There is the "Most" quantifier
(binding a variable occurring in two formulas: Mx(...x...;---x---) is
interpreted as meaning "More of the objects satisfying ...x... also satisfy
---x--- than don't); apparently some people call this the "Rescher"
quantifier.  Another quantifier definable in terms of it is the
Equinumerosity quantifier (EQx(...x...;---x---) meaning that the satisfiers
of ...x.. are of the same cardinality as those of ---x---).  This is
apparently sometimes called the "Hartig Quantifier"; there is a review of
results about it by Heinrich et al. in JSL 56 (1991).  Both of these share
with the logic of branching quantifiers the property that the only
variables appearing range over individuals, and "most" belongs to the same
grammatical category as "all" and "some" in English.  So if the Quinean
objections to be overcome were semantic or "ordinary-language" instead of
proof-theoretic, these would be good candidates.  First-Order Logic
enriched with a MOST quantifier seems to be a formalization of a part of
ordinary discourse uniform with that formalized by First-Order Logic.
Another example-- similar in not permitting a complete proof procedure,
and in giving some of the expressive power of Second-Order Logic (e.g.
allowing a categorical axiomatization of arithmetic)-- comes from
considering MULTIGRADE predicates.  These are predicates-- such as "live
together" or "have lined up in order of age"-- which can take a variable
number of arguments.  Adding them to First-Order Logic in such a way that
each occurrence of the predicate has a definite number of arguments is
trivial; the interesting bit comes when we allow quantified sentences to
make generalizations with instances of varying "grade."  This means
allowing quantifiers to bind (and multigrade predicates to combine with)
"vector" variables: variables which can have sequences of terms (of varying
length) substituted for them. (Details: Barry Taylor  and A.P. Hazen,
"Lexibly structured predication," in "Logique et Analyse" 139-140 (1992
cover date- actually appeared 1995), pp. 375-393)  This logic seems like a
very natural extension of First-Order Logic if you are in the habit of
using F.O.L. to formalize non-mathematical subject matter.
I do not, however, know if Quine ever thought about these logics.
Very different is George Boolos's "plural quantification."  This is
formally (monadic) Second-Order Logic, and has Second-Order variables, but
the Second-Order variables are no interpreted as RANGING OVER any special
domain of higher-type entities.  I know that Quine discussed this
interpretation of Second Order Logic with David Lewis (Burgess, Lewis, and
I corresponded with Quine during the preparation of the appendix to Lewis's
1991 monograph "Parts of Classes"), and I believe  he took a fairly
positive attitude toward it.  And, when combined with the calculus of
individuals, which we know Quine liked, it gives the expressive power of
full Second-Order logic.
---
The last PUBLISHED remarks of Quine's on Second-Order Logic that I know
of are in his reply to Parsons and Putnam on p. 352 of Leonardi and
Santambrogio, eds., "On Quine" (1995-- papers from the 1990 Quine
conference in San Marino).  There he still says "I dissociate so-called
higher-order logic from set theory, an extra-logical segment of
mathematics."  As reasons he gives its incompleteness (it "is subject to
Gödel's celebrated incompleteness theorem") and that "it has ontological
content...it has its special objects."  The various logics (and Boolos and
Lewis reinterpretations of logic) mentioned are all attempts to get around
the second, but all necessarily fall foul of the first.
--
Allen Hazen
Philosophy Department
University of Melbourne