I'm trying to understand the proof of (a version) of the upward Löwenheim Skolem Theorem, which states that given a language $\mathscr{L}$ and a set of $\mathscr{L}$-sentences $\Sigma$ with a countably infinite model $\mathscr{A}$, there also exists an uncountable model of $\Sigma$.

I understand that first one has to enrich the language with uncountably many new constant-symbols $\{c_i|i\in \mathbb{R}\}$ to get a language $\mathscr{L^*}$, and then considers $\Sigma'=\Sigma \cup\{c_i\neq c_j|i\neq j\}$ and shows that it has an uncountable $\mathscr{L}^*$-model by adding new elements $\{a_i|i\in I\}$ to $\mathscr{A}$, proving that this is a $\mathscr{L}^*$model of every finite subset of $\Sigma'$, and hence due to the compactness theorem also a $\mathscr{L}^*$model of $\Sigma'$. Then the restriction of $\Sigma'$ is an $\mathscr{L}$-model of $\Sigma$ with the same cardinality as $\mathscr{A}\cup\{a_i|i\in I\}$, i.e. uncountable.

But I am missing the point where I need that there has to exist a countably infinite model in the first place. Why can't it just be finite?


Your reproduction of the proof is a bit off, which is why you're confused.

You're not supposed to add new elements to the model in the step where you consider the finite subsets of $\Sigma'$. The point here is that the original $\mathscr A$ can be a model of every finite subset of $\Sigma'$, without adding new individuals, because it has enough elements already to assign meanings to the $c_i$ constants such that sufficiently many of them are different. But this step only works because $\mathscr A$ is infinite; if it were finite there might not be space to make sufficiently many of the $c_i$s map to different different elements.

After you have done this, you know that $\Sigma'$ is consistent (by compactness), and the completeness theorem now gives you a new model for the entire $\Sigma'$. In this new model all the $c_i$s are different, so it must have at least the same cardinality as $I$.

(And then you may need to use the downwards Löwenheim-Skolem theorem to cut your new model down to size exactly $|I|$).

And now you should also be able to see why the hypothesis can be weakened from "$\Sigma$ has an infinite model" to "for every finite $n$, $\Sigma$ has a model of cardinality at least $n$".

  • $\begingroup$ As a secondary issue: Can one map different constant-symbols to the same individual? And regarding your main point: So I need at least as many different individuals in $\mathscr{A}$ as there are different $c_i$'s appearing in each finite subset of $\Sigma'$ for $\mathscr{A}$ to be a model of said subset? $\endgroup$ – azureai Jan 17 '16 at 14:13
  • 1
    $\begingroup$ @see: (1) There is nothing in the definition of "structure" that prevents two different constant letters from having the same interpretation. This possibility is necessary for the completeness theorem to hold. For example, the theory $\{\forall x\forall y(x=y)\}$ in the language $\{c_1,c_2\}$ is consistent (having more constants that are not mentioned in any axiom doesn't make it easier to derive a contradiction, because a variable can do anything that such a constant does in a proof), but it can only have a model if $c_1$ and $c_2$ are allowed to be interpreted as the same element. $\endgroup$ – hmakholm left over Monica Jan 17 '16 at 14:23
  • 1
    $\begingroup$ @see: (2) Yes, that is a good way to think of it. It is not strictly true, in that for some finite subsets of $\Sigma'$ you can get away with fewer elements than that. For example if you consider the subset $$\{c_1\ne c_2, c_3\ne c_4, \ldots, c_{2n-1}\ne c_{2n} \}$$ then having two elements is enough. $\endgroup$ – hmakholm left over Monica Jan 17 '16 at 14:26
  • $\begingroup$ Got it. Thank you very much. $\endgroup$ – azureai Jan 17 '16 at 14:48

Consider the sentence $\forall x \forall y.x = y$. The only models of this sentence have exactly one element, so the upward Löwenheim-Skolem theorem must fail for the set comprising just this sentence. The proof breaks down because $c_1 \neq c_2$ is not satisfiable in any model of this sentence.


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.