Löwenheim–Skolem Theorem

Every satisfiable theory has a countable model, and the Skolem paradox.

The idea

Theorem (Löwenheim–Skolem theorem).

Let $T$ be a set of first-order sentences in a countable language. Downward. If $T$ has a model, then $T$ has a model whose domain is countable. Upward. If $T$ has an infinite model, then $T$ has models of every infinite cardinality.

The figure places both directions on the line of infinite cardinalities $\aleph_{0}, \aleph_{1}, \aleph_{2}, \dots$: from an infinite model of $T$, the downward theorem reaches a countable model at $\aleph_{0}$ and the upward theorem reaches every larger cardinality. Together they say that first-order logic exercises almost no control over the size of its models. The downward half is the surprising one: a model never needs to be larger than the language that describes it.

Two consequences follow. Structures of different cardinalities are never isomorphic, so no first-order theory with an infinite model determines its model up to isomorphism. And first-order set theory, if it has a model at all, has a countable model — a model that nonetheless satisfies the sentence asserting that an uncountable set exists. This is the Skolem paradox, and it resolves because uncountability is judged inside the model: the bijection that would count the set exists outside the model, but is not one of the model's elements.

Ways to work on it

• Walkthrough. The downward theorem, countable models, and the Skolem paradox.
• Practice. Decide which model-existence claims the theorems actually guarantee.
• Hardest. Show that no first-order theory determines its infinite model up to isomorphism.

Not sure where to start? Take the ten-question placement test.