FOM: Re: SOL confusion

[Harvey Friedman]

Reply to Insall 12:07AM 9/9/00:

>Harvey:
>There is a sentence in second order logic with only equality whose models
>are exactly the domains that are finite. There is no sentence in first
>order logic with only equality whose models are exactly the domains that
>are finite.

>Matt:
>This I knew, and have said as much in some replies to Roger Jones.  This is,
>in fact, the reason that SOL fails to satisfy the compactness principle.
>Since compactness in a finitary deduction system is equivalent to the
>conjunction of soundness and completeness, I conclude that SOL is either
>unsound or incomplete.

Semantic SOL is not a finitary deduction system. In fact, it is not even a
deduction system at all.

In addition, your statement

"compactness in a finitary deduction system is equivalent to the
conjunction of soundness and completeness"

is meaningless to me.

Any sound deductive system for SOL is necessary incomplete simply because
the set of semantic SOL vaidities is not recursively enumerable.

>Being convinced that it is sound, I conclude that
>SOL is incomplete.

Deductive SOL has been known to be incomplete for semantic SOL for 70
years, and perhaps longer.

>Now, you and Martin Davis are discussing multiple versions of SOL.

We are discussing the same semantic SOL, and we are discussing the same
versions of deductive SOL.

>One of
>these you refer to as the ``more robust, unproblematic, semantic sense''.
>This I am less familiar with.

I was referring to standaard semantic SOL. Itt is robust and unproblematic.

>From some of what you have said, Harvey, it
>seems to me that the semantics to which you have referred is the
>generalization of the definition for FOL of satisfaction that is frequently
>attributed to Tarski.  Is this still what you mean when you say ``...
>semantic sense''?

Yes, semantic SOL.

>If so, I wonder at your use of the term
>``unproblematic'',

Well motivated, canonical, obvious, etcetera.

>for it seems to me it will still fail to satisfy the
>compactness principle unless you change the semantics to, for instance, the
>general semantics presented in Enderton's ``A Mathematical Introduction to
>Logic''.

The compactness principle is not a defect in semantic SOL. It has nothing
to do with any of the goals served by semantic SOL.

>However, it seems to me that this entire system for SOL (general
>SOL) can be interpreted in (some extension of) first order ZF (or ZFC),
>reducing, as Enderton seems to suggest, general SOL to a first order theory
>(see page 286).

You are referring to some not standard semantics for SOL, I think called
Henkin semantics.

>I wonder if I have misunderstood some of your terminology, or if you can
>point me to some specific references where enough of this ``robust'' version
>of SOL is rigorously developed.

See, e.g., Richard Montague, Reduction of Higher-Order Logic, in:  The
Theory of Models, ed. Addison, Henkin, Tarski, North-Holland, 1965.