The Löwenheim-Skolem Theorem says that if M is an infinite model in some language L, then for every cardinal {\displaystyle \kappa \geq |L|}, there is a model N of cardinality {\displaystyle \kappa }, elementarily equivalent to M.

More precisely, one has two theorems:

Downward Löwenheim-Skolem Theorem: Let M be an infinite model in some language L. Then for any subset S ⊆ M, there exists an elementary substructure {\displaystyle N\preceq M} containing S, with {\displaystyle |N|=|S|+|L|}. In particular, taking S to be an arbitrary subset of size {\displaystyle \kappa } with {\displaystyle |L|\leq \kappa \leq |M|}, we can find an elementary substructure of M of size {\displaystyle \kappa }.

Upward Löwenheim-Skolem Theorem: Let M be an infinite model in some language L. Then for every cardinal {\displaystyle \kappa } bigger than |M| and |L|, there is an elementary extension of M of size {\displaystyle \kappa }.

On the level of theories, the Löwenheim-Skolem Theorem implies that if T is a theory with an infinite model, then T has a model of cardinality {\displaystyle \kappa } for every infinite {\displaystyle \kappa \geq |T|}.

These statements become slightly simpler when working in a countable language. In this case, Upward Löwenheim-Skolem says that if M is an infinite structure, then M has elementary extensions of all cardinalities greater than |M|. Similarly, Downward Löwenheim-Skolem implies that if M is an infinite structure, then M has elementary substructures of all infinite sizes less than |M|.

Proof of Downward Löwenheim-Skolem Theorem[]

Let M be a structure. For each non-empty definable subset D of M, choose some element e(D) ∈ D, using the axiom of choice. If X is any subset of M, let

{\displaystyle c(X)=X\cup \{e(D):D{\text{ definable over }}X,~D\neq \emptyset \}}

Note that over a set of size {\displaystyle \lambda }, there are at most {\displaystyle \lambda +|L|} definable sets. Consequently,

{\displaystyle |c(X)|\leq |X|+|L|}

Now given S ⊆ M as in the theorem, let

{\displaystyle N=S\cup c(S)\cup c(c(S))\cup \cdots }

By basic cardinal arithmetic, {\displaystyle |N|=|S|+|L|}. Then {\displaystyle N\preceq M} by the Tarski-Vaught test. Indeed, if D is a subset of M definable over N, then D uses only finitely many parameters, and is therefore definable over c(i)(S) ⊆ N for some i. Then

{\displaystyle e(D)\in c^{(i+1)}(S)\subset N},

so e(D) is an element of {\displaystyle N\cap D}. Therefore, every non-empty N-definable set intersects N. Therefore the Tarski-Vaught criterion holds and N is an elementary substructure of M. It has the correct size. QED

Proof of Upward Löwenheim-Skolem Theorem[]

Given an infinite structure M and a cardinal {\displaystyle \kappa } at least as big as both |M| and |L|, let T be the union of the elementary diagram of M and the collection of statements

{\displaystyle \{c_{\alpha }\neq c_{\beta }:\alpha <\beta <\kappa \}}

where {\displaystyle \{c_{\alpha }\}_{\alpha <\kappa }} is a collection of {\displaystyle \kappa } new constant symbols. By compactness, T is consistent. Indeed, any finite subset of T only mentions finitely many of the {\displaystyle c_{\alpha }} and therefore has a model consisting of M with the finitely many {\displaystyle c_{\alpha }} interpreted as distinct elements of M. So by compactness we can find a model {\displaystyle N\models T}. Then N is a model of the elementary diagram of M, so N is an elementary extension of M. Also, the {\displaystyle c_{\alpha }} ensure that N contains at least {\displaystyle \kappa } distinct elements, i.e., {\displaystyle |N|\geq \kappa }. There is a possiblity that N is too big; to hit {\displaystyle \kappa } on the nose, we use Downward Löwenheim-Skolem to find an elementary substructure of N having size {\displaystyle \kappa } and containing M. On general grounds, the resulting structure is an elementary extension of M. QED ::: ::: :::