42.01.07 · mathematical-logic / first-order-logic-completeness

Compactness and the Löwenheim-Skolem Theorems for First-Order Logic

shipped3 tiersLean: none

Anchor (Master): Enderton 2001 §2.6; Chang and Keisler 1990 *Model Theory* 3e (North-Holland) Ch. 1-2 (compactness via the completeness theorem and via the ultraproduct/Łoś construction, the Löwenheim-Skolem-Tarski theorem in full, the method of constants, elementary chains); Marker 2002 *Model Theory: An Introduction* (Springer GTM 217) Ch. 2 (compactness, Löwenheim-Skolem, the Tarski-Vaught test, the failure of first-order categoricity, non-standard models); Hodges 1993 *Model Theory* (Cambridge) Ch. 5-6 (downward and upward Löwenheim-Skolem, Skolem functions and Skolem hulls); Lindström 1969 *On extensions of elementary logic* (Theoria 35) (the maximality of first-order logic among logics with countable compactness and downward Löwenheim-Skolem); Robinson 1966 *Non-standard Analysis* (North-Holland) Ch. 1-3 (the hyperreals as a non-standard model of the reals)

Intuition Beginner

The previous unit settled a remarkable match: a batch of assumptions has a world making them all true exactly when the proof game cannot grind a contradiction out of them, and that game only ever touches finitely many assumptions at a time. Put those two facts side by side and a slogan drops out. A batch of demands can be satisfied all at once whenever every finite handful of them can be. Failure, if it happens, must already show up in some finite handful. This is the compactness theorem, now for the richer language that says "for all" and "there exists." It is far stronger than the switch-flipping version, since the demands can talk about numbers, orders, and structures.

The power shows up the moment you feed it a sneaky infinite list. Start with everything true about ordinary counting numbers. Add one new name, call it $c$ , and pile on the endless demands " $c$ is bigger than $1$ ," " $c$ is bigger than $2$ ," and so on forever. Any finite handful is easy: just let $c$ be a big enough ordinary number. So compactness hands you a single world satisfying the whole infinite list. In that world $c$ is bigger than every ordinary number — an infinite number sitting past all the familiar ones. The counting numbers, in this language, could never keep such intruders out.

Two more surprises follow the same way. A world you can pin down in words can always be shrunk to one with only countably many things in it, yet that shrunken world can still insist some of its own collections are too big to count. The next sections make "demand," "world," and "shrink" precise and prove these promises.

Visual Beginner

The picture is a number line that has grown an extra tail. The ordinary counting numbers sit at the start in their usual order. Compactness forces a new point $c$ that lies past every one of them, and once one such point exists, a whole block of new points appears around it.

   FORCING A NUMBER BIGGER THAN ALL THE ORDINARY ONES

   demands (every finite handful is easy to meet):
        c > 1 ,  c > 2 ,  c > 3 ,  c > 4 ,  ...   (never ends)

   finite handful  { c > 1, c > 2, c > 3 } :
        let  c = 100   ->  all three hold     ->  satisfiable

   so by compactness the WHOLE list has one world:

      ordinary numbers                    new infinite numbers
      0   1   2   3   4   ...   ............   ...  c-1   c   c+1  ...
      |---|---|---|---|----            ----|----|---|---|---
       the familiar start            a tail past every ordinary number

   RESULT  a single world where c sits beyond all of 0,1,2,3,...
           yet every ordinary true statement still holds.

Read it left to right. Each finite handful of "bigger than" demands is met by choosing a large enough ordinary number, so no finite handful ever clashes. Because every finite handful is satisfiable, compactness gives one world meeting all of them at once, and in that world $c$ has no ordinary size — it is an infinite number.

ingredient	what it is	role
the old truths	everything true of counting	kept intact
the new name $c$	one extra constant	the intruder
the endless demands	" $c$ bigger than each number"	force the tail
each finite handful	finitely many "bigger than"	met by a big ordinary number

Nothing about ordinary arithmetic is broken; the world simply has more numbers than you bargained for, because finitely-checkable demands could not forbid them.

Worked example Beginner

We force a single infinite number into a world and watch finite-checking do all the work. Keep every true fact about ordinary counting numbers, where each number has a name: $0$ , then $1$ , then $2$ , and so on. Add one fresh name $c$ . Then add the endless list of demands $D_{1} :$ " $c$ is bigger than $0$ ," $D_{2} :$ " $c$ is bigger than $1$ ," $D_{3} :$ " $c$ is bigger than $2$ ," continuing forever.

Step 1. Pick any finite handful of these demands. Say we grab $D_{1}, D_{2}, D_{3}, D_{4}, D_{5}$ — the demands " $c$ bigger than $0$ " up through " $c$ bigger than $4$ ." There are five of them.

Step 2. Satisfy that handful inside the ordinary numbers. Let $c$ name the number $5$ . Then $5$ is bigger than $0, 1, 2, 3$ , and $4$ , so all five demands in the handful hold at once. Every true fact about ordinary counting still holds too, since we changed nothing except the meaning of the new name $c$ .

Step 3. Notice this always works. Whatever finite handful you grab, it mentions a largest number, say $N$ . Letting $c$ name $N + 1$ meets every demand in that handful, because $N + 1$ is bigger than $0, 1, \dots, N$ . So every finite handful is satisfiable.

Step 4. Apply compactness. Since every finite handful of the whole infinite list is satisfiable, the entire list has one world that satisfies all of it together. Call this world $M$ .

Step 5. Inspect $c$ in $M$ . The name $c$ must satisfy all the demands at once: $c$ is bigger than $0$ , bigger than $1$ , bigger than $2$ , and so on without end. So in $M$ the object named $c$ is larger than every ordinary number. It is a number with no ordinary size — an infinite number.

What this tells us: by checking only finite handfuls, each met by a big enough ordinary number, we conjured a world containing a number past all the ordinary ones, while every ordinary truth survived. No finite handful could rule the intruder out, so the infinite list could not either. The next sections turn "keep the truths, add a constant beyond every numeral" into the precise compactness argument and its consequences.

Check your understanding Beginner

Exercise (easy, multiple choice).

Why is every finite handful of the demands " $c$ bigger than $0$ ," " $c$ bigger than $1$ ," " $c$ bigger than $2$ ," … satisfiable inside the ordinary numbers?

A. Because the whole infinite list is satisfiable, so each handful must be too.

B. Because a finite handful mentions a largest number $N$ , and letting $c$ name $N + 1$ meets every demand in it.

C. Because $c$ is already an infinite number from the start.

D. Because the ordinary numbers have a biggest element.

Hint

A finite handful only asks $c$ to beat finitely many numbers. What is the largest one it names?

Answer

B. A finite handful names finitely many numbers and so has a largest one, $N$ ; choosing $c$ to be $N + 1$ beats every number in the handful at once. Feedback-correct: finite-checking is easy precisely because each handful has a top number to beat. Feedback-wrong: A reverses the logic (we use the handfuls to get the whole list, not the other way around); C is false before compactness acts; D is false, the counting numbers have no biggest element.

Formal definition Intermediate+

Fix a first-order language $L$ with equality, the satisfaction relation $⊨$ of 42.01.04 pending, the deductive calculus and consistency of 42.01.05 pending, and the completeness theorem of 42.01.06 pending in its model-existence form: every consistent set of sentences has a model. A theory is a set $T$ of $L$ -sentences; $T$ is satisfiable when some structure $A ⊨ T$ , and finitely satisfiable when every finite $T_{0} \subseteq T$ is satisfiable ^{[Enderton §2.6]}.

Compactness theorem (first-order). A set $Γ$ of $L$ -sentences has a model if and only if every finite subset of $Γ$ has a model.

One direction is monotone: a model of $Γ$ models each finite subset. The substance is the converse, and it is a corollary of completeness. If $Γ$ has no model then by completeness $Γ$ is inconsistent, so $Γ ⊢ β$ and $Γ ⊢ \neg β$ for some $β$ ; each deduction cites finitely many premises, so a finite $Γ_{0} \subseteq Γ$ proves both, is inconsistent, and by soundness 42.01.05 pending has no model. Contrapositively, finite satisfiability gives satisfiability. The whole content is the finiteness of deductions transported across $⊢ = ⊨$ ; the propositional case 42.01.02 pending is the same skeleton over truth values, but the first-order harvest is incomparably richer.

For two structures $A \subseteq B$ in the same language ( $A$ a substructure, with $∣ A ∣ \subseteq ∣ B ∣$ and the operations agreeing), $A$ is an elementary substructure, written $A ⪯ B$ , when for every formula $φ (x_{1}, \dots, x_{n})$ and tuple $\overset{a}{ˉ}$ from $∣ A ∣$ , $A ⊨ φ [\overset{a}{ˉ}] \Leftrightarrow B ⊨ φ [\overset{a}{ˉ}]$ . The Tarski-Vaught test characterizes this: $A ⪯ B$ iff $A \subseteq B$ and for every formula $φ (\overset{x}{ˉ}, y)$ and $\overset{a}{ˉ}$ from $∣ A ∣$ , whenever $B ⊨ \exists y φ [\overset{a}{ˉ}, y]$ there is a witness $b \in ∣ A ∣$ with $B ⊨ φ [\overset{a}{ˉ}, b]$ ^{[Marker Ch. 2]}.

The downward Löwenheim-Skolem-Tarski theorem asserts that every infinite structure $B$ in a language of size $λ$ has, for each $X \subseteq ∣ B ∣$ , an elementary substructure $A ⪯ B$ with $X \subseteq ∣ A ∣$ and $∣ A ∣ \leq ∣ X ∣ + λ + ℵ_{0}$ . The upward Löwenheim-Skolem theorem asserts that a theory with an infinite model has a model of every cardinality $κ \geq λ + ℵ_{0}$ . A theory is categorical if all its models are isomorphic.

Counterexamples to common slips Intermediate+

"Compactness is just the propositional theorem in a bigger language." The skeleton is shared, but a propositional theory only ever constrains truth values, while a first-order theory constrains structures: the constant-adjunction trick yields non-standard models, infinite cardinalities, and infinitesimals, none of which the propositional case 42.01.02 pending can express.
"A consistent theory describing $N$ has only $N$ as a model." True arithmetic $Th (N)$ has non-standard models of every infinite cardinality. First-order axioms cannot exclude a constant placed above every numeral, so no infinite structure is pinned down up to isomorphism.
"An elementary substructure is the same as a substructure." The even numbers $(2 Z; +)$ form a substructure of $(Z; +)$ but not an elementary one once a constant for $2$ is present: " $\exists y (y + y = 2)$ " fails inside the evens (no witness) yet holds in $Z$ . Elementarity is the Tarski-Vaught witness condition, strictly stronger than closure under operations.
"Skolem's paradox shows set theory is inconsistent." It shows cardinality is not absolute. A countable model $M ⊨ ZF$ thinks some $x$ is uncountable because the bijection $N \to x$ that exists outside $M$ is not an element of $M$ ; internal and external counting diverge, with no contradiction.

Key theorem with proof Intermediate+

The signature consequence of compactness is the construction of non-standard models — structures satisfying exactly the same first-order sentences as a target yet not isomorphic to it. The argument is the constant-adjunction template in its cleanest form, and it is what no propositional compactness theorem can produce.

Theorem (non-standard models of arithmetic). Let $N = (N; 0, S, +, \cdot, <)$ be the standard model and $T = Th (N)$ its complete first-order theory. There is a model $M ⊨ T$ with an element $ν \in ∣ M ∣$ satisfying $ν > S^{n} 0$ for every $n \in N$ ; thus $M$ is elementarily equivalent to $N$ but not isomorphic to it ^{[Enderton §2.6]}.

Proof. Expand $L$ to $L^{*} = L \cup {c}$ with a new constant $c$ , and set $Γ = T \cup {c > S^{n} 0 : n \in N},$ where $S^{n} 0$ is the numeral $n S \dots S 0$ . Each finite $Γ_{0} \subseteq Γ$ uses only finitely many of the sentences $c > S^{n} 0$ , say for $n \leq N$ . Interpret $c$ in $N$ as the number $N + 1$ : then $N$ with this interpretation models $T$ (the sentences of $T$ do not mention $c$ ) and every $c > S^{n} 0$ for $n \leq N$ , so $N ⊨ Γ_{0}$ . Hence $Γ$ is finitely satisfiable, and by compactness $Γ$ has a model $M^{*}$ . Let $ν = c^{M^{*}}$ and let $M = M^{*} ↾ L$ be its reduct, forgetting $c$ . Then $M ⊨ T$ , and since $M^{*} ⊨ c > S^{n} 0$ for every $n$ , the element $ν$ exceeds every standard numeral's interpretation $S^{n} 0^{M}$ .

Because $T$ is complete, $M \equiv N$ (they satisfy the same sentences). They are not isomorphic: an isomorphism would send the interpretation of each numeral $S^{n} 0$ to itself and so could not accommodate $ν$ , which is the interpretation of no numeral, exceeding them all. The standard part ${S^{n} 0^{M} : n \in N}$ is a proper initial segment, and $ν$ lies strictly above it; $M$ is a non-standard model of true arithmetic. $□$

Corollary (downward Löwenheim-Skolem from the term model). Since $Γ$ above is countable, the Henkin term model of 42.01.06 pending has cardinality at most $∣ L^{*} ∣ + ℵ_{0} = ℵ_{0}$ , so $M$ may be taken countable: a countable non-standard model of arithmetic exists.

Bridge. The constant-adjunction argument is the foundational reason compactness has teeth a propositional theorem lacks: a single new constant plus an infinite-but-finitely-harmless batch of inequalities manufactures an element with no standard size, and this is exactly the completeness theorem of 42.01.06 pending read forward — consistency of every finite fragment delivers one model of the whole. It builds toward the upward and downward Löwenheim-Skolem theorems, which run the same template to scale cardinality up and down, and it appears again in the hyperreals and in model theory 42.02.01 pending, where the method of diagrams turns any consistent expansion into an elementary extension. The central insight is that first-order axioms see only finitely many premises at a time, so they cannot fence off a limit they never inspect; this is exactly why $Th (N)$ fails to be categorical, and putting these together, the same finiteness that makes the proof game safe makes first-order description leak — the bridge is that compactness converts the syntactic finiteness of deductions into the semantic impossibility of pinning down an infinite structure.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Use compactness to prove the upward Löwenheim-Skolem theorem: if a theory $T$ has an infinite model, then for every cardinal $κ \geq ∣ L ∣ + ℵ_{0}$ , $T$ has a model of cardinality $\geq κ$ .

Hint

Adjoin $κ$ new constants $c_{α}$ and the axioms $c_{α} \neq = c_{β}$ for $α \neq = β$ ; check finite satisfiability in the infinite model.

Answer

Expand $L$ to $L^{'}$ by new constants ${c_{α} : α < κ}$ and set $T^{'} = T \cup {c_{α} \neq = c_{β} : α < β < κ}$ . A finite $T_{0}^{'} \subseteq T^{'}$ mentions finitely many constants $c_{α_{1}}, \dots, c_{α_{m}}$ ; an infinite model $A ⊨ T$ has at least $m$ distinct elements, so interpreting the $c_{α_{i}}$ as distinct elements of $∣ A ∣$ makes $A ⊨ T_{0}^{'}$ . Thus $T^{'}$ is finitely satisfiable, and by compactness has a model $B^{'}$ ; its reduct $B$ models $T$ , and the $κ$ distinct interpretations $c_{α}^{B^{'}}$ force $∣ B ∣ \geq κ$ . Rubric: full credit for the distinct-constants theory, the finite-satisfiability check in the infinite model, and the cardinality conclusion from $κ$ distinct constants.

Exercise 4 (medium, symbolic).

Show that no first-order theory $T$ with an infinite model is categorical (has all models isomorphic). Conclude that no first-order theory determines $N$ up to isomorphism.

Hint

Combine the upward and downward Löwenheim-Skolem theorems to get models of different cardinalities.

Answer

Suppose $T$ has an infinite model. By the upward Löwenheim-Skolem theorem $T$ has a model of cardinality $\geq κ$ for every $κ$ , in particular one of cardinality $\geq ℵ_{1}$ ; by the downward Löwenheim-Skolem theorem $T$ has a countable model. Models of cardinality $ℵ_{0}$ and $\geq ℵ_{1}$ have different cardinalities, hence are not isomorphic (an isomorphism is a bijection of universes). So $T$ is not categorical. In particular $Th (N)$ , and any first-order theory true of $N$ , has non-isomorphic models, so no first-order theory pins down $N$ . Rubric: full credit for producing two models of distinct cardinality and concluding non-isomorphism, with the $N$ specialization.

Exercise 5 (medium, symbolic).

Verify one direction of the Tarski-Vaught test: if $A \subseteq B$ and every existential $\exists y φ (\overset{a}{ˉ}, y)$ true in $B$ (with $\overset{a}{ˉ}$ from $∣ A ∣$ ) has a witness in $∣ A ∣$ , then $A ⪯ B$ .

Hint

Induct on formula complexity; the existential step is exactly the witness hypothesis, and the universal case is its dual.

Answer

By induction on $φ$ show $A ⊨ φ [\overset{a}{ˉ}] \Leftrightarrow B ⊨ φ [\overset{a}{ˉ}]$ for $\overset{a}{ˉ}$ from $∣ A ∣$ . Atomic formulas: $A \subseteq B$ makes term-values and atomic truth agree. Negation and conjunction commute with the equivalence by the inductive hypothesis. Existential $\exists y ψ (\overset{a}{ˉ}, y)$ : if $A ⊨ \exists y ψ$ , a witness $a^{'} \in ∣ A ∣ \subseteq ∣ B ∣$ gives $B ⊨ ψ [\overset{a}{ˉ}, a^{'}]$ by induction, so $B ⊨ \exists y ψ$ ; conversely if $B ⊨ \exists y ψ [\overset{a}{ˉ}, y]$ , the hypothesis supplies a witness $a^{'} \in ∣ A ∣$ with $B ⊨ ψ [\overset{a}{ˉ}, a^{'}]$ , hence $A ⊨ ψ [\overset{a}{ˉ}, a^{'}]$ by induction, so $A ⊨ \exists y ψ$ . The universal case follows via $\forall y \equiv \neg\exists y \neg$ . Rubric: full credit for the induction with the existential step keyed to the witness hypothesis.

Exercise 6 (medium, symbolic).

Use compactness to show that the class of finite groups is not first-order axiomatizable: there is no set $T$ of sentences in the language of groups whose models are exactly the finite groups.

Hint

If such $T$ existed, add sentences $λ_{n}$ asserting "there are at least $n$ distinct elements" and apply compactness.

Answer

Suppose $T$ axiomatizes the finite groups. For each $n$ let $λ_{n}$ be the sentence "there exist at least $n$ distinct elements," $\exists x_{1} \dots \exists x_{n} ⋀_{i < j} x_{i} \neq = x_{j}$ . Consider $T \cup {λ_{n} : n \geq 1}$ . Any finite subset uses $λ_{n}$ only up to some $N$ ; a finite group of order $\geq N$ (e.g. the cyclic group $Z / N Z$ ) models $T$ and all $λ_{n}$ for $n \leq N$ , so the subset is satisfiable. By compactness $T \cup {λ_{n} : n \geq 1}$ has a model $G$ , which is a group (models $T$ ) and infinite (models every $λ_{n}$ ). But $G ⊨ T$ forces $G$ finite, a contradiction. So no such $T$ exists. Rubric: full credit for the at-least- $n$ sentences, the finite-group witnesses, and the contradiction.

Exercise 7 (hard, symbolic).

Prove the downward Löwenheim-Skolem theorem for a countable language: every infinite structure $B$ has a countable elementary substructure. Use the Tarski-Vaught test and a Skolem-witness closure.

Hint

Build $A_{0} \subseteq A_{1} \subseteq \dots$ where each $A_{k + 1}$ adds, for every formula $\exists y φ (\overset{a}{ˉ}, y)$ true in $B$ with $\overset{a}{ˉ}$ from $A_{k}$ , one witness; take the union.

Answer

Fix a countable $A_{0} \subseteq ∣ B ∣$ (a single element suffices). Given countable $A_{k}$ , for each formula $φ (\overset{x}{ˉ}, y)$ and tuple $\overset{a}{ˉ}$ from $A_{k}$ with $B ⊨ \exists y φ [\overset{a}{ˉ}, y]$ , choose one witness $b_{φ, \overset{a}{ˉ}} \in ∣ B ∣$ (axiom of choice) and let $A_{k + 1}$ be $A_{k}$ together with all these witnesses. Since the language is countable there are countably many formulas, and $A_{k}$ is countable so there are countably many tuples $\overset{a}{ˉ}$ ; thus $A_{k + 1}$ is countable. Let $A = ⋃_{k} A_{k}$ , countable as a countable union of countable sets, and closed under the operations of $B$ (witnesses for $\exists y (f (\overset{a}{ˉ}) = y)$ are included), so $A$ is the universe of a substructure $A \subseteq B$ . For Tarski-Vaught: if $B ⊨ \exists y φ [\overset{a}{ˉ}, y]$ with $\overset{a}{ˉ}$ from $A$ , then $\overset{a}{ˉ}$ lies in some $A_{k}$ , so a witness $b_{φ, \overset{a}{ˉ}} \in A_{k + 1} \subseteq A$ was added. Hence $A ⪯ B$ , and $A$ is countable. Rubric: full credit for the witness-closure chain, the countability bookkeeping, and the Tarski-Vaught verification.

Exercise 8 (hard, symbolic).

Use compactness to construct a positive infinitesimal: a model of the complete first-order theory of $(R; +, \cdot, <, 0, 1)$ containing an element $ε$ with $0 < ε < 1/ n$ for every positive integer $n$ . Explain why this gives infinitesimals.

Hint

Adjoin a constant $ε$ and the sentences $0 < ε$ and $ε < \underline{1/ n}$ for each $n$ (using the term $n 1 + \dots + 1$ to name $n$ ). Check finite satisfiability in $R$ .

Answer

Let $T = Th (R; +, \cdot, <, 0, 1)$ and adjoin a constant $ε$ , forming $Γ = T \cup {0 < ε} \cup {ε \cdot \underline{n} < 1 : n \geq 1}$ , where $\underline{n}$ is the term $1 + \dots + 1$ ( $n$ ones), so $ε \cdot \underline{n} < 1$ says $ε < 1/ n$ . A finite $Γ_{0}$ uses these for $n \leq N$ ; interpreting $ε$ in $R$ as $\frac{1}{N + 1}$ gives $0 < ε$ and $ε < 1/ n$ for all $n \leq N$ , so $R ⊨ Γ_{0}$ . By compactness $Γ$ has a model $^{*} R$ , whose reduct models $T$ , so it is an ordered field elementarily equivalent to $R$ ; the element $ε^{^{*} R}$ is positive yet smaller than every $1/ n$ , a positive infinitesimal. Its reciprocal exceeds every integer, an infinite number. Because $^{*} R \equiv R$ , every first-order property of $R$ transfers, which is the transfer principle of non-standard analysis. Rubric: full credit for the infinitesimal-forcing theory, the finite-satisfiability check, and the transfer remark.

Advanced results Master

The compactness theorem and the Löwenheim-Skolem theorems organize four developments: the two semantic routes to compactness and their equal strength; the upward and downward Löwenheim-Skolem-Tarski theorems with the resulting impossibility of first-order categoricity; Skolem's paradox and the non-absoluteness of cardinality; and the exact location of first-order logic among logics, fixed by Lindström's theorem as the maximal one carrying both metatheorems.

Theorem 1 (two proofs of compactness). Compactness has a deductive proof — completeness 42.01.06 pending plus deduction-finiteness — and a calculus-free ultraproduct proof ^{[Chang-Keisler Ch. 1]}. For the latter, let every finite $Γ_{0} \subseteq Γ$ have a model; index the finite subsets by $I$ , take for each $i \in I$ a model $A_{i}$ of the finite subset $i$ , and let $U$ be an ultrafilter on $I$ containing each cone ${i : i \supseteq i_{0}}$ (these have the finite intersection property, so such $U$ exists by the ultrafilter lemma). By Łoś's theorem, the ultraproduct $\prod_{U} A_{i}$ satisfies a sentence iff $U$ -almost-all factors do; each $γ \in Γ$ holds in $A_{i}$ for every $i \supseteq {γ}$ , a $U$ -large set, so $\prod_{U} A_{i} ⊨ γ$ . The ultraproduct is a single model of $Γ$ . Both proofs use exactly the Boolean prime ideal theorem; over $ZF$ , first-order compactness is equivalent to it, as in the propositional case 42.01.02 pending, the ultrafilter on $I$ being the sole choice ingredient.

Theorem 2 (Löwenheim-Skolem-Tarski; failure of categoricity). Every infinite structure $B$ in a language of size $λ$ has, for each $X \subseteq ∣ B ∣$ , an elementary substructure $A ⪯ B$ with $X \subseteq ∣ A ∣$ and $∣ A ∣ \leq ∣ X ∣ + λ + ℵ_{0}$ — close $X$ under Skolem witnesses and apply the Tarski-Vaught test ^{[Marker Ch. 2]}. Dually, a theory with an infinite model has models of every cardinality $κ \geq λ + ℵ_{0}$ : adjoin $κ$ distinct constants and apply compactness for the lower bound, then the downward theorem to hit $κ$ exactly. Together they yield models in every infinite cardinality $\geq λ$ for any theory with one infinite model, whence no first-order theory with an infinite model is categorical: it has models of distinct cardinalities, never all isomorphic. The substitute is $κ$ -categoricity, governed by Morley's theorem 42.02.01 pending.

Theorem 3 (Skolem's paradox; non-absoluteness of cardinality). If $ZF$ is consistent it has a countable model $M$ , by the downward Löwenheim-Skolem theorem applied to any model ^{[Enderton §2.6]}. Inside $M$ the theorem of Cantor "there is an uncountable set" holds: some $x \in ∣ M ∣$ satisfies $M ⊨$ " $x$ is uncountable." Yet ${y \in ∣ M ∣ : M ⊨ y \in x}$ is countable in the real universe, since $∣ M ∣$ is. The resolution is that "uncountable" means "no bijection with $ω$ exists as a set in the model." A bijection $ω \to x$ exists externally but is not an element of $M$ , so $x$ is uncountable relative to $M$ and countable relative to $V$ . Cardinality is a non-absolute notion: it depends on which functions the model contains. The first-order axioms of $ZF$ cannot force a model to contain every bijection, the precise mechanism by which Löwenheim-Skolem and Skolem's paradox coincide.

Theorem 4 (Lindström's theorem; the price of compactness). First-order logic is the maximal abstract logic satisfying both the countable compactness theorem and the downward Löwenheim-Skolem theorem to $ℵ_{0}$ : any abstract logic extending it with both properties has exactly its expressive power ^{[Lindström 1969]}. This pinpoints the trade-off. Second-order logic, quantifying over subsets, is categorical for $N$ (the second-order Peano axioms have only $N$ up to isomorphism) and for $R$ (the complete ordered field is unique), but it loses compactness, loses the Löwenheim-Skolem theorems, and has no recursively axiomatizable complete proof system — its validities are not even arithmetically definable. The infinitary logic $L_{ω_{1} ω}$ keeps a Löwenheim-Skolem theorem but loses compactness; the logic with "there exist uncountably many" keeps compactness in the countable form but loses downward Löwenheim-Skolem. The expressive limits derived here are not defects to be engineered away: by Lindström they are equivalent to possessing both metatheorems at all.

Synthesis. Compactness is the foundational reason first-order logic cannot control cardinality, and putting these together it organizes all four developments through one mechanism — finitely many axioms are inspected at a time, so any limit they never examine slips through. This is exactly what the two proofs of Theorem 1 make precise from opposite sides: the deductive route reads compactness off the finiteness of a single proof, the ultraproduct route off Łoś's theorem averaging finite models, and their equal strength (both equivalent to the Boolean prime ideal theorem) is dual to the same equivalence in the propositional case 42.01.02 pending. The cardinality flexibility of Theorem 2 is the central insight read in two directions — upward by adjoining distinct constants, downward by Skolem-closing under witnesses — and it generalises the term-model bound of 42.01.06 pending into the statement that no infinite structure is first-order categorical, so $N$ and $R$ alike escape capture. Skolem's paradox of Theorem 3 is this flexibility turned on set theory: the model that downward Löwenheim-Skolem shrinks is one whose internal cardinalities desynchronize from external ones, and the bridge is that cardinality depends on which functions a model holds, not an absolute. Lindström's theorem closes the circle: the limits are the logic. The keystone is that the same finiteness of deduction that made the proof game sound and complete 42.01.05 pending, 42.01.06 pending makes first-order description leak, and on this leak the whole model theory of 42.02.01 pending is built.

Full proof set Master

Proposition 1 (compactness from completeness). A set $Γ$ of $L$ -sentences has a model iff every finite subset of $Γ$ has a model.

Proof. ( $\Rightarrow$ ) A model of $Γ$ models every subset. ( $\Leftarrow$ ) Suppose $Γ$ has no model. By the completeness theorem 42.01.06 pending in model-existence form, $Γ$ is inconsistent, so $Γ ⊢ β$ and $Γ ⊢ \neg β$ for some sentence $β$ . Each deduction is a finite sequence citing finitely many members of $Γ$ ; let $Γ_{0}$ be the finite union of premises cited in the two deductions. Then $Γ_{0} ⊢ β$ and $Γ_{0} ⊢ \neg β$ , so $Γ_{0}$ is inconsistent, hence by soundness 42.01.05 pending has no model. Thus some finite subset of $Γ$ has no model; contrapositively, finite satisfiability gives satisfiability. $□$

Proposition 2 (Tarski-Vaught test). For $A \subseteq B$ , $A ⪯ B$ iff for every formula $φ (\overset{x}{ˉ}, y)$ and tuple $\overset{a}{ˉ}$ from $∣ A ∣$ with $B ⊨ \exists y φ [\overset{a}{ˉ}, y]$ there is $b \in ∣ A ∣$ with $B ⊨ φ [\overset{a}{ˉ}, b]$ .

Proof. ( $\Rightarrow$ ) If $A ⪯ B$ and $B ⊨ \exists y φ [\overset{a}{ˉ}, y]$ , then $A ⊨ \exists y φ [\overset{a}{ˉ}, y]$ by elementarity, so a witness $b \in ∣ A ∣$ has $A ⊨ φ [\overset{a}{ˉ}, b]$ , hence $B ⊨ φ [\overset{a}{ˉ}, b]$ again by elementarity. ( $\Leftarrow$ ) Induct on $φ$ to show $A ⊨ φ [\overset{a}{ˉ}] \Leftrightarrow B ⊨ φ [\overset{a}{ˉ}]$ for $\overset{a}{ˉ}$ from $∣ A ∣$ . Atomic: term-values and atomic relations agree because $A$ is a substructure. Negation and implication: from the inductive hypothesis via the truth clauses. Existential $\exists y ψ (\overset{a}{ˉ}, y)$ : if $A ⊨ \exists y ψ$ , a witness $a^{'} \in ∣ A ∣$ gives $A ⊨ ψ [\overset{a}{ˉ}, a^{'}]$ , so $B ⊨ ψ [\overset{a}{ˉ}, a^{'}]$ by induction, whence $B ⊨ \exists y ψ$ . Conversely if $B ⊨ \exists y ψ [\overset{a}{ˉ}, y]$ , the witness hypothesis supplies $b \in ∣ A ∣$ with $B ⊨ ψ [\overset{a}{ˉ}, b]$ , so $A ⊨ ψ [\overset{a}{ˉ}, b]$ by induction, hence $A ⊨ \exists y ψ$ . The universal case is dual. So $A ⪯ B$ . $□$

Proposition 3 (downward Löwenheim-Skolem-Tarski). Let $B$ be a structure in a language of size $λ$ and $X \subseteq ∣ B ∣$ . There is $A ⪯ B$ with $X \subseteq ∣ A ∣$ and $∣ A ∣ \leq ∣ X ∣ + λ + ℵ_{0}$ .

Proof. Set $A_{0} = X$ if nonempty, else a singleton. Given $A_{k}$ , for each formula $φ (\overset{x}{ˉ}, y)$ of $L$ and each tuple $\overset{a}{ˉ}$ from $A_{k}$ with $B ⊨ \exists y φ [\overset{a}{ˉ}, y]$ , select one witness $b_{φ, \overset{a}{ˉ}} \in ∣ B ∣$ (axiom of choice) and let $A_{k + 1} = A_{k} \cup {b_{φ, \overset{a}{ˉ}}}$ . The number of pairs $(φ, \overset{a}{ˉ})$ is at most $λ \cdot ∣ A_{k} ∣^{< ω} \cdot ℵ_{0} = ∣ A_{k} ∣ + λ + ℵ_{0}$ , so $∣ A_{k + 1} ∣ \leq ∣ A_{k} ∣ + λ + ℵ_{0}$ . Let $A = ⋃_{k < ω} A_{k}$ ; then $∣ A ∣ \leq ∣ X ∣ + λ + ℵ_{0}$ (a countable increasing union with bounded steps). $A$ is closed under the functions of $B$ — for a function symbol $f$ , the witness for $\exists y (f \overset{a}{ˉ} = y)$ lies in $A$ — so $A$ underlies a substructure $A \subseteq B$ . For Tarski-Vaught: a tuple $\overset{a}{ˉ}$ from $A$ lies in some $A_{k}$ , and any $B ⊨ \exists y φ [\overset{a}{ˉ}, y]$ contributed a witness $b_{φ, \overset{a}{ˉ}} \in A_{k + 1} \subseteq A$ . By Proposition 2, $A ⪯ B$ . $□$

Proposition 4 (upward Löwenheim-Skolem). If a theory $T$ has an infinite model, then for every $κ \geq ∣ L ∣ + ℵ_{0}$ , $T$ has a model of cardinality exactly $κ$ .

Proof. Adjoin new constants ${c_{α} : α < κ}$ and let $T^{'} = T \cup {c_{α} \neq = c_{β} : α < β < κ}$ . A finite $T_{0}^{'} \subseteq T^{'}$ mentions finitely many constants; an infinite model $A ⊨ T$ interprets them as distinct elements, so $A ⊨ T_{0}^{'}$ . By compactness (Proposition 1) $T^{'}$ has a model $B^{'}$ ; its reduct $B ⊨ T$ has $\geq κ$ elements, the distinct $c_{α}^{B^{'}}$ . Now apply Proposition 3 with $X = {c_{α}^{B^{'}} : α < κ}$ to obtain $C ⪯ B$ with $X \subseteq ∣ C ∣$ and $∣ C ∣ \leq κ + ∣ L ∣ + ℵ_{0} = κ$ ; since $X \subseteq ∣ C ∣$ forces $∣ C ∣ \geq κ$ , equality holds, and $C ⊨ T$ . $□$

Proposition 5 (non-categoricity and Skolem's paradox). (i) No first-order theory with an infinite model is categorical. (ii) If $ZF$ is consistent, it has a countable model in which "there is an uncountable set" is true.

Proof. (i) By Proposition 4, $T$ has a model of cardinality $ℵ_{0}$ and one of cardinality $ℵ_{1}$ (taking $κ = ℵ_{1} \geq ∣ L ∣ + ℵ_{0}$ when $L$ is countable; otherwise $κ = ∣ L ∣^{+}$ and $κ = ℵ_{0}$ via the downward theorem). Distinct cardinalities preclude a bijection, so the models are not isomorphic, and $T$ is not categorical. (ii) If $ZF$ is consistent it has a model $N_{0}$ by completeness; by Proposition 3 (with $X = \emptyset$ , $λ = ℵ_{0}$ ) it has a countable elementary submodel $M$ , so $M ⊨ ZF$ . Cantor's theorem is a theorem of $ZF$ , so $M ⊨$ " $\exists x (x is uncountable)$ "; fix such an $x$ . The set ${y \in ∣ M ∣ : M ⊨ y \in x}$ injects into $∣ M ∣$ , which is countable, so $x$ has countably many members externally. A bijection $ω \to x$ exists in $V$ but, were it an element of $M$ , would witness $M ⊨$ " $x$ is countable," contradicting the choice of $x$ ; so it is not in $M$ . Hence $x$ is uncountable in $M$ and countable in $V$ , with no contradiction: cardinality is non-absolute. $□$

Connections Master

Gödel's completeness theorem and the Henkin construction 42.01.06 pending is the prerequisite this unit harvests. Completeness in model-existence form, combined with the finiteness of deductions, is the first-order compactness theorem; the term model's cardinality bound $∣ A ∣ \leq ∣ L ∣ + ℵ_{0}$ is the downward Löwenheim-Skolem theorem in its first form. Where 42.01.06 pending proved that consistency equals satisfiability, this unit reads the consequences of that identification when applied to finite fragments — the single move that turns a meaning-capturing calculus into a tool for manufacturing non-standard structures.
The compactness theorem for propositional logic 42.01.02 pending is the decidable warm-up. The finite-intersection skeleton and the equivalence with the Boolean prime ideal theorem are shared, and the ultraproduct proof here is the first-order analogue of the ultrafilter-on-the-Lindenbaum-algebra proof there. What changes is the harvest: truth-value cylinders become spaces of structures, so first-order compactness yields non-standard models, infinitesimals, and the failure of finite axiomatizability, none of which the propositional case can state. The connection isolates exactly the expressive jump from propositional to first-order logic.
The model theory of first-order structures, co-produced as 42.02.01 pending, rests on compactness and Löwenheim-Skolem as its two foundational metatheorems. The method of diagrams, elementary chains and amalgamation, the spectrum function counting models in each cardinality, Morley's categoricity theorem, and the stability-theoretic classification all presuppose that a consistent expansion has a model (compactness) and that cardinality is freely adjustable (Löwenheim-Skolem). The non-standard models built here are the prototype objects of that theory, and the Tarski-Vaught test introduced here is its basic tool for recognizing elementary substructures.
Set theory and the cumulative hierarchy 42.03.01 is where Skolem's paradox lives and is resolved. The countable model of $ZF$ produced by downward Löwenheim-Skolem, and the non-absoluteness of cardinality it exhibits, feed directly into the study of absoluteness, the Lévy hierarchy, and forcing, where which sets a model contains is precisely the object of manipulation. The paradox is not a defect but the first appearance of the relativity of set-theoretic notions that the independence proofs of 42.03.01 exploit systematically.
Gödel's incompleteness theorems 42.01.09 pending depend on the non-standard models compactness guarantees. The Gödel sentence $G_{T}$ is unprovable in $T$ precisely because it is false in some non-standard model of $T$ while true in $N$ , so $T \neq ⊨ G_{T}$ ; the existence of those non-standard models is the constant-adjunction construction of this unit. Completeness and incompleteness are reconciled exactly through the multiplicity of models that compactness produces — provability matches full semantic consequence, but a fixed theory's models outrun the standard one.

Historical & philosophical context Master

The downward Löwenheim-Skolem theorem originates with Leopold Löwenheim's 1915 paper Über Möglichkeiten im Relativkalkül, which showed that a first-order sentence with a model has a countable model, and was sharpened and corrected by Thoralf Skolem in a sequence of papers from 1920 to 1923, who introduced the use of Skolem functions and normal forms and proved the theorem for sets of sentences ^{[Enderton §2.6]}. Skolem drew the unsettling consequence now bearing his name: a first-order axiomatization of set theory, if it has a model at all, has a countable one, in which "uncountable" sets nonetheless exist — the relativity of cardinality to the model. Skolem regarded this as evidence against the adequacy of any first-order foundation for the absolute notion of set, a stance that prefigured the later understanding of absoluteness and forcing.

The compactness theorem for first-order logic was isolated by Kurt Gödel as a corollary of his 1930 completeness theorem and given a direct semantic proof, independent of any deductive calculus, by Anatoly Maltsev in 1936, whose general (uncountable-language) form opened the door to applications in algebra; the ultraproduct proof is due to the work of Jerzy Łoś (1955), whose fundamental theorem on ultraproducts made the construction routine ^{[Chang-Keisler Ch. 1]}. Abraham Robinson built non-standard analysis on these foundations in 1961-1966, realizing Leibniz's infinitesimals as elements of a non-standard model of the reals obtained by compactness or ultrapower ^{[Robinson Ch. 1-3]}. Per Lindström's 1969 theorem established that compactness together with the downward Löwenheim-Skolem property characterizes first-order logic uniquely among abstract logics, fixing the precise sense in which the expressive limits derived here are the defining trait of elementary logic ^{[Lindström 1969]}.

Bibliography Master

@book{enderton2001logic,
  author    = {Enderton, Herbert B.},
  title     = {A Mathematical Introduction to Logic},
  edition   = {2},
  publisher = {Harcourt/Academic Press},
  year      = {2001}
}

@book{changkeisler1990modeltheory,
  author    = {Chang, Chen Chung and Keisler, H. Jerome},
  title     = {Model Theory},
  edition   = {3},
  series    = {Studies in Logic and the Foundations of Mathematics},
  volume    = {73},
  publisher = {North-Holland},
  year      = {1990}
}

@book{marker2002modeltheory,
  author    = {Marker, David},
  title     = {Model Theory: An Introduction},
  series    = {Graduate Texts in Mathematics},
  volume    = {217},
  publisher = {Springer},
  year      = {2002}
}

@book{hodges1993modeltheory,
  author    = {Hodges, Wilfrid},
  title     = {Model Theory},
  series    = {Encyclopedia of Mathematics and its Applications},
  volume    = {42},
  publisher = {Cambridge University Press},
  year      = {1993}
}

@article{lowenheim1915,
  author  = {L\"{o}wenheim, Leopold},
  title   = {\"{U}ber M\"{o}glichkeiten im Relativkalk\"{u}l},
  journal = {Mathematische Annalen},
  volume  = {76},
  year    = {1915},
  pages   = {447--470}
}

@article{skolem1920,
  author  = {Skolem, Thoralf},
  title   = {Logisch-kombinatorische Untersuchungen \"{u}ber die Erf\"{u}llbarkeit oder Beweisbarkeit mathematischer S\"{a}tze},
  journal = {Skrifter utgit av Videnskapsselskapet i Kristiania},
  year    = {1920}
}

@article{malcev1936,
  author  = {Mal'cev, Anatoly I.},
  title   = {Untersuchungen aus dem Gebiete der mathematischen Logik},
  journal = {Matematicheskii Sbornik},
  volume  = {1},
  year    = {1936},
  pages   = {323--336}
}

@article{los1955,
  author  = {{\L}o\'{s}, Jerzy},
  title   = {Quelques remarques, th\'{e}or\`{e}mes et probl\`{e}mes sur les classes d\'{e}finissables d'alg\`{e}bres},
  journal = {Mathematical Interpretation of Formal Systems},
  publisher = {North-Holland},
  year    = {1955},
  pages   = {98--113}
}

@book{robinson1966nonstandard,
  author    = {Robinson, Abraham},
  title     = {Non-standard Analysis},
  publisher = {North-Holland},
  year      = {1966}
}

@article{lindstrom1969,
  author  = {Lindstr\"{o}m, Per},
  title   = {On extensions of elementary logic},
  journal = {Theoria},
  volume  = {35},
  year    = {1969},
  pages   = {1--11}
}

Prerequisites

42.01.06

Tier anchors

beginner: Enderton 2001 *A Mathematical Introduction to Logic* 2e (Harcourt/Academic Press) §2.6 (compactness for first-order logic read as 'a batch of demands has a world iff every finite handful does', illustrated by adding a single endless demand 'bigger than 1, bigger than 2, bigger than 3, …' to force a number with no honest size, so a counting world must sprout an extra number standing past all the ordinary ones; the downward Löwenheim-Skolem idea that a world describable in words can always be shrunk to one with only countably many things; the Skolem surprise that a world this small can still believe some of its collections are too big to count)
intermediate: Enderton 2001 *A Mathematical Introduction to Logic* 2e §2.6 (the compactness theorem for first-order logic as a corollary of completeness 42.01.06 — a set of sentences has a model iff every finite subset does — together with the non-standard model of arithmetic obtained by adjoining a constant c with c > Sⁿ0 for every n; the downward Löwenheim-Skolem-Tarski theorem via the term model's cardinality bound and the Tarski-Vaught elementary-substructure test, and the upward direction by adjoining κ distinct constants; Skolem's paradox in a countable model of ZF and the relativity of cardinality)
master: Enderton 2001 §2.6; Chang and Keisler 1990 *Model Theory* 3e (North-Holland) Ch. 1-2 (compactness via the completeness theorem and via the ultraproduct/Łoś construction, the Löwenheim-Skolem-Tarski theorem in full, the method of constants, elementary chains); Marker 2002 *Model Theory: An Introduction* (Springer GTM 217) Ch. 2 (compactness, Löwenheim-Skolem, the Tarski-Vaught test, the failure of first-order categoricity, non-standard models); Hodges 1993 *Model Theory* (Cambridge) Ch. 5-6 (downward and upward Löwenheim-Skolem, Skolem functions and Skolem hulls); Lindström 1969 *On extensions of elementary logic* (Theoria 35) (the maximality of first-order logic among logics with countable compactness and downward Löwenheim-Skolem); Robinson 1966 *Non-standard Analysis* (North-Holland) Ch. 1-3 (the hyperreals as a non-standard model of the reals)

References

Enderton, H. B. — A Mathematical Introduction to Logic · 2nd edition, Harcourt/Academic Press (2001), §2.6 ('Models of Theories'). Derives the compactness theorem for first-order logic from the completeness theorem of §2.5 (42.01.06): a set Γ of sentences has a model iff Γ is consistent iff (by finiteness of deductions) every finite subset of Γ is consistent iff every finite subset has a model. Develops the standard consequences absent from the propositional case: (i) NON-STANDARD MODELS OF ARITHMETIC — adjoin a new constant c to the language of the standard model 𝔑 = (ℕ; 0, S, +, ·, <) together with the sentences c ≠ 0, c ≠ S0, c ≠ SS0, …, i.e. c > Sⁿ0 for every numeral; every finite subset is satisfiable in 𝔑 by interpreting c as a large enough number, so by compactness the whole set has a model, an elementary extension of 𝔑 containing an element exceeding every standard numeral (an 'infinite' non-standard number); the same device makes Th(𝔑) — true arithmetic — non-categorical and gives models with infinite descending-in-size structure above the standard part. (ii) The DOWNWARD LÖWENHEIM-SKOLEM(-TARSKI) THEOREM: every structure 𝔄 in a countable language has a countable elementary substructure (and, in the Tarski form, for any X ⊆ |𝔄| an elementary substructure of cardinality ≤ |X| + ℵ₀ containing X), proved by closing X under Skolem witnesses (for each formula ∃y φ(x̄, y) a chosen witness, via the Tarski-Vaught test that an existential satisfied in 𝔄 has a witness in the substructure). (iii) The UPWARD LÖWENHEIM-SKOLEM THEOREM: a theory with an infinite model has models of every cardinality κ ≥ |language| + ℵ₀, by adjoining κ new constants c_α with the axioms c_α ≠ c_β (α ≠ β); every finite subset is satisfiable in the infinite model, so by compactness the theory plus the distinctness axioms is satisfiable, in a model of cardinality ≥ κ, then down to exactly κ by the downward theorem. (iv) SKOLEM'S PARADOX: ZF, if consistent, has a countable model 𝔐 (downward LS), in which the sentence 'there exists an uncountable set' is true; the resolution is that uncountability is not absolute — the bijection ℕ → x witnessing countability of x exists in the real universe but is not an element of 𝔐, so x is 'uncountable in 𝔐' while countable outside. (v) The failure of FIRST-ORDER CATEGORICITY for infinite structures: no first-order theory with an infinite model is categorical (determines its model up to isomorphism), since it has models of distinct cardinalities; in particular no first-order theory pins down ℕ or ℝ uniquely.
Chang, C. C. and Keisler, H. J. — Model Theory · 3rd edition, Studies in Logic 73, North-Holland (1990), Chapters 1-2. Gives two independent proofs of the compactness theorem for first-order logic: the deductive route through the completeness theorem (finiteness of deductions), and the ultraproduct route via the fundamental theorem of ultraproducts (Łoś's theorem) — given a family of models 𝔄_i (i ∈ I) of every finite subset of Γ and an ultrafilter U on I extending the Fréchet filter of cofinite sets indexed so that 𝔄_i ⊨ each sentence of Γ for all i in a U-large set, the ultraproduct ∏_U 𝔄_i is a single model of Γ by Łoś's theorem (a first-order sentence holds in the ultraproduct iff it holds in U-almost-all factors). This proof is choice-based but uses no deductive calculus, isolating compactness as a purely semantic phenomenon. Develops the method of constants and elementary diagrams, the downward and upward Löwenheim-Skolem-Tarski theorems, the existence of elementary extensions and chains, the non-standard models of arithmetic and analysis, and saturated models; treats compactness as equivalent over ZF to the Boolean prime ideal theorem and the ultrafilter existence on the index set as the choice ingredient.
Marker, D. — Model Theory: An Introduction · Graduate Texts in Mathematics 217, Springer (2002), Chapter 2. States and proves the compactness theorem (via completeness and via ultraproducts), the Tarski-Vaught test for elementary substructures (𝔄 ⊆ 𝔅 is elementary iff every existential ∃y φ(ā, y) realized in 𝔅 with ā from 𝔄 has a witness in 𝔄), and the downward Löwenheim-Skolem theorem by iterating Skolem-function closure, with the cardinality bound |L| + |X| + ℵ₀. Derives the upward Löwenheim-Skolem theorem by the new-constants compactness argument. Treats the failure of first-order categoricity (no infinite structure is determined up to isomorphism by its first-order theory), the consequent role of κ-categoricity (Morley's theorem) as the substitute notion, and the construction of non-standard models of arithmetic and of the reals (the hyperreals) by compactness or ultrapower. Frames compactness + Löwenheim-Skolem as the twin pillars on which model theory is built and as the precise statement of first-order logic's inability to control cardinality.
Lindström, P. — On extensions of elementary logic · Theoria 35 (1969), pp. 1-11. Proves Lindström's theorem: first-order logic is the maximal logic (in the sense of an abstract logic, a class of abstract structures with a satisfaction relation closed under isomorphism, renaming, and the Boolean and quantifier operations) that satisfies both the (countable) compactness theorem and the downward Löwenheim-Skolem theorem to ℵ₀; any abstract logic properly extending first-order logic and possessing both properties is in fact equivalent to first-order logic in expressive power. The theorem is the precise sense in which the package 'compactness + downward Löwenheim-Skolem' characterizes first-order logic and explains the trade-off: second-order logic gains categoricity for ℕ (and ℝ) at the cost of both compactness and a recursively axiomatizable complete proof system, while logics intermediate between first- and second-order (Lω₁ω, logics with the quantifier 'there exist uncountably many') keep one property and lose the other. Establishes that the expressive limits this unit derives from compactness and Löwenheim-Skolem are not removable without abandoning one of the two metatheorems.
Robinson, A. — Non-standard Analysis · North-Holland (1966), Chapters 1-3. Constructs the field of hyperreal numbers *ℝ as a non-standard model of the complete first-order (and higher-order, in the type-theoretic superstructure) theory of the ordered field of real numbers, obtained either by compactness (adjoin a constant ε with the sentences 0 < ε < 1/Sⁿ0 for every numeral n, forcing a positive infinitesimal) or as an ultrapower ℝ^ℕ/U modulo a non-principal ultrafilter U. The transfer principle is Łoś's theorem: every first-order sentence true of ℝ is true of *ℝ, so *ℝ has infinitesimals and infinite numbers while satisfying exactly the first-order properties of ℝ; the standard part map and the internal/external distinction recover classical analysis. This realizes Leibniz's infinitesimals rigorously and is the model-theoretic payoff of compactness applied to analysis, parallel to the non-standard models of arithmetic obtained from the same device.

Estimated time

beginner: 20m
intermediate: 55m
master: 90m