research36 min studyLesson 973 in Mathematics

Compactness and Löwenheim–Skolem

Construct a nonstandard element and state model-size theorems with the language cardinal included.

Before you begin

On this page

The question for today

What you’ll understand

Derive compactness from finiteness of formal proofs.
Build a model with an element beyond every standard numeral.
State downward and upward Löwenheim–Skolem with parameter and cardinal bounds.

First-order assertions inspect finitely many symbols at a time, even when a theory contains infinitely many sentences. Compactness turns that finitary feature into a powerful existence principle. Löwenheim–Skolem then controls possible model sizes, provided the language's own size is included. These results explain why a theory may have models that differ sharply from its intended interpretation, without showing that infinite structures can be replaced by finite ones.

Finite satisfiability gives a model of the whole theory

Compactness states that a set of first-order sentences has a model exactly when each finite subset has a model. If the full theory were inconsistent, a finite proof of contradiction would use only finitely many premises. Soundness would make that finite subset unsatisfiable. Thus finite satisfiability gives syntactic consistency, and completeness supplies a model. This proof identifies the essential finitary input while keeping the semantic existence step explicit.

The finite models of different fragments need not fit together as nested structures. For example, demand at least n distinct elements for every positive integer n. Each finite collection is satisfied by a sufficiently large finite domain, but any model of all demands is infinite. Compactness produces a single model of every sentence; it does not choose one of the finite fragment models or give an effective method for finding the resulting infinite object.

\chi_n:=\exists x_1\cdots\exists x_n\bigwedge_{i<j}x_i\ne x_j,\qquad\{\chi_n:n\ge1\}\text{ has only infinite models}.

Every finite collection of these demands has a finite model, while their union requires unbounded domain size.↔ Scroll wide equations horizontally.

Downward size bounds must include the language and parameters

Work in the usual classical set-theoretic metatheory with choice and a set-sized first-order language L. If M is infinite and A is a subset of its domain, an elementary substructure containing A exists with size at most the maximum of the sizes of A, L, and the natural numbers. More precisely, any infinite cardinal lambda between that maximum and the size of M is achievable as the elementary substructure's size. Elementarity preserves all formulas with parameters from the smaller structure.

The construction repeatedly adds witnesses for existential formulas with parameters already selected; counting such formulas explains the language term in the bound. A countable language and countable A therefore permit a countable elementary substructure of any infinite M. An uncountable language need not. Upward Löwenheim–Skolem gives an elementary extension of infinite M of each cardinal at least the maximum of its size and the language size. Consequently a theory with an infinite model has models in every infinite cardinal at least the language size.

\max(|L|,|A|,\aleph_0)\le\lambda\le|M|\ \Longrightarrow\ \exists N\preccurlyeq M:\ A\subseteq N,\ |N|=\lambda.

The language and parameter bounds cannot be discarded when applying downward Löwenheim–Skolem.↔ Scroll wide equations horizontally.

A nonstandard element is not a new standard natural number

Expand the arithmetic language with a constant c and require c to exceed every standard numeral. Alongside all sentences true in the standard natural numbers, every finite fragment can be satisfied in that standard structure by choosing c large enough. Compactness then gives a model satisfying the whole expanded theory. Its c exceeds every interpreted standard numeral, so that model cannot be isomorphic to the standard natural numbers.

This conclusion distinguishes external standardness from internal arithmetic. The model still satisfies every first-order arithmetic sentence true in the standard structure, yet its domain has extra elements. Neither completeness nor compactness singles out an intended model up to isomorphism. Likewise, a countable model of a theory speaking about uncountable sets does not automatically supply inside that model a bijection that the theory forbids; external cardinality and internally definable functions are different comparisons.

\operatorname{Th}(\mathbb N)\cup\{\bar n<c:n\in\mathbb N\}\text{ is finitely satisfiable and hence satisfiable}.

The constant is larger than every standard numeral in the resulting model, without becoming a standard natural number.↔ Scroll wide equations horizontally.

Work it through

Make an element larger than every standard numeral

Apply compactness to true arithmetic together with the inequalities n<c for each standard natural n. Prove finite satisfiability and explain exactly why the resulting arithmetic reduct is nonstandard.

A finite fragment contains only finitely many inequalities, say with largest index N. Interpret the arithmetic symbols in $\mathbb N$ and c as N+1. Every selected true arithmetic sentence remains true, and each selected inequality holds.
Compactness gives one expanded structure satisfying every sentence in the full set. Its element c is strictly above zero, one, two, and every other standard numeral simultaneously. The finite choices N+1 were witnesses for fragments, not one fixed interpretation in the standard structure.
An isomorphism of arithmetic structures preserves zero and successor, hence every standard numeral by induction. If the reduct were isomorphic to $\mathbb N$ , the image of c would equal some standard n, contradicting the inequality $\bar n<c$ . Therefore its reduct is nonstandard.

c^{\mathcal M}>\bar n^{\mathcal M}\quad\text{for every standard }n,\qquad\mathcal M\not\cong\mathbb N.

Any arithmetic isomorphism fixes the values of all standard numerals.↔ Scroll wide equations horizontally.

The result

A model of every true first-order arithmetic sentence can still contain nonstandard elements. Compactness supplies existence, not an algorithm computing their arithmetic.

The living notebook

Explore the model

Interactive lab

Interactive lab · probability

Count finite labels before asking for infinitely many elements

Pause and Reset; set probability 0.5 and trials 4. The five bars group sixteen equally likely four-bit labels, with multiplicities 1,4,6,4,1. A domain consisting of those labels satisfies the at-least-sixteen demand but not the at-least-seventeen demand. For a fresh comparison Reset and set both probability 0.5 and trials 5: there are thirty-two labels. The controls stop at thirty trials and never construct an infinite model. Edits preserve time. The lab counts finite labels; compactness is a separate proof.

Exact probabilityHighlighted outcomeMean np

Mean · np: 5
Variance · np(1−p): 2.5
Total probability: 1

Success probability p0.5Trials n10

t = 0 s

These are exact binomial probabilities for independent trials with one fixed success probability. Playback tours the distribution; it does not resample outcomes. Parameter changes pause playback and recompute the model at the current elapsed time. Reset restores both parameters and returns time to zero. Playback starts paused. Adjust either parameter, then choose Play or Step.

Look forEvery finite demand can have enough labels without one finite domain satisfying all demands.

Pause & reason

Check your understanding

Interactive checks need JavaScript. You can still read the explanation.

Read the checkpoint explanation

The constants require at least κ different elements, and the language has size at least κ. The countable-model corollary applies to countable languages, not arbitrary uncountable signatures.

Your turn

Try it yourself

For an uncountable cardinal κ, use a language with constants cᵢ for i<κ and all pairwise distinctness axioms. Exhibit a model of size κ, prove that none is countable, and state the correct downward bound when a parameter set A is also retained.

Take a moment to make a prediction or work it out on paper. Open a hint when you need one.

Give me a hint

Interpret each constant by its own index. Count the required distinct interpretations before invoking a model-size theorem.

Compare with the solution

Take domain κ and interpret cᵢ as i; equality then satisfies every distinctness axiom. Any model contains at least κ elements because the constant interpretations form an injection of κ into its domain, so no countable model exists. With parameters A, the downward bound is $\max(|L|,|A|,\aleph_0)$ , and exact intermediate infinite sizes are available only up to the size of the original model. Here the uncountable signature itself blocks a countable conclusion.

Keep the idea

Take it with you

Compactness combines all finite satisfiability checks into one model-existence theorem.
Löwenheim–Skolem bounds include the language size and retained parameters.
Truth of all standard arithmetic sentences does not characterize the standard model up to isomorphism.

Read further

Original sources and deeper explanations to follow at your own pace.

Optional progress, saved in this browser when available. Revisit any lesson at any time.

Lesson not marked complete.