2
$\begingroup$

I found two definitions of the Downward Löwenheim-Skolem Theorem:

Def.1: If Γ is consistent, then it has a countable model, i.e. it is satisfiable in a structure whose domain is either finite or countably infinite.

From Zach et al.

Def. 2: Let B be a model for ℒ and let κ be any cardinal such that |ℒ| ≤ κ ≤ |B|. Then, B has an elementary submodel A of cardinality κ.

From Weiss et al.

What confuses me is that the first definition makes statements of finite models while the second definition makes statements only about models of cardinality |ℒ| ≤ κ, i.e. κ must be at least countably infinite, since "any language ℒ contains infinitely many variables".

Is there an explanation that somehow unifies those two definitions? Or are they fundamentally different?

Looking forward to the responses 😊.

$\endgroup$
3
$\begingroup$

Well the difference is that the first version of the theorem is simply false if there are not more assumptions on the language; and even if the right hypotheses are given, the first version is incredibly weaker than the second one.

Note that, as stated, version 2 is also false, $\kappa$ needs to be assumed to be infinite for it to be true.

With these precisions, let's compare the two versions. For simplicity, and to make the first version true and the second version easier to state, let's assume the language is at most countable.

In this case the first version becomes true, and the second one becomes : if $B$ is an $\mathscr{L}$-structure and $\kappa$ an infinite cardinal, $\kappa\leq |B|$ then $B$ has an elementary substructure of size $\kappa$.

From this we may deduce the first version by simply saying : if $\Gamma$ is consistent, then either it has a finite model, in which case we are done; or it has an infinite model, in which case we may apply version 2 with this model $B$ and $\kappa = \aleph_0$.

Since $B$ is a model of $\Gamma$, any elementary substructure is also a model of $\Gamma$, so we get a countable model and we are done.

Now version 1 is much weaker than version 2 because it does not speak about any cardinals beyond $\aleph_0$, and it does not even speak about elementary substructures; you only get models of a certain theory.

I don't know if this weakness can be quantified, but for instance I wouldn't be surprised if there were models of ZF+(version 1) + $\neg$ (version 2) (note that I have to put ZF and not ZFC because of course ZFC proves version 2 - the existence of these models of course relying on the consistency of ZF) - though I can't be sure, someone more qualified than me should be able to answer.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ In def.2 $\kappa$ is assumed to be $\ge |\mathcal L|$, so it must be infinite. $\endgroup$ – Berci Jan 26 '19 at 12:30
  • $\begingroup$ @Berci : it depends on the definition of $|\mathscr{L}|$; but if you say that $|\mathscr{L}|$ must be infinite then yes $\endgroup$ – Maxime Ramzi Jan 26 '19 at 12:53
  • 8
    $\begingroup$ This answer is very clear. The book by Zach et al. does use the "old fashioned" approach in which there is a single, countable signature that is shared by every first-order theory (p. 64ff). So, in their set of definitions, their statement of the Lowenhiem-Skolem theorem is correct. This is an important point for the OP: you cannot mix and match theorems from introductory logic books without checking the exact definitions in each book to see if they match. $\endgroup$ – Carl Mummert Jan 26 '19 at 13:13
  • 6
    $\begingroup$ Related to the question at the end of the answer, the general Lowenheim-Skolem theorem is equivalent to the principle "Dependent Choice", slightly weaker than AC, over ZF. The first version of the LS theorem above, for countable theories, is provable in ZF. There is some info linked from math.stackexchange.com/questions/1367342/… $\endgroup$ – Carl Mummert Jan 26 '19 at 13:17
  • $\begingroup$ @CarlMummert good point about introductory textbooks, and thanks for mentioning the equivalence between LS and choice principles $\endgroup$ – Maxime Ramzi Jan 26 '19 at 13:19

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.