FW: FOM: Re: SOL confusion

[Matt Insall]

>Matt:
>This I knew, and I have, I think, the same view of syntax and semantics as
>you.  (In fact, there is more trouble in FOL:  There is no SET of formulas
>in FOL with equality which encodes the notion of finiteness.  This follows
>from the compactness principle.)  [Please let me know if I am missing
>something here.]


Harvey:
The only thing you are missing is that you refer to "trouble". Since the
recognized successful purposes of FOL have nothing to do with expressing
the notion of finiteness in this way, it is wrong to refer to this as
"trouble."


Matt:
I guess I have chosen an unfortunate wording.  What I have felt for several
years is that all of mathematics can be done using first order logic.  It
seems to me that if others either believe this to be true or would like it
to be true, then they would consider the lack of a set of axioms for
finiteness in FOL to be a drawback, in this regard.  Perhaps I tried to
``overload'' the word ``trouble'' with some pre-suppositions I had, in
particular about the purposes of FOL.


>This is the reason I consider second order logic to be
>incomplete.


Harvey:
Do you mean "second" or "first"? If you mean "second" then I think you
should clarify what you mean by incomplete here.


Matt:
I mean SOL.  Actually, in light of the discussion about ``semantic'' versus
``deductive'' SOL, I should say ``This is the reason I consider DSOL
(deductive SOL) to be incomplete.''  What I mean is that DSOL fails to
satisfy the generalized completeness principle, in the sense that there is a
set S of sentences of DSOL, and there is a sentence p of DSOL, such that p
is a (semantic, in the sense of a ``Tarski-like'' semantics for SOL)
consequence of S, but there is no deduction of p from S.  It seems to me
that in any finitary deductive system, the compactness principle is
equivalent to the combination of soundness and completeness.  The proof is
really done the same one way as it is done in Enderton's book on page 136,
even though he states that there are proofs of compactness that avoid the
deductive calculus.  Thus, if the completeness and soundness principles
hold, then the compactness principle holds, because of the finitary nature
of proofs, coupled with the soundness to relate the semantics to the
deductions.  The other direction is straightforward as well.  Assume the
compactness principle in a logic with a deductive system available.  If the
system is unsound, it is, it seems to me,  trivially complete, so suppose it
is sound.  Let S be a set of formulas and let p be a formula such that p is
a consequence of S.  We wish to show that p is deducible from S.  To this
end, note that by compactness, p is a consequence of some finite subset
T={s_1,...,s_n} of S.  We claim that p is deducible from T.  To see this,
note that if it were not, then the union of {not(p)} with T would be
consistent, and then it would be satisfiable because of soundness, but it is
not, since p is a consequence of T.



>I understood that as with FOL, SOL proofs are finitary, and the
>compactness principle is equivalent to the conjunction of the soundness and
>(generalized) completeness principles.


Harvey:
Semantic SOL has no proofs. Deductive SOL does, and they are normally taken
to be finitary. Also, in what context does compactness imply soundness or
completeness? Compactness is a purely semantic notion, whereas soundness
and completeness are not. So I do not know what you are talking about here.



Matt:
I hope I have answered this question above.  Basically, I guess I am saying
that I believe the argument I gave does not depend upon very many specific
properties of the logic system, and hence can be generalized to many (most?)
deductive systems.  I believe this is similar in spirit to chapter XII of an
undergraduate text from which I have taught, called ``Mathematical Logic''
by Ebbinghaus, Flum and Thomas.  But I am trying here to extend the approach
they discuss to DSOL and other systems, in a similar way to the discussion
on pages 103 to 106 of ``Models and Ultraproducts'' by Bell and Slomson.  It
is demonstrated there that for classical FOL, Gödel-Henkin completeness,
compactness, and the BPF (boolean prime filter theorem) are all equivalent.
(Thus, they are all weak forms of AC.)




>It follows that
>SOL is either unsound or incomplete.


Harvey:
What is the connection?? What kind of SOL are you talking about here?

I don't see any point right now in responding to the rest of your message
until this is cleared up.


Matt:
I hope I have cleared up what I think is the connection between compactness
(an admittedly purely semantic notion), soundness (relating semantics and
deductions, in the sense that unsatisfiable formulas are not deducible), and
completeness (again relating semantics and deductions, but in the sense that
consequence entails deducibility).  Please tell me if I seem to have missed
something.



Dr. Matt Insall
http://www.umr.edu/~insall