Model-Theoretic Connections

The Compactness Theorem and its Consequences

If every finite piece of a theory has a model, the whole theory has one. That single statement is why first-order logic cannot express finiteness, well-ordering, or connectedness.

Engineering · Mathematics5 min readKV-MATH-0252

Learning objectives

State compactness in both the satisfiability and consequence forms.
Prove it using ultraproducts.
Derive the existence of non-standard models.
Use compactness to show a property is not first-order expressible.
List the standard non-expressible properties.
Relate compactness to BPI and to topological compactness.

01Two formulations

Compactness stated twice
Form	Statement
Satisfiability	If every finite subset of a theory T has a model, then T has a model.
Consequence	If T ⊨ σ then Σ ⊨ σ for some finite Σ ⊆ T.

The two are contrapositives of one another applied to T ∪ {¬σ}. The satisfiability form is the one used to construct models; the consequence form is the one used to argue that proofs are finite.

Key resultWhy 'compactness'

The name is topological. The space of complete theories in a language carries a natural topology — the Stone topology on the Lindenbaum algebra — and the theorem says exactly that this space is compact. Since the Lindenbaum algebra is a Boolean algebra, this is Stone duality applied to logic, and it is why compactness is equivalent to BPI.

02Proof by ultraproducts

ProcedureCompactness from Łoś's theorem

in: finitely satisfiable T → out: a model of T

input: theory T with every finite subset satisfiable
let I := the set of finite subsets of T
for each Σ ∈ I choose a model A_Σ ⊨ Σ
for each σ ∈ T let I_σ := { Σ ∈ I : σ ∈ Σ }
the family { I_σ : σ ∈ T } has the finite intersection property:
I_{σ₁} ∩ ⋯ ∩ I_{σₙ} contains {σ₁,…,σₙ}, so is non-empty
extend it to an ultrafilter U on I (BPI)
form B := ∏_Σ A_Σ / U
for each σ ∈ T: { Σ : A_Σ ⊨ σ } ⊇ I_σ ∈ U, so by Łoś B ⊨ σ
therefore B ⊨ T

The finite intersection property step is the crux and is where the hypothesis is used. Caveat: BPI is needed to obtain U, and compactness is in fact equivalent to BPI, so no weaker principle would suffice.

The Henkin construction gives an alternative proof by building a model syntactically from a maximal consistent set of sentences. It conceals the choice principle inside the maximality step, which is itself of BPI strength.

03Non-standard models

Compactness produces models with elements that no standard model contains.

Add a new constant
Extend the language of arithmetic by a constant c and the theory by the sentences c > 0, c > 1, c > 2, and so on for every numeral.
Every finite subset is satisfiable
A finite subset mentions finitely many numerals; interpret c as any larger standard number in the standard model.
Compactness gives a model
The whole theory has a model, in which c exceeds every standard natural number.
The model is elementarily equivalent to the standard one
It satisfies the same sentences, since the theory included all of Th(ℕ). Yet it is not isomorphic — it contains an infinite element.

The same argument applied to the ordered field of reals gives infinitesimals, and hence the framework of non-standard analysis. Applied to any infinite structure it gives proper elementary extensions of arbitrary size — the upward Löwenheim–Skolem theorem.

04Proving non-expressibility

ProcedureThe compactness recipe for non-expressibility

in: candidate property P → out: proof of non-expressibility

goal: show property P is not expressible by a first-order theory
assume for contradiction that T has exactly the structures with P as models
extend T by new symbols and sentences asserting P fails 'at the limit'
show every finite subset of the extended theory is satisfiable,
usually by taking a large enough structure with P
compactness gives a model of the extended theory
that model satisfies T but lacks P — contradiction
conclude: P is not first-order expressible

The recipe works whenever P is a 'finiteness at infinity' condition. Caveat: it does not apply to properties that are genuinely first-order but merely awkward, so failure of the recipe proves nothing.

Standard non-expressible properties
Property	Compactness argument
Finiteness	Add sentences asserting more than n elements for every n.
Being a torsion group	Add a constant of infinite order.
Being archimedean	Add an element exceeding every numeral.
Well-ordering	Add a descending chain of constants.
Connectedness of a graph	Add two constants at distance greater than every n.
Being the standard naturals	Non-standard models exist.
Cardinality above the language size	Löwenheim–Skolem in both directions.

05Consequences for universal algebra

Finite algebras

Not an elementary class

The class of finite algebras of a type is not the model class of any first-order theory. So 'locally finite' and 'residually finite' are not first-order properties.

Varieties

Elementary only sometimes

A variety is an elementary class exactly when it is finitely based — its identities then form a finite theory. Non-finitely-based varieties are not elementary classes, which is one motivation for the finite basis problem.

NoteWhere this bites in Chapter V

The finite basis theorems matter partly because a finite basis makes the variety an elementary class, bringing the whole model-theoretic apparatus to bear. Without one, compactness arguments about the variety are unavailable.

06The choice-principle picture

What compactness costs and equals
Statement	Relation to compactness
Boolean Prime Ideal Theorem	equivalent
Ultrafilter lemma	equivalent
Tychonoff for compact Hausdorff spaces	equivalent
Gödel completeness (general form)	equivalent
Stone representation theorem	equivalent
Axiom of choice	strictly stronger
ZF alone	strictly weaker — compactness fails in some models

The equivalences make compactness one of the most-connected statements in mathematics: a topological theorem, an algebraic theorem and a logical theorem that are the same theorem. That the Lindenbaum algebra is Boolean and its Stone space is the space of complete theories is the thread linking them.

Frequently asked

Does compactness hold for second-order logic?

No. Second-order logic can express finiteness and well-ordering, and it categorically characterises the natural numbers, so compactness fails outright. Lindström's theorem makes this precise: first-order logic is the strongest logic with both compactness and downward Löwenheim–Skolem.

Is compactness constructive?

No. It is equivalent to BPI and produces models that cannot be exhibited. A non-standard model of arithmetic exists by compactness and no such model can be given explicitly — indeed Tennenbaum's theorem shows no countable non-standard model has computable operations.

Why is the class of finite structures not elementary?

Because a theory whose models include arbitrarily large finite structures has an infinite model, by adding sentences asserting more than n elements exist and applying compactness. So no theory has exactly the finite structures as models. This is the single most-used non-expressibility argument.

Sources and further reading

S. Burris and H. P. Sankappanavar, A Course in Universal Algebra, Millennium Edition (a corrected re-typesetting of Springer GTM 78, 1981).
G. Grätzer, Universal Algebra, 2nd edition, Springer.
R. McKenzie, G. McNulty and W. Taylor, Algebras, Lattices, Varieties, Volume I.

Original KEVOS® explanatory article. Written from the topic map of the cited works; no text is reproduced from them.