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

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

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 for every infinite .

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 Note that over a set of size , there are at most definable sets. Consequently, Now given S ⊆ M as in the theorem, let By basic cardinal arithmetic, . Then 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 ,

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