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