Theories, Elementary Classes, and Categoricity

The set of all sentences true in a class of structures is closed under logical consequence by construction; it is a theory. The questions that matter about a theory are whether it settles every sentence (completeness) and whether its membership can be decided by a procedure (decidability).

Theories and the model correspondence

Two extremes bracket the possibilities. The smallest theory is the set of valid sentences, true in every structure. The largest is the set of all sentences, the unique unsatisfiable theory. Between them, every class of structures picks out a theory, and every set of sentences generates one.

Theory of a class. For a class $K$ of structures, $Th K = {σ ∣ σ is true in every member of K}$ .
Consequences of a set. For a set $Σ$ of sentences, $Cn Σ = {σ ∣ Σ ⊨ σ} = Th Mod Σ$ , the sentences true in every model of $Σ$ .

The operators $Th$ and $Mod$ move between sentences and structures in opposite directions, and each reverses inclusion. If $Σ_{1} \subseteq Σ_{2}$ then $Mod Σ_{2} \subseteq Mod Σ_{1}$ ; if $K_{1} \subseteq K_{2}$ then $Th K_{2} \subseteq Th K_{1}$ . Composing them stabilizes: $Mod Th Mod Σ = Mod Σ$ and $Th Mod Th K = Th K$ . This is a Galois connection between sets of sentences and classes of structures, with the theories on one side and the elementary classes on the other as its closed elements.

The operators Th and Mod form an antitone Galois connection; a set of sentences equals its own double closure exactly when it is a theory.

A set $T$ is a theory precisely when $T = Cn T$ . Set theory, for instance, is $Cn A_{Z F}$ for the Zermelo–Fraenkel axioms.¹

Complete theories

Completeness is the property of leaving nothing undecided. For a single structure $A$ , the theory $Th A$ is always complete: every sentence is either true or false in $A$ . The converse direction connects completeness to elementary equivalence.

The theory of fields is not complete: the sentence $1 + 1 = 0$ holds in some fields and fails in others, so neither it nor its negation is a consequence of the field axioms. The theory of algebraically closed fields of characteristic $0$ is complete, though that is far from obvious and is proved below.

Axiomatizable theories

A theory presented by a manageable set of axioms is more useful than one given as an opaque set of consequences. Two grades of manageability matter.

A finite $Σ$ can be replaced by the single conjunction $σ$ of its members, so a finitely axiomatizable theory is $Cn σ$ . The theory of fields is finitely axiomatizable, being $Cn Σ$ for the finite list of field axioms. The theory of fields of characteristic $0$ is axiomatizable but not finitely so: to the field axioms one must add the infinite list

1 + 1 \neq = 0, 1 + 1 + 1 \neq = 0, \dots

ruling out each positive characteristic. No finite subset suffices, because a finite subset excludes only finitely many characteristics and is therefore true in some field of large prime characteristic. The general principle behind this argument is compactness.

A finite subset of the characteristic-0 axioms forbids only finitely many characteristics, so a field of some larger prime characteristic still models it.

Completeness and decidability

The value of these notions is that they combine to make a theory decidable. The soundness and completeness theorems, restated for theories, give the following.

Part (a) follows because provability from a decidable axiom set can be systematically searched: enumerate deductions, listing their conclusions. Part (b) adds a halting criterion. Given $σ$ , enumerate the theorems of $T$ and wait; since $T$ is complete, either $σ$ or $\neg σ$ will appear, and which one appears decides membership.²

The three grades of tractability nest; completeness converts effective enumerability into full decidability.

A theory given axiomatically, such as Zermelo–Fraenkel set theory, is effectively enumerable. Whether it is also decidable turns on completeness. Set theory and full number theory are not complete, and their theories are therefore not decidable — results proved through incompleteness. When completeness can be established, part (b) delivers decidability. Categoricity establishes completeness without checking each sentence individually.

The Łoś–Vaught test

Categoricity in a single cardinal is compatible with having non-isomorphic models elsewhere, so it survives the failure of full first-order categoricity. It is exactly enough to force completeness, provided finite models are excluded.³

Categoricity at one infinite size forces completeness: any two models are stretched to that size, become isomorphic, and drag elementary equivalence back to the originals.

The converse fails. There are complete theories that are $κ$ -categorical for no $κ$ ; the theory of the real field is one, so the test does not apply to it even though the theory is complete.

Dense linear orders

The order of the rationals and the order of the reals satisfy exactly the same first-order sentences, and the Łoś–Vaught test proves it. The language has equality and a single binary relation $<$ . Let $δ$ conjoin the axioms of a dense linear order without endpoints:

Order. Trichotomy $\forall x \forall y (x < y \lor x = y \lor y < x)$ and transitivity.
Density. $\forall x \forall y (x < y \to \exists z (x < z \land z < y))$ .
No endpoints. $\forall x \exists y \exists z (y < x \land x < z)$ .

Every model of $δ$ is infinite. The categoricity input is a theorem of Cantor.

The isomorphism is built by a back-and-forth construction. Enumerate both universes and pair elements in stages, at even stages matching the next unmatched point of the first order to a point of the second that preserves all order relations already fixed, at odd stages doing the reverse. Density guarantees a suitable partner always exists, and the alternation guarantees every element is eventually matched.

The back-and-forth method interleaves matching points of one dense order to the other in both directions, using density to place each new point between its already-matched neighbors.

Worked example (Back-and-forth, first stages). Let $A$ and $B$ be countable dense linear orders without endpoints, enumerated $∣ A ∣ = {a_{0}, a_{1}, \dots}$ and $∣ B ∣ = {b_{0}, b_{1}, \dots}$ . Build an order isomorphism in stages, alternating direction.

Stage 0 (forth). Match $a_{0}$ to $b_{0}$ .
Stage 1 (back). Take the least-indexed unmatched point of $B$ , say $b_{1}$ . If $b_{1} < b_{0}$ , choose a point below $a_{0}$ ; the absence of a left endpoint supplies one. Match $b_{1}$ to it.
Stage 2 (forth). Take the least unmatched $a_{i}$ . It falls between two already-matched points $a_{j} < a_{i} < a_{k}$ ; density in $B$ supplies a point strictly between their images, and $a_{i}$ is matched to it.

Even stages exhaust $∣ A ∣$ and odd stages exhaust $∣ B ∣$ , so every point is matched, and each match respects $<$ by choice. The union of the stages is an isomorphism $A ≅ B$ ; taking $B = (Q, <)$ recovers Cantor's theorem.

By the test, $Cn δ$ is complete. Both $(Q, <)$ and $(R, <)$ model $δ$ , so they are elementarily equivalent: $(Q; <) \equiv (R; <)$ . They are not isomorphic — one is countable, the other is not — which is a concrete instance of elementary equivalence without isomorphism. Both theories are also decidable, being complete and axiomatizable.

Algebraically closed fields

The same test settles a deeper case. Let $Σ_{0}$ be the field axioms for characteristic $0$ and $Λ$ the sentences asserting that every polynomial of each positive degree has a root:

\forall a \forall b \forall c (a \neq = 0 \to \exists x a \cdot x \cdot x + b \cdot x + c = 0), \dots

The theory of the real field is also decidable, a much deeper result of Tarski, but it is categorical in no infinite cardinality, so the Łoś–Vaught route is unavailable there.

Theory	Axiomatizable	Complete	Decidable	Route to completeness
fields	finitely	no	no	—
fields of characteristic $0$	yes, not finitely	no	no	—
dense linear orders w/o endpoints	finitely	yes	yes	$ℵ_{0}$ -categoricity
algebraically closed, char $0$	yes	yes	yes	uncountable categoricity
real field	yes	yes	yes	quantifier elimination (Tarski)
full arithmetic $Th N$	no	yes	no	—

Prenex normal form

One syntactic tool recurs in constructions on theories: pulling every quantifier to the front. A formula is in prenex form if it reads $Q_{1} x_{1} \dots Q_{n} x_{n} α$ with each $Q_{i}$ a quantifier and $α$ quantifier-free.

The proof is an induction using quantifier-movement equivalences, valid when the moved variable does not occur free in the stationary formula:

\neg\forall x α \equiv \exists x \neg α, (α \to \forall x β) \equiv \forall x (α \to β), (\forall x α \to β) \equiv \exists x (α \to β) .

Renaming bound variables through alphabetic variants removes clashes before the rules apply.⁴

Prenex form is the starting point for Skolemization, which trades existential quantifiers for Skolem functions.

Enderton, §2.6 — theories as deductively closed sets, $Th K$ , $Cn Σ$ (Theorem 26G), complete theories, and axiomatizable versus finitely axiomatizable theories (Theorem 26H). ↩
Enderton, §2.6 — Corollary 26I linking axiomatizability to effective enumerability and completeness to decidability. ↩
Enderton, §2.6 — the Łoś–Vaught test (1954), Cantor's theorem on countable dense linear orders (26K), and Theorem 26J on algebraically closed fields and the complex field. ↩
Enderton, §2.6 — the prenex normal form theorem and the quantifier-manipulation rules Q1–Q3. ↩

Theories and the model correspondence

Complete theories

Axiomatizable theories

Completeness and decidability

The Łoś–Vaught test

Dense linear orders

Algebraically closed fields

Prenex normal form

Footnotes