Compactness and Loewenheim-Skolem Theorems

The compactness and Loewenheim-Skolem theorems are the two foundational results that govern which structures first-order theories can describe, revealing both the power and the inherent limitations of first-order logic.

Definition

The compactness theorem states that a set of first-order sentences is satisfiable if and only if every finite subset is; the Loewenheim-Skolem theorems state that any first-order theory with an infinite model has models in every infinite cardinality at least that of its language.

Scope

This topic covers the compactness theorem and its proof via completeness or ultraproducts, the downward and upward Loewenheim-Skolem theorems on the cardinalities of models, their standard consequences including the existence of nonstandard models of arithmetic and analysis, and the Skolem paradox.

Core questions

• Why does finite satisfiability of a theory guarantee a model?
• How do these theorems produce nonstandard models of arithmetic and the reals?
• Why can no first-order theory characterize an infinite structure up to cardinality?
• What is the Skolem paradox and how is it resolved?

Key theories

Compactness theorem

If every finite subset of a set of sentences has a model, then the whole set has a model; it follows from completeness or can be proved semantically with ultraproducts.

Downward Loewenheim-Skolem theorem

Any infinite structure has an elementary substructure of cardinality at most that of its language, so countable theories with infinite models have countable models.

Upward Loewenheim-Skolem theorem

Any infinite model can be elementarily extended to models of every larger cardinality, so first-order theories cannot fix the size of their infinite models.

Clinical relevance

These theorems are the workhorses of model theory: compactness is used to construct nonstandard models that prove or transfer results, and the Loewenheim-Skolem theorems explain why first-order axiomatizations of the natural numbers or the reals always admit unintended models, shaping the choice of logical frameworks.

History

Loewenheim proved a version of the downward theorem in 1915 and Skolem generalized and sharpened it through the 1920s. Compactness was obtained by Goedel as a corollary of completeness and extended to uncountable languages by Maltsev, who first exploited it to derive algebraic theorems, opening the way to applied model theory.

Key figures

• Leopold Loewenheim
• Thoralf Skolem
• Kurt Goedel
• Anatoly Maltsev

Seminal works

• changkeisler1990
• marker2002
• hodges1993

Frequently asked questions

What is a nonstandard model of arithmetic?

By compactness one can add to the axioms of arithmetic a constant larger than every numeral; the resulting consistent theory has a model containing infinite elements beyond the standard natural numbers. Such models satisfy exactly the same first-order sentences as the standard one.

What is the Skolem paradox?

The downward Loewenheim-Skolem theorem gives a countable model of set theory, even though that theory proves uncountable sets exist. The resolution is that uncountability is relative to the model: a set the model regards as uncountable has no bijection with the naturals inside the model, though one exists externally.