1
$\begingroup$

I get how first-order logic has Lowenheim-Skolem, compactness theorem, but I am not sure why this leads to first-order logic being strongest. All Lowenheim-Skolem seems to say is that for first-order countable infinite theory, there exists countable infinite model. And all compactness theorem seems to say is that for any subset of the aforementioned theory, there must be a model. What are consequences of not having those?

$\endgroup$
  • $\begingroup$ Example: math.stackexchange.com/questions/284455/… $\endgroup$ – Asaf Karagila Feb 21 '13 at 11:56
  • 2
    $\begingroup$ Compactness and Loweheim-Skolem are very nice results. However, they could be viewed as indicating weakness rather than strength, since they are ways in which standard first-order logic has less expressive strength than second-order logic, or certain infinitary logics. $\endgroup$ – André Nicolas Feb 21 '13 at 12:38
8
$\begingroup$

You have to be careful to be precise about what you mean by "strongest."

One notion of "strength" of the logic has to do with which classes of structures appear as a class of models for some theory in the logic. So logic $L$ is stronger than or equivalent to logic $L'$ ($L\succeq L'$) if every time a class of structures is "elementary" for $L'$ (can be picked out as the class of models of some $L'$-theory), it is also "elementary" for $L$.

If you take this notion of strongest, then you have Lindstrom's theorem (which might be what prompted the question). Lindstom's theorem states that first-order logic is the strongest abstract logic which satisfies Lowenheim-Skolem and compactness.

(Parenthetical note: If I remember correctly, "strongest" here means that first-order logic is a maximal element of this partial order on abstract logics, not a maximum element.)

So in this sense, it's not that Lowenheim-Skolem and compactness make first-order logic strong. Instead, these properties are limits to the strength of the logic (Lowenheim-Skolem implies that the logic can't talk about the infinite cardinality of a model, compactness implies that the logic can't separate the finite from the pseudo-finite, etc.) and first order logic is as strong as possible without violating those two properties.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.