FOM: Re: SOL confusion
Harvey Friedman
friedman at math.ohio-state.edu
Fri Sep 8 17:40:23 EDT 2000
Reply to Insall 10:21AM 9/8/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 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.]
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."
>This is the reason I consider second order logic to be
>incomplete.
Do you mean "second" or "first"? If you mean "second" then I think you
should clarify what you mean by incomplete here.
>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.
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.
>This particular example you give
>shows that SOL, as you describe it, is not compact (i.e., it fails the
>compactness principle, as mentioned in Enderton, page 271).
Correct.
>It follows that
>SOL is either unsound or incomplete.
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.
More information about the FOM
mailing list