FANDOM


The Löwenheim-Skolem Theorem says that if M is an infinite model in some language L, then for every cardinal $ \kappa \ge |L| $, there is a model N of cardinality $ \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 $ N \preceq M $ containing S, with $ |N| = |S| + |L| $. In particular, taking S to be an arbitrary subset of size $ \kappa $ with $ |L| \le \kappa \le |M| $, we can find an elementary substructure of M of size $ \kappa $.

Upward Löwenheim-Skolem Theorem: Let M be an infinite model in some language L. Then for every cardinal $ \kappa $ bigger than |M| and |L|, there is an elementary extension of M of size $ \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 $ \kappa $ for every infinite $ \kappa \ge |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 TheoremEdit

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

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

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

$ |c(X)| \le |X| + |L| $

Now given S ⊆ M as in the theorem, let

$ N = S \cup c(S) \cup c(c(S)) \cup \cdots $

By basic cardinal arithmetic, $ |N| = |S| + |L| $. Then $ 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

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

so e(D) is an element of $ 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 TheoremEdit

Given an infinite structure M and a cardinal $ \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

$ \{c_\alpha \ne c_\beta : \alpha < \beta < \kappa \} $

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