## FANDOM

78 Pages

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