Löwenheim-Skolem theorem

The Löwenheim--Skolem theorems control the cardinalities of models of a first-order theory without changing its first-order truths.

A countable model of set theory can internally assert that an uncountable set exists. There is no contradiction because “there is a bijection” ranges only over functions in the model. An external enumeration of its domain need not itself be an element of that domain. Löwenheim-Skolem theorem controls external cardinality; Cantor's theorem remains valid for the sets and functions that the model contains.

If an $L$-theory has an infinite model, then it has models of arbitrarily large cardinality. For a cardinal $\kappa$, add constants $c_{\alpha }$ for $\alpha <\kappa$ and all inequalities $c_{\alpha }\ne c_{\beta }$. Every finite fragment is satisfiable in the given infinite model, so compactness gives a model with at least $\kappa$ elements. Applying the downward theorem produces a model of exactly $\kappa$ when $\kappa \ge |L|+{\aleph }_0$.

If $A$ is an infinite $L$-structure and $|L|+{\aleph }_0\le \kappa \le |A|$, then $A$ has an elementary substructure of cardinality $\kappa$. One proof adds Skolem functions for existential formulas and closes a chosen $\kappa$-element subset under them; the closure still has size $\kappa$, and the Tarski--Vaught test makes it elementary.