The Löwenheim–Skolem theorem

Theorem

The Löwenheim–Skolem theorem

T-128Home MU-403Threads logic

Statement

Let \(\mathcal{L}\) be a first-order language and let \(T\) be an \(\mathcal{L}\)-theory (a set of \(\mathcal{L}\)-sentences) which has an infinite model. Let \(\kappa\) be the cardinality of \(\mathcal{L}\), i.e. \(\kappa = \max(\aleph_0, |\mathcal{L}|)\) where \(|\mathcal{L}|\) is the number of non-logical symbols of \(\mathcal{L}\). Then: (Downward) if \(M \models T\) and \(X \subseteq M\) with \(\kappa \le |X|\le|M|\), there is an elementary substructure \(N \preceq M\) with \(X \subseteq N\) and \(|N| = |X|\); in particular \(T\) has a model of every infinite cardinality \(\lambda\) with \(\kappa \le \lambda \le |M|\). (Upward) if \(M \models T\) is infinite, then for every cardinal \(\lambda \ge |M|\) (and \(\lambda \ge \kappa\)) there is a model \(M' \models T\) with \(M \preceq M'\) and \(|M'| = \lambda\). Consequently \(T\) has models of every infinite cardinality \(\ge \kappa\).

Why it matters

The Löwenheim–Skolem theorem is the first great structural limitation theorem of model theory: it shows that no set of first-order sentences in a countable language can pin down a unique infinite structure up to isomorphism, because if it has one infinite model it has models of every infinite size. This immediately kills any hope of a first-order axiomatisation that is categorical for an infinite structure (Peano arithmetic, the reals as an ordered field, ZFC itself), and it is the engine behind Skolem's Paradox: a countable model of ZFC "contains" (in the sense of satisfying the internal formula) an uncountable set, viewed from outside as merely countable.

Beyond the philosophical shock value, the downward direction is a genuine everyday tool: it lets you replace an unwieldy large structure by a small elementary substructure that reflects exactly the same first-order truths, which is the starting point of many compactness-and-elementary-submodel arguments in algebra (e.g. constructing generic/countable elementarily equivalent copies) and in set theory (elementary submodels of \(H_\theta\)).

Hypotheses

The language \(\mathcal{L}\) is first-order (finitary, with the usual semantics of \(\forall,\exists\) ranging over elements, not subsets or relations). In second-order logic with full semantics, "the ordered field of reals" and "the standard model of arithmetic" ARE categorical — second-order Peano arithmetic has no non-standard models — so downward/upward Löwenheim–Skolem simply fails for second-order logic with standard semantics.

\(T\) has at least one infinite model (equivalently, admits arbitrarily large finite models, by the standard compactness argument). Drop this and the theorem is vacuous or false as stated: the theory "there are exactly 5 elements" has only finite models, all of the same size 5, and plainly has no model of size \(\aleph_0\).

The target cardinality \(\lambda\) satisfies \(\lambda \ge \kappa = |\mathcal{L}|\) (downward) or is compared against the source model's size (upward as stated). If \(\mathcal{L}\) has uncountably many constants \(c_i\), \(i \lt \omega_1\), and \(T\) asserts they are pairwise distinct, \(T\) cannot have a countable model, so downward Löwenheim–Skolem to cardinality \(\aleph_0\) fails when \(\lambda \lt \kappa\); the theorem's hypothesis \(\lambda \ge \kappa\) is not decorative.

The Axiom of Choice (or at least a suitable choice principle) is available in the metatheory, since the proof enumerates Skolem functions and closes off a set under countably (or \(\kappa\)-many) applications, an argument that uses countable/dependent choice at least. Without any choice at all, one can construct (in ZF) models of pathological theories where a definable well-ordering of the required Skolem hull fails to exist, and the naive closure construction cannot be carried out; the theorem is normally stated and proved in ZFC.

Proof

We prove the downward form first, via Skolem functions and the Tarski–Vaught test; the upward form then follows from compactness.

\text{Expand } \mathcal{L} \text{ to } \mathcal{L}^{Sk} \text{ by adding, for each formula } \varphi(x,\bar y) \text{ of } \mathcal{L}^{Sk}, \text{ a new function symbol } f_\varphi(\bar y).

Definition of a Skolem expansion: we build \(\mathcal{L}^{Sk} = \bigcup_n \mathcal{L}_n\) where \(\mathcal{L}_0 = \mathcal{L}\) and \(\mathcal{L}_{n+1}\) adds one Skolem symbol per \(\mathcal{L}_n\)-formula \(\varphi(x,\bar y)\); this recursion has length \(\omega\), and \(|\mathcal{L}^{Sk}| = |\mathcal{L}| \cdot \aleph_0 = \kappa\) since each stage adds at most \(\kappa\) new symbols (there are \(\kappa\) formulas at each finite stage, as \(\mathcal{L}_n\) has \(\kappa\) symbols and formulas are finite strings). B

M \models T \ \Rightarrow\ M \text{ expands to an } \mathcal{L}^{Sk}\text{-structure } M^{Sk} \models T^{Sk}

For each new symbol \(f_\varphi(\bar y)\), interpret \(f_\varphi^M(\bar a)\) as any \(b \in M\) with \(M \models \varphi(b,\bar a)\) if such \(b\) exists (choice, applied to the nonempty family of witness-sets indexed by \(\bar a \in M^{|\bar y|}\), of which there are at most \(|M|\)), and arbitrarily otherwise; \(T^{Sk}\) is \(T\) together with the Skolem axioms \(\forall \bar y\,(\exists x\,\varphi(x,\bar y) \to \varphi(f_\varphi(\bar y),\bar y))\), which hold in \(M^{Sk}\) by construction. B

A(X) := \text{closure of } X \text{ under all Skolem functions } f_\varphi,\quad |A(X)| \le |X| + \kappa

Build \(A(X) = \bigcup_{n\lt\omega} X_n\) with \(X_0 = X\) and \(X_{n+1} = X_n \cup \{f_\varphi^M(\bar a) : \varphi \text{ a Skolem-indexed formula}, \bar a \in X_n^{\lt\omega}\}\); at each stage the number of new elements added is at most \(\kappa \cdot |X_n|^{\lt\omega} = \kappa \cdot |X_n|\) (since \(|X_n| \ge \aleph_0\) once \(X\) is infinite, or we simply bound by \(\kappa\) if \(X\) finite but recall \(\kappa \ge \aleph_0\)), so by induction \(|X_n| \le \max(|X|,\kappa)\) for all \(n\), and \(|A(X)| = |\bigcup_n X_n| \le \aleph_0 \cdot \max(|X|,\kappa) = \max(|X|,\kappa)\). Since \(|X|\ge\kappa\) by hypothesis, \(|A(X)| = |X|\) (using \(|A(X)|\ge|X|\) trivially and Cantor–Schröder–Bernstein). C

A(X) \text{ is closed under every Skolem function, hence } A(X)^{Sk} \preceq M^{Sk}

By the Tarski–Vaught test, a substructure \(N \subseteq M^{Sk}\) satisfies \(N \preceq M^{Sk}\) iff for every \(\mathcal{L}^{Sk}\)-formula \(\varphi(x,\bar y)\) and every \(\bar a \in N\), if \(M^{Sk} \models \exists x\, \varphi(x,\bar a)\) then some witness \(b \in N\) satisfies \(M^{Sk}\models \varphi(b,\bar a)\). Take \(b = f_\varphi^{M}(\bar a) \in A(X)\) by closure (step 3); by the Skolem axiom this \(b\) is exactly such a witness. So the test is met for every formula and every tuple, giving elementarity. B

N := A(X)^{Sk}\restriction \mathcal{L} \ \Rightarrow\ N \preceq M \text{ (as }\mathcal{L}\text{-structures), } X\subseteq N,\ |N|=|X|

Reducts of elementarily equivalent/elementary-submodel pairs to a sublanguage preserve the elementary submodel relation: if \(A(X)^{Sk} \preceq M^{Sk}\) then for any \(\mathcal{L}\)-formula \(\psi\) (a fortiori an \(\mathcal{L}^{Sk}\)-formula) and \(\bar a \in N\), \(N \models \psi(\bar a) \iff A(X)^{Sk}\models\psi(\bar a) \iff M^{Sk}\models\psi(\bar a) \iff M \models \psi(\bar a)\), which is exactly \(N \preceq M\) in \(\mathcal{L}\). Cardinality and containment of \(X\) carry over unchanged from step 3 since the reduct has the same underlying set. This proves the Downward Löwenheim–Skolem–Tarski theorem in full generality. C

\text{Applying step 5 with } X \subseteq M,\ |X|=\lambda \text{ gives a model of } T \text{ of size } \lambda \text{ for every } \kappa\le\lambda\le|M|

Since \(M\) is infinite, for any cardinal \(\lambda\) with \(\kappa\le\lambda\le|M|\) we may pick \(X\subseteq M\) of size \(\lambda\) (possible as \(\lambda \le |M|\)); the resulting \(N\preceq M\) satisfies \(N\models T\) because \(M\models T\) and \(T\subseteq \mathcal{L}\)-sentences are preserved downward along \(\preceq\) (elementarity is truth-preservation for all formulas, sentences in particular). This completes downward Löwenheim–Skolem. A

\text{Upward: for } \lambda \ge |M| \text{ (and } \lambda\ge\kappa\text{), add } \lambda \text{ fresh constants } \{c_i : i\lt\lambda\} \text{ to } \mathcal{L}, \text{ and let } T' = T \cup \mathrm{Diag}_{el}(M) \cup \{c_i \ne c_j : i\ne j\}

\(\mathrm{Diag}_{el}(M)\) is the elementary diagram of \(M\): all \(\mathcal{L}_M\)-sentences (\(\mathcal{L}\) with a name for each element of \(M\)) true in \(M\); by definition any model of \(\mathrm{Diag}_{el}(M)\) is (isomorphic to an) elementary extension of \(M\), a standard fact of model theory (the Elementary Diagram Lemma). B

T' \text{ is finitely satisfiable}

Any finite subset \(T_0 \subseteq T'\) mentions only finitely many of the \(c_i\), say \(c_{i_1},\dots,c_{i_n}\); since \(M\) is infinite we may interpret these as \(n\) distinct elements of \(M\), and interpret every other new constant \(c_i\) (\(i\) not among the \(i_k\)) as any element of \(M\) not equal to those chosen — possible because \(M\) is infinite, so \(M\) itself (suitably expanded) models \(T_0\), using that \(\mathrm{Diag}_{el}(M)\) and \(T\) already hold of \(M\). B

\text{By Compactness, } T' \text{ has a model } M''.\text{ Let } M' \text{ be its } \mathcal{L}\text{-reduct; then } M \preceq M' \models T

Compactness Theorem for first-order logic: a theory is satisfiable iff every finite subfragment is. Since \(M''\models \mathrm{Diag}_{el}(M)\), the Elementary Diagram Lemma gives an elementary embedding \(M \preceq M'' \restriction \mathcal{L}_M \cong\) (identifying \(M\) with its image) so \(M \preceq M'\); and \(M' \models T\) since \(T\subseteq T'\). B

|M'| \ge \lambda \text{ (the } \lambda \text{ distinct interpretations of } c_i\text{), and } |M'|\le \lambda

Lower bound: the sentences \(c_i \ne c_j\) force \(\lambda\)-many distinct elements. Upper bound: a standard cardinality count on the compactness/Henkin construction of \(M''\) shows \(|M''|\) can be taken equal to \(|\mathcal{L}_M \cup \{c_i:i\lt\lambda\}| = \max(|M|,\kappa,\lambda)=\lambda\) (using \(\lambda\ge|M|,\kappa\)); formally one runs downward Löwenheim–Skolem (steps 1–6) inside \(M''\) over the set \(M\cup\{c_i^{M''}:i\lt\lambda\}\), of size \(\lambda\), to trim \(M''\) down to exactly size \(\lambda\) while preserving \(M\preceq M'\) and the distinctness sentences (this trimmed submodel still contains all named elements, since the Skolem hull of a set contains the set). By Cantor–Schröder–Bernstein, \(|M'|=\lambda\). C

Result

T \text{ has an infinite model} \ \Longrightarrow\ T \text{ has a model of every infinite cardinality } \ge |\mathcal{L}|

Reading. A first-order theory cannot control the size of its infinite models: as soon as it has one, it has ones of literally every infinite size from the size of its own vocabulary upward. Size is not a first-order-expressible property of infinite structures.

Scope. Applies to any first-order theory in classical (finitary, two-valued) logic; the downward part gives elementary submodels of any given infinite model down to size \(\max(\aleph_0,|\mathcal{L}|)\), the upward part gives elementary extensions up to any larger cardinality. Fails outright for second-order logic with standard (full) semantics, and the specific bound \(\kappa=|\mathcal{L}|\) is sharp.

Corollaries & converses

No first-order theory in a countable language is categorical in any infinite cardinality unless it is categorical in all infinite cardinalities \(\ge \aleph_0\) is false to hope for; more precisely, categoricity in one infinite power says nothing about categoricity in another (Łoś–Vaught test uses exactly this asymmetry) — but a theory categorical in *some* uncountable power that has no finite models is complete (Łoś–Vaught test), a genuine free corollary of the theorem's machinery.
Peano Arithmetic, ZFC, and the first-order theory of real closed fields all have countable models (downward) and models of every uncountable cardinality (upward); in particular ZFC, if consistent, has a countable model — Skolem's Paradox.
Every infinite structure \(M\) in a countable language has a countable elementary substructure; this is the standard source of "countable elementary submodels" arguments in algebra and analysis.
Converse-type statement: is every cardinal \(\ge\kappa\) achieved by an infinite-model theory actually necessary, i.e. can a theory have infinite models of cardinalities \(\kappa\) and \(\lambda\) but skip some cardinal in between or above? No — the theorem says every such cardinal is achieved, so there is no "gap" converse to state; the real converse question ("must every infinite-model theory have models of arbitrarily large size?") is precisely what the upward theorem asserts, so the statement is in this sense self-converse and there is no separate weaker version that fails.
The theorem does NOT say the models of different cardinalities are isomorphic or even elementarily distinguishable from each other beyond \(T\) — many pairwise non-isomorphic models of \(T\) can share a cardinality too.

Fails without

Finitary first-order logic: in second-order logic with standard semantics, the Peano axioms (second-order induction schema as a single second-order sentence) are categorical — pin down \((\mathbb{N},0,S,+,\times)\) up to isomorphism — so there is no countable-language second-order theory with an infinite model that also has models of every infinite size; Löwenheim–Skolem is a genuinely first-order phenomenon.
An infinite model existing at all: \(T = \{\exists^{=5}x\, (x=x)\}\) ("there are exactly 5 elements", expressible by a single first-order sentence) has models only of size 5; it trivially has no infinite model, and correspondingly no model of size \(\aleph_0\) or anything else — the hypothesis "T has an infinite model" cannot be weakened to "T has arbitrarily large finite models" for the conclusion about size \(\aleph_0\) itself, though note by compactness the latter *does* imply the former, so this is really the same hypothesis in disguise; the genuine failure case is theories all of whose models are bounded in size, e.g. \(T=\{\exists^{=5}x\,(x=x)\}\).
\(\lambda \ge \kappa=|\mathcal{L}|\) in the downward direction: let \(\mathcal{L}\) have uncountably many constants \(\{c_i : i\lt\omega_1\}\) and \(T=\{c_i\ne c_j : i\ne j\}\); every model of \(T\) has size \(\ge\aleph_1=\kappa\), so there is no model of size \(\aleph_0\lt\kappa\), showing downward Löwenheim–Skolem cannot be pushed below the language's own cardinality.
Choice-free ZF in the metatheory: the Skolem-hull construction and elementary-diagram compactness argument both implicitly well-order countable unions of choices; in models of ZF where countable choice fails badly, one can build first-order theories whose "hull" constructions do not close off into a set of the claimed cardinality, so the clean cardinal arithmetic \(|A(X)|=|X|\) of step 3 can break down.

Common errors

Thinking the theorem gives a model of every size \(\le|M|\) *isomorphic* to a substructure of \(M\) in the naive sense — it gives an elementary substructure, which is much stronger and is exactly why the Tarski–Vaught test is needed; an arbitrary small subset closed under nothing need not even be a substructure, let alone elementary.
Concluding from the countable model of ZFC (Skolem's Paradox) that ZFC is inconsistent, or that "countable" is not really meaningful — the resolution is that "\(x\) is uncountable" inside the countable model is a genuinely true internal first-order statement, because the bijection witnessing countability from the *outside* is simply not an element of the model; \(\preceq\) preserves truth of formulas, not existence of arbitrary external functions.
Applying the theorem to second-order theories (e.g. "second-order PA has a countable model too") — it does not apply; second-order logic with full semantics is not first-order and the compactness/completeness machinery the proof relies on (steps 7–9) simply is not available there.
Forgetting the lower bound \(\kappa=|\mathcal{L}|\) and claiming, e.g., that a theory in a language with continuum-many constants must have a countable model — it need not, as the counterexample in "Fails without" shows.
Conflating "has a model of size \(\lambda\)" with "is categorical in size \(\lambda\)" — Löwenheim–Skolem says nothing about uniqueness of the model at a given cardinality, only existence.

Discussion

The theorem was assembled in stages: Löwenheim (1915) proved the countable case (a satisfiable countable-language sentence has a countable model) using an early, non-fully-rigorous combinatorial argument; Skolem (1920, 1922) reproved and sharpened it using explicit Skolem functions — the very device used in the proof above — and, crucially, drew out the paradoxical consequence for set theory that now bears his name. The upward extension and the general cardinal-arithmetic version are due to Tarski and Vaught in the 1950s, whose elementary-submodel test (step 4) turned the whole subject into a systematic technique rather than a one-off trick.

Skolem himself regarded the countable-model result for set theory as evidence that "set" and "uncountable" are not absolute notions but relative to the model one is reasoning in — a genuinely early instance of what became a guiding theme of modern set theory (forcing, inner models, absoluteness). The paradox dissolves once one is careful about the distinction between a model satisfying "there is no bijection between \(A\) and \(\omega\)" and there actually being no such bijection in the full set-theoretic universe: the countable model of ZFC is simply missing the bijection, even though (from outside) one exists.

Model-theoretically, the pair of theorems delimits exactly what a first-order theory can and cannot control about the cardinality of its models, and this is what makes categoricity in a single infinite power such a strong and useful hypothesis — Morley's Categoricity Theorem (a countable first-order theory categorical in one uncountable cardinality is categorical in all uncountable cardinalities) is a deep converse-flavoured refinement that only makes sense because Löwenheim–Skolem has already told us categoricity can never hold simultaneously across *all* infinite cardinalities including \(\aleph_0\) for a theory with any nontrivial infinite structure of size \(\gt\aleph_0\) around.

A subtler point: the downward theorem is often mis-stated as merely "every infinite model has a countable elementary submodel." That special case (\(\lambda=\aleph_0\), \(\mathcal{L}\) countable) is the most quoted, but the general Tarski–Vaught form is considerably sharper — it lets you *prescribe* a target subset \(X\) to be contained in the elementary submodel, which is exactly the extra strength needed for elementary-submodel arguments in algebra (e.g., building a countable elementary submodel of \(\mathbb{C}\) containing a given finite list of "interesting" elements) and in combinatorial set theory (elementary submodels of \(H_\theta\) containing a prescribed real or ordinal).

Worked examples

\text{Show: the theory RCF of real closed fields has a countable model, and hence } \mathbb{R} \text{ is not first-order-definable up to isomorphism among real closed fields of its own size by "being } \mathbb{R}\text{".}

RCF is a first-order theory (ordered field axioms + intermediate value property schema for polynomials + every positive element has a square root) in the countable language \(\{+,\times,\lt,0,1\}\), so \(\kappa=\aleph_0\). A

\mathbb{R} \models \mathrm{RCF}, \quad |\mathbb{R}| = 2^{\aleph_0} \gt \aleph_0 = \kappa

\(\mathbb{R}\) is a standard model of RCF (Tarski's theorem that RCF axiomatises the first-order theory of \(\mathbb{R}\)); it is infinite, so the theorem's hypotheses hold with \(M=\mathbb{R}\). A

\text{By Downward L\ddot{o}wenheim–Skolem (steps 1–6) with } X\subseteq\mathbb{R},\ |X|=\aleph_0,\ \text{take } N \preceq \mathbb{R},\ |N|=\aleph_0

\(\kappa=\aleph_0 \le \aleph_0 \le |\mathbb{R}|\), so the theorem applies directly; e.g. take \(X=\mathbb{Q}\), the real algebraic numbers, or any countable dense subset — the resulting \(N\) will contain it and be elementarily equivalent to \(\mathbb{R}\) as an ordered field. B

N \models \mathrm{RCF}, \quad N \not\cong \mathbb{R} \text{ (cardinality)}, \quad N \equiv \mathbb{R} \text{ (elementary equivalence, in fact } N\preceq\mathbb{R}\text{)}

\(N\) is a countable real closed field (e.g. the field of real algebraic numbers is one natural witness, though the theorem produces one abstractly without needing to identify it), literally satisfying the same first-order sentences as \(\mathbb{R}\) — including "every polynomial of odd degree has a root," "the ordering is dense," etc. — yet it cannot even be put in bijection with \(\mathbb{R}\). A

\text{RCF has a countable model } N \prec \mathbb{R}, \text{ so no first-order sentence of RCF can single out } \mathbb{R} \text{ by cardinality}

Reading. Completeness (in the order-theoretic, Dedekind sense) is not a first-order property; RCF captures the algebraic/order behaviour of \(\mathbb{R}\) perfectly but is satisfied by strictly smaller structures too.

\text{Show: ZFC, if consistent, has a countable model (Skolem's Paradox), and explain why this is not a contradiction.}

ZFC is a first-order theory in the countable language \(\{\in\}\), so \(\kappa=\aleph_0\). A

\text{Assume ZFC is consistent} \Rightarrow \text{ZFC has a model } M \text{ (Completeness Theorem)}

Gödel's Completeness Theorem: a consistent first-order theory has a model. \(M\) is necessarily infinite since ZFC proves the existence of an infinite set (Axiom of Infinity). A

\text{By Downward L\ddot{o}wenheim–Skolem with } X=\varnothing \text{ (or any countable } X\subseteq M\text{),} \ \exists\, N\preceq M,\ |N|=\aleph_0

\(\kappa=\aleph_0\le\aleph_0\le|M|\), theorem applies; \(N\preceq M\) so \(N\models\) every sentence \(M\) satisfies, in particular \(N\models\mathrm{ZFC}\) since \(\mathrm{ZFC}\subseteq\) the sentences true in \(M\). B

N \models \text{``}\mathbb{R}\text{ (as internally constructed) is uncountable''}, \quad \text{yet } |N|=\aleph_0 \text{ from outside}

ZFC proves Cantor's theorem "there is no surjection from \(\omega\) onto \(\mathcal{P}(\omega)\)"; \(N\) models this internally, i.e. \(N\models\neg\exists f\,(f:\omega\twoheadrightarrow\mathcal{P}(\omega)^N)\). No contradiction with \(|N|=\aleph_0\) arises because the witnessing bijection between \(N\) and \(\omega\) (which exists in the ambient metatheory, by \(N\) countable) is simply not an element of \(N\) itself — non-absoluteness of "there exists a bijection" between \(N\) and its metatheoretic universe. C

\text{ZFC (if consistent) has a countable model } N; \ N\models \text{``}\mathcal{P}(\omega)^N\text{ is uncountable''} \text{ while } |N|=\aleph_0 \text{ externally}

Reading. "Countable" and "uncountable" are not absolute properties of a set but relative to which bijections the surrounding model happens to contain — the countable model is simply missing the bijection that would witness its internal \(\mathcal{P}(\omega)\) as countable.

Problems

State precisely why the theory \(T=\{\forall x\,\forall y\,(x=y)\}\) ("there is exactly one element") does not contradict Löwenheim–Skolem despite having only one model up to isomorphism.
Solution
\(T\)'s only models have exactly 1 element — \(T\) has no infinite model at all, so the hypothesis of Löwenheim–Skolem ("\(T\) has an infinite model") is simply not satisfied, and the theorem makes no claim about \(T\). There is no contradiction because the theorem is a conditional statement whose antecedent fails here.
Let \(\mathcal{L}=\{+,\times,0,1,\lt\}\) (countable) and let \(T\) be the first-order theory of \((\mathbb{N},+,\times,0,1,\lt)\) (true arithmetic). Does downward Löwenheim–Skolem give a countable model of \(T\) different from \(\mathbb{N}\) itself, and if so is it isomorphic to \(\mathbb{N}\)?
Solution
Yes: since \(\mathcal{L}\) is countable and \(\mathbb{N}\) is an infinite model of \(T\), downward Löwenheim–Skolem with \(X=\mathbb{N}\) (or any countably infinite subset) yields a countable \(N\preceq \mathbb{N}\), but this merely reproduces \(\mathbb{N}\) itself up to isomorphism if we take \(X=\mathbb{N}\), since \(N\) elementarily closed and containing all of \(\mathbb{N}\) must equal \(\mathbb{N}\). To get a *genuinely different* countable model one instead uses the Upward theorem plus compactness: adjoin a new constant \(c\) with axioms \(c\gt \underline n\) for every numeral \(\underline n\), get a model \(M'\gt\mathbb{N}\) with a nonstandard element, then apply downward Löwenheim–Skolem inside \(M'\) to shrink back to a countable model containing that nonstandard element — this countable model is elementarily equivalent to \(\mathbb{N}\) (models the same true arithmetic sentences) but NOT isomorphic to \(\mathbb{N}\) (it has a nonstandard/non-well-founded-order element), by Tennenbaum-type non-standard model theory. So: downward Löwenheim–Skolem alone (applied to \(\mathbb{N}\) itself) does not produce a non-isomorphic countable model; one needs the upward-then-downward combination.
A student claims: "since ZFC has a countable model \(N\) by Löwenheim–Skolem, and ZFC proves \(\mathcal{P}(\omega)\) is uncountable, ZFC must be inconsistent." Identify the exact logical error.
Solution
The error conflates the metatheoretic statement "\(N\) has only countably many elements" (a fact about \(N\) viewed from outside, using a bijection \(f:\omega\to N\) that lives in the ambient set theory) with the internal statement "\(N \models \exists g\,(g:\omega \to \mathcal{P}(\omega)^N \text{ is a surjection})\)". These are different claims about different objects/functions, and there is no requirement that the external bijection \(f\) be an element of \(N\) itself. \(N\) correctly proves (internally) that no *element of \(N\)* witnesses a bijection between \(\omega^N\) and \(\mathcal{P}(\omega)^N\); it says nothing about bijections that exist only outside \(N\). No inconsistency follows.
Prove directly (without quoting the general theorem) that the theory of dense linear orders without endpoints (DLO), which is complete, has a model of cardinality \(\aleph_1\), given that \((\mathbb{Q},\lt)\models\mathrm{DLO}\) is countable.
Solution
DLO is in the countable language \(\{\lt\}\), so \(\kappa=\aleph_0\), and \((\mathbb{Q},\lt)\) is an infinite model, so upward Löwenheim–Skolem (steps 7–10) applies with \(\lambda=\aleph_1\ge|\mathbb{Q}|=\aleph_0\): add \(\aleph_1\) fresh constants \(c_i\), form \(T' = \mathrm{Diag}_{el}(\mathbb{Q}) \cup \{c_i\ne c_j:i\ne j\}\), check finite satisfiability (any finite subset only mentions finitely many \(c_i\), interpretable as distinct rationals since \(\mathbb{Q}\) is infinite), apply Compactness to get a model \(M''\), whose \(\{\lt\}\)-reduct trimmed by downward Löwenheim–Skolem to the \(\aleph_1\)-sized set \(\mathbb{Q}\cup\{c_i^{M''}\}\) gives \(M'\models\mathrm{DLO}\) with \(|M'|=\aleph_1\), e.g. concretely realisable as the order type of \(\mathbb{Q}\times\eta\)-like constructions, though the abstract argument suffices without exhibiting one.
Explain, using the theorem, why no first-order theory (in a countable language) can axiomatise the class of finite groups (i.e., have exactly the finite groups, and no infinite ones, as its models), assuming that class is closed under a natural notion of "arbitrarily large finite models."
Solution
Suppose \(T\) is a first-order theory whose models are exactly the finite groups, and suppose (as given) finite groups of arbitrarily large size exist among its models. Consider \(T\) together with, for each \(n\), the sentence \(\sigma_n\) asserting "there are at least \(n\) elements" (definable in pure first-order logic with just \(=\)). Every finite subset of \(T\cup\{\sigma_n : n\lt\omega\}\) mentions only finitely many \(\sigma_n\), and is satisfiable by a sufficiently large finite group from \(T\)'s models (using the arbitrarily-large-models hypothesis). By Compactness, \(T\cup\{\sigma_n:n\lt\omega\}\) is satisfiable, giving a model \(M\) of \(T\) satisfying every \(\sigma_n\), hence \(M\) is infinite. But \(M\models T\) and \(T\)'s models are supposed to be exactly the finite groups — contradiction. (This uses Compactness rather than Löwenheim–Skolem directly, but it is the same phenomenon: first-order theories cannot control finiteness, and this "arbitrarily large finite models force an infinite model" fact is precisely the hypothesis-generating step that feeds into Löwenheim–Skolem, e.g. once you have that infinite model you then get models of every infinite cardinality too, compounding the non-axiomatisability.)