FOM: second-order logic is a myth

[Pat Hayes]

> > [Simpson] emphasises repeatedly that when he says 'second-order
> > logic' he means to refer not to Henkin's logic but to full
> > classical second-order logic. The trouble is, that this distinction
> > makes sense only if we understand 'logic' to be defined
> > semantically.
>
>I don't understand this remark.  Maybe you had better explain.

Had you posted my full message, everyone would have seen the explanation,
but thanks for the opportunity to give a more careful one.

>I define logic in the accepted traditional way, as the science of
>correct inference.  I don't think logic should be `defined
>semantically', although obviously considerations of meaning are
>relevant to the question of what is a correct inference.

"The science of correct inference" is a vague enough phrase to be
understood in several ways. You construe it to mean the study of rules
which sanction or describe inference-making; but another (quite coherent)
position thinks of it as referring to a semantical analysis of the notion
of validity. For many centuries these different interpretations would have
focussed in the same place, but since second-order logic isn't complete
they diverge. I don't mean to argue that your construal is wrong, let me
emphasise: in fact, I largely agree with you, coming as I do from
computational logic. However - and this was my point - it seems to me that
when making the distinction between Henkin second-order logic and classical
second-order logic, and restricting your usage of the term "second-order"
to the latter, you are making an essentially semantic distinction. If a
logic is defined to *be* a set of axioms and rules of inference - what you
call "in the traditional way" - then there is, literally, no distinction to
be made between Henkin and 'classical' second-order logic: they are exactly
the same logic, in that sense of "logic". Henkin didn't rewrite the rules
of second-order logic, he just applied Godel's reasoning to second-order
syntax in order to reverse-engineer an alternative semantics which could
support a completeness theorem for them.

 On the other
>hand, I do follow Shapiro in distinguishing `second-order logic with
>standard semantics' (in my view this is not really logic, because it
>offers no rules,of inference) from `second-order logic with Henkin
>semantics' (in my view this is really a species of first-order logic,
>with essentially the usual first-order rules of inference).
>
> > It's the same *logic*, though, in Simpson's sense.
>
>Now I'm really confused.  Do you accept Shapiro's distinction between
>standard semantics and Henkin semantics, or don't you?

Of course I accept the distinction between the *semantics*. However, this
very word makes my point: they are both semantic theories for the same
*logic*, if by "logic" one means a syntax and a formal specification of
inferences (by means of rules of inference, tableau, sequents or whatever.)
And my point was only that you seem to want to have it both ways: a logic
is a system of rules, but the same set of rules is a different logic when
you give it a different semantics. (Or maybe: first-order logic is
primarily a system of rules, with validity a secondary matter; but
second-order logic must be defined semantically, and since the set of valid
inferences isnt R.E. it isnt really a logical calculus at all.)

To illustrate the point in a purely first-order context, consider
Herbrand's theorem, and an alternative semantics for predicate logic is
which E-quantifiers are skolemised, every ground term refers to itself, and
quantification is taken to be over the set of recursively defined term
expressions. The usual first-order rules are valid and complete with
respect to such Herbrand interpretations. Can one then legitimately claim
that predicate calculus isnt really about anything but syntax, and conclude
that predicate logic cannot refer to integers or sets? Or would you want to
say that the same rules with this different semantics are a different
logic? If the latter, how can you simultaneously claim that a logic is
defined to be a set of rules?
...

> > I don't see how one can re-do Tarski without mentioning sets.
>
>I'm not sure what you mean by `re-doing Tarski'.  If you are referring
>to the Tarski semantics for predicate calculus, then obviously there
>is no way to do it without sets, because the Tarski models are given
>by structures consisting of a set D and one or more relations on D.
>
>However, this does not mean that the predicate calculus depends on set
>theory.

I disagree. Even if Tarski's theory were only descriptive, I'd say that
when discussing foundational issues one can't legitimately introduce sets
into the discussion without providing some theory of what those sets are.
But in any case, there is some real mathematics to be done. How does one
establish completeness and compactness, for example, without making some
arguments about these sets? As you have noted, one doesn't need all of ZF
in order to establish first-order completeness, but one does need at least
a glimmering of some kind of of set theory.

>....  The predicate calculus
>can and should be understood and motivated as a general method of
>reasoning about any subject whatsoever,......

As I said in my previous message, I entirely agree with you here, as do
thousands of other people whose business is the construction of formal
axiomatizations of every subject under the sun. Predicate calculus has been
the staple representational language in AI now for a quarter of a century,
and is widely used as a programming language. But that isn't my point. To
claim that we need T to analyse the semantics of a language is not to say
that that language must be *about* T.

However, you then go on to make what I think is a basic philosophical
mistake, when you use "only":

>.... not only about Tarskian
>set-theoretic structures.

Tarski's theory of truth uses the idea of set not as one particular
subject-matter, but in order to make sense of the idea of quantification.
(If one is going to say what 'P(x) is true for all x' means in a particular
interpretation, then one has to specify the range of the 'all'.) The domain
of a Tarskian interpretation is a set, but it can be a set of anything: of
shoes and ships and sealing-wax, of cabbages and kings, you name it.
Tarski's theory is a theory of truth, not of truth relativised to set
theory. It uses sets to describe interpretations of a language which can
refer to anything.

Pat Hayes

PS.
>What is 1PC?
Sorry; this is a common contraction in my email community for "first-order
predicate calculus". (The term "predicate calculus" is considered to be
ambiguous, since second-order logic is also sometimes called 'second-order
predicate calculus' or 'second-order predicate logic'.)

---------------------------------------------------------------------
IHMC, University of West Florida		(850)434 8903   home
11000 University Parkway			(850)474 2091   office
Pensacola,  FL 32514			(850)474 3023   fax
phayes at ai.uwf.edu
http://www.coginst.uwf.edu/~phayes