Lowenheim-Skolem Theorem

The Löwenheim-Skolem theorem is a fundamental result in mathematical logic establishing that any first-order theory with an infinite model has models of every infinite cardinality. Its upward form guarantees the existence of arbitrarily large models; its downward form guarantees the existence of countable models, even for theories that appear to characterize uncountable structures such as the real numbers.

The theorem reveals something deeply counterintuitive about first-order predicate logic: it cannot pin down a unique infinite cardinality. A first-order axiomatization of the real numbers has a countable model — a model in which the domain contains only countably many elements, despite the axioms apparently describing an uncountable continuum. This is Skolem's paradox: set theory, which proves the existence of uncountable sets, itself has a countable model. The paradox is not a contradiction; it results from the fact that 'uncountable' is itself a relational property that shifts meaning across models.

The Löwenheim-Skolem theorem is one of the limitative results — alongside Gödel's incompleteness theorems and Church's undecidability result — that define the ceiling of first-order formal systems. It demonstrates that expressive power and categorical uniqueness are not the same thing: a language can be powerful enough to axiomatize a structure without being powerful enough to characterize it. Any philosophy of mathematics that ignores the Löwenheim-Skolem theorem has not yet grappled with what mathematical language can and cannot do.