Connections with Model Theory
The Tarski–Vaught Test and Löwenheim–Skolem
The practical criterion for recognising elementary substructures and the theorems that build them at prescribed cardinalities.
Learning objectives
- State and apply the Tarski–Vaught test
- State both Löwenheim–Skolem theorems
- Explain the consequences for categoricity
The Tarski–Vaught test
Let A be a substructure of B. Then A ≺ B if and only if for every formula Φ(x, y) and every tuple a from A: whenever B satisfies ∃x Φ(x, a), there is a witness already in A.
It replaces a condition on all formulas by a condition on existential witnesses. The verification is still infinite but is now a closure condition — “whenever B can find something, A already has one” — which can be arranged by construction.
Downward Löwenheim–Skolem
Let B be a structure for a language of cardinality κ and let X ⊆ B. Then there is an elementary substructure A ≺ B containing X with |A| ≤ |X| + κ + ℵ0.
The proof is the witness-closure construction above, using choice to select witnesses. In particular, any structure for a countable language has a countable elementary substructure.
Applied to a model of set theory, the theorem produces a countable elementary substructure — a countable model of set theory, which internally believes uncountable sets exist. There is no contradiction: the bijection witnessing countability lives outside the model. The paradox is a lesson about the relativity of first-order notions, not a genuine inconsistency.
Upward Löwenheim–Skolem
If a theory has an infinite model, it has models of every cardinality at least the size of the language.
The proof adds κ new constant symbols with axioms asserting they are pairwise distinct, then applies compactness: every finite subset of the extended theory has a model, so the whole theory does.
Downward and upward Löwenheim–Skolem say first-order logic cannot control cardinality at all above the language size. A theory with an infinite model has models at every infinite cardinality, so no first-order theory characterises an infinite structure up to isomorphism.
Categoricity
A theory all of whose models of cardinality κ are isomorphic.
| Theory | Categoricity |
|---|---|
| Dense linear orders without endpoints | ℵ0-categorical |
| Algebraically closed fields of fixed characteristic | κ-categorical for every uncountable κ |
| Infinite vector spaces over a fixed countable field | κ-categorical for uncountable κ |
| Atomless Boolean algebras | ℵ0-categorical |
| Peano arithmetic | Not categorical at any cardinality |
A theory with no finite models that is κ-categorical for some κ at least the language size is complete — it decides every sentence.
Morley's theorem, later than the source, strengthens this: a countable theory categorical in one uncountable cardinality is categorical in all of them. It is the founding result of modern classification theory.
Frequently asked questions
Does the Tarski–Vaught test require checking all formulas?
In principle yes, but only existential ones matter — the other cases follow by induction. In practice one checks a generating set of formulas, often those in a quantifier-elimination normal form.
Why must the language size bound the model size?
Because a language with κ constant symbols forces every model to have at least κ elements if the constants are required to be distinct. The bound is unavoidable.
Source. S. Burris and H. P. Sankappanavar, A Course in Universal Algebra, The Millennium Edition — a corrected re-typesetting of Springer-Verlag Graduate Texts in Mathematics 78 (1981). Section V.1, book pages 227-233.
This page is an original exposition prepared for the KEVOS® knowledge library. It restates and reorganises mathematical results; it is not a reproduction of the source text.