502 – The Löwenheim-Skølem theorem

November 8, 2009

In this note I sketch the proof of the Löwenheim-Skølem (or Löwenheim-Skølem-Tarski) theorem for first order theories. This basic result of model theory is really a consequence of a set theoretic combinatorial lemma, as the proof will demonstrate.

Let {{\mathcal L}} be a first order language, understood as a set of constant, function, and relation symbols. Let

\displaystyle  \kappa_{\mathcal L}=|{\mathcal L}|+\aleph_0,

so {\kappa_{\mathcal L}} is {|{\mathcal L}|,} unless {{\mathcal L}} is finite, in which case we take {\kappa_{\mathcal L}=\omega.} Talking about {\kappa_{\mathcal L}} rather than {|{\mathcal L}|} simplifies the presentation slightly.

The Löwenheim-Skølem theorem is concerned with the possible infinite sizes of models of first order theories. Of course, a theory {T} could only have finite models; the result does not say anything about {T} if that is the case.

Theorem 1 If {T} is a first order theory in a language {{\mathcal L},} and there is at least one infinite model of {T,} then there are models of {T} of size {\lambda,} for all {\lambda\ge\kappa_{\mathcal L}.}

We will prove a more precise statement. Before stating it, note that it is possible to have a theory {T} in some uncountable language {{\mathcal L}} such that {T} has models of certain infinite sizes, but not all. Theorem 1 does not say anything about infinite models of {T} of size {<\kappa_{\mathcal L}.} What cardinals in this range are the possible sizes of models of {T} is actually a rather difficult problem, and we will not address it.

Read the rest of this entry »