---
title: Theories, Elementary Classes, and Categoricity
module: Models, Compactness, and Theories
moduleNumber: 5
lessonNumber: 2
order: 502
summary: >
  A theory is a set of sentences closed under logical consequence. Theories
  correspond to classes of models; a theory may be complete, axiomatizable, or
  finitely axiomatizable, and completeness together with axiomatizability yields
  decidability. The Łoś–Vaught test derives completeness from categoricity in a
  cardinal, applied to dense linear orders and to algebraically closed fields.
topics: [Models, Compactness, and Theories]
sources:
  - book: Enderton
    ref: "Ch. 2 — First-Order Logic; §2.6 Models of Theories (theories, categoricity, decidability)"
draft: false
---

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

> **Definition (Theory).** A set $T$ of sentences is a **theory** if it is
> closed under logical implication: whenever $T \models \sigma$, already
> $\sigma \in T$. Only sentences, never formulas with free variables, are
> admitted.

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 = \{\sigma \mid \sigma \text{ is true in every member of } K\}$.
- **Consequences of a set.** For a set $\Sigma$ of sentences,
  $\Cn \Sigma = \{\sigma \mid \Sigma \models \sigma\} = \Th \Mod \Sigma$, the
  sentences true in every model of $\Sigma$.

> **Theorem (The theory of a class).** $\Th K$ is a theory.

> **Proof.** Any member of $K$ is a model of $\Th K$. So if $\sigma$ is true in
> every model of $\Th K$, it is true in every member of $K$, hence lies in
> $\Th K$. $\square$

The operators $\Th$ and $\Mod$ move between sentences and structures in opposite
directions, and each reverses inclusion. If $\Sigma_1 \subseteq \Sigma_2$ then
$\Mod \Sigma_2 \subseteq \Mod \Sigma_1$; if $K_1 \subseteq K_2$ then
$\Th K_2 \subseteq \Th K_1$. Composing them stabilizes: $\Mod \Th \Mod \Sigma =
\Mod \Sigma$ 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.

$$
% caption: 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.
\begin{tikzpicture}[scale=1.0, >=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{4A6FA5}
  \node[draw, minimum width=32mm, minimum height=13mm, align=center] (s) at (0,0) {sets of\\sentences};
  \node[draw, minimum width=32mm, minimum height=13mm, align=center] (k) at (6.4,0) {classes\\of structures};
  \draw[->, acc, thick] (s.north east) .. controls (3.2,1.5) .. (k.north west);
  \draw[->, acc, thick] (k.south west) .. controls (3.2,-1.5) .. (s.south east);
  \node[acc, font=\scriptsize] at (3.2,1.75) {Mod (take all models)};
  \node[acc, font=\scriptsize] at (3.2,-1.75) {Th (take common sentences)};
  \node[font=\scriptsize] at (0,-2.4) {closed elements: theories};
  \node[font=\scriptsize] at (6.4,-2.4) {closed elements: elementary classes};
\end{tikzpicture}
$$

A set $T$ is a theory precisely when $T = \Cn T$. Set theory, for instance, is
$\Cn A_{ZF}$ for the Zermelo–Fraenkel axioms.[^theories]

## Complete theories

> **Definition (Complete).** A theory $T$ is **complete** if for every sentence
> $\sigma$, either $\sigma \in T$ or $\neg\sigma \in T$.

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

> **Lemma.** $\Th K$ is complete if and only if any two members of $K$ are
> elementarily equivalent. A theory $T$ is complete if and only if any two
> models of $T$ are elementarily equivalent.

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.

> **Definition (Axiomatizable).** A theory $T$ is **axiomatizable** if
> $T = \Cn \Sigma$ for some _decidable_ set $\Sigma$ of sentences. It is
> **finitely axiomatizable** if $T = \Cn \Sigma$ for some _finite_ $\Sigma$.

A finite $\Sigma$ can be replaced by the single conjunction $\sigma$ of its
members, so a finitely axiomatizable theory is $\Cn \sigma$. The theory of
fields is finitely axiomatizable, being $\Cn \Sigma$ 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, \qquad 1 + 1 + 1 \neq 0, \qquad \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.

> **Worked example (Characteristic $0$ is not finitely axiomatizable).**
> The theory of fields of characteristic $0$ is $\Cn \Sigma$, where $\Sigma$
> adds to the field axioms the sentences
> $$
> \sigma_n : \underbrace{1 + \cdots + 1}_{n \text{ ones}} \neq 0
> \qquad (n \geq 2).
> $$
> Suppose a finite $\Sigma_0 \subseteq \Sigma$ had the whole theory as its
> consequences. Only finitely many $\sigma_n$ lie in $\Sigma_0$; let $N$ be the
> largest such $n$. Choose a prime $q > N$. In the field $\mathbb{Z}/q\mathbb{Z}$
> every field axiom holds, and $\sigma_n$ holds for each $n \leq N$, since
> $n < q$ makes $n \cdot 1 \not\equiv 0 \pmod{q}$. So
> $\mathbb{Z}/q\mathbb{Z} \models \Sigma_0$, yet it has characteristic
> $q \neq 0$ and falsifies $\sigma_q \in \Sigma$. Hence
> $\Cn \Sigma_0 \neq \Cn \Sigma$, and no finite subset axiomatizes the theory.

$$
% caption: A finite subset of the characteristic-0 axioms forbids only finitely
% many characteristics, so a field of some larger prime characteristic still
% models it.
\begin{tikzpicture}[scale=1.0, >=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{4A6FA5}
  \draw[thick] (-0.2,0) -- (8.4,0);
  \foreach \x/\n in {0.8/2, 2.0/3, 3.2/5, 4.4/7} {\fill (\x,0) circle (1.6pt); \node[below, font=\scriptsize] at (\x,-0.16) {\n};}
  \foreach \x in {5.2,5.5,5.8} \fill (\x,0) circle (0.8pt);
  \fill[acc] (7.4,0) circle (2.0pt);
  \node[acc, below, font=\scriptsize] at (7.4,-0.16) {q};
  \draw[thick] (0.8,0.42) -- (0.8,0.6) -- (4.4,0.6) -- (4.4,0.42);
  \node[font=\scriptsize, align=center] at (2.6,1.0) {characteristics forbidden\\by the f\/inite subset};
  \node[acc, font=\scriptsize, align=center] at (7.4,1.05) {f\/ield of char q\\models the subset};
\end{tikzpicture}
$$

> **Theorem (Finite axiomatizability from a finite subset).** If $\Cn \Sigma$ is finitely axiomatizable, then
> $\Cn \Sigma_0 = \Cn \Sigma$ for some finite $\Sigma_0 \subseteq \Sigma$.

> **Proof.** Say $\Cn \Sigma = \Cn \tau$ for a single sentence $\tau$. Then
> $\Sigma \models \tau$ (since $\tau \in \Cn \tau = \Cn \Sigma$). By compactness
> $\Sigma_0 \models \tau$ for some finite $\Sigma_0 \subseteq \Sigma$, so
> $\Cn \tau \subseteq \Cn \Sigma_0 \subseteq \Cn \Sigma = \Cn \tau$, forcing
> equality. $\square$

## 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.

> **Corollary (Decidability of complete axiomatizable theories).** (a) An axiomatizable theory in a reasonable language is
> effectively enumerable. (b) A complete axiomatizable theory in a reasonable
> language is decidable.

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 $\sigma$, enumerate the theorems of $T$ and
wait; since $T$ is complete, either $\sigma$ or $\neg\sigma$ will appear, and
which one appears decides membership.[^decide]

$$
% caption: The three grades of tractability nest; completeness converts
% effective enumerability into full decidability.
\begin{tikzpicture}[scale=1.0, >=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{4A6FA5}
  \node[draw, minimum width=34mm, minimum height=9mm, align=center] (ax) at (0,2.0) {axiomatizable};
  \node[draw, minimum width=34mm, minimum height=9mm, align=center] (ee) at (0,0.5) {ef\/fectively enumerable};
  \node[draw, minimum width=34mm, minimum height=9mm, align=center] (co) at (5.6,2.0) {complete and axiomatizable};
  \node[draw=acc, thick, fill=acc!10, minimum width=34mm, minimum height=9mm, align=center] (de) at (5.6,0.5) {decidable};
  \draw[->, acc, thick] (ax) -- (ee);
  \draw[->, acc, thick] (co) -- (de);
  \draw[->, black, thick] (co.west) -- (ax.east);
  \node[font=\scriptsize] at (2.8,-0.7) {complete + axiomatizable gives a halting test};
\end{tikzpicture}
$$

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](/logic/incompleteness/incompleteness-and-undecidability). When
completeness _can_ be established, part (b) delivers decidability. Categoricity
establishes completeness without checking each sentence individually.

## The Łoś–Vaught test

> **Definition ($\kappa$-categorical).** A theory $T$ is
> **$\kappa$-categorical** if all its models of cardinality $\kappa$ are
> isomorphic. It is **$\aleph_0$-categorical** when all its countably infinite
> models are isomorphic.

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.[^lv]

> **Theorem (Łoś–Vaught test).** Let $T$ be a theory in a countable language
> with no finite models. If $T$ is $\kappa$-categorical for some infinite
> cardinal $\kappa$ (in particular for $\kappa = \aleph_0$), then $T$ is
> complete.

> **Proof.** It suffices to show any two models $\fA, \fB$ of $T$
> are elementarily equivalent. Both are infinite, so by the LST theorem there are
> $\fA' \equiv \fA$ and $\fB' \equiv \fB$ of
> cardinality $\kappa$. Both $\fA'$ and $\fB'$ are models of $T$
> of size $\kappa$, so by $\kappa$-categoricity they are isomorphic, hence
> elementarily equivalent. Chaining the relations,
>
> $$
> \fA \equiv \fA' \cong \fB' \equiv \fB,
> $$
>
> gives $\fA \equiv \fB$. $\square$

$$
% caption: 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.
\begin{tikzpicture}[scale=1.0, >=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{4A6FA5}
  \node[draw, circle, minimum size=8mm] (A) at (0,0) {$A$};
  \node[draw, circle, minimum size=8mm] (Ap) at (2.6,0) {$A_2$};
  \node[draw, circle, minimum size=8mm] (Bp) at (5.2,0) {$B_2$};
  \node[draw, circle, minimum size=8mm] (B) at (7.8,0) {$B$};
  \draw[-, black, thick] (A) -- (Ap);
  \draw[-, acc, very thick] (Ap) -- (Bp);
  \draw[-, black, thick] (Bp) -- (B);
  \node[font=\scriptsize] at (1.3,0.45) {equiv.};
  \node[acc, font=\scriptsize] at (3.9,0.55) {isomorphic (same size)};
  \node[font=\scriptsize] at (6.5,0.45) {equiv.};
  \node[font=\scriptsize] at (1.3,-0.55) {grow to size};
  \node[font=\scriptsize] at (6.5,-0.55) {grow to size};
\end{tikzpicture}
$$

The converse fails. There are complete theories that are $\kappa$-categorical
for no $\kappa$; 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 $\delta$ conjoin the axioms of a
dense linear order without endpoints:

- **Order.** Trichotomy $\forall x \, \forall y \, (x < y \vee x = y \vee y < x)$
  and transitivity.
- **Density.** $\forall x \, \forall y \, (x < y \to \exists z \, (x < z \wedge z < y))$.
- **No endpoints.** $\forall x \, \exists y \, \exists z \, (y < x \wedge x < z)$.

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

> **Theorem (Isomorphism of countable dense orders; Cantor).** Any two countable dense linear orders without
> endpoints are isomorphic; in particular any countable model of $\delta$ is
> isomorphic to $(\mathbb{Q}, <)$.

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.

$$
% caption: 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.
\begin{tikzpicture}[scale=1.0, >=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{4A6FA5}
  \draw[thick] (0,1.2) -- (7,1.2);
  \node[left, font=\scriptsize] at (0,1.2) {order A};
  \foreach \x in {1,2.4,3.1,4.6,5.8} \fill (\x,1.2) circle (1.5pt);
  \draw[thick] (0,-0.4) -- (7,-0.4);
  \node[left, font=\scriptsize] at (0,-0.4) {order B};
  \foreach \x in {0.9,2.1,3.4,4.4,6.0} \fill (\x,-0.4) circle (1.5pt);
  \draw[acc, thick] (1,1.2) -- (0.9,-0.4);
  \draw[acc, thick] (2.4,1.2) -- (2.1,-0.4);
  \draw[acc, thick] (3.1,1.2) -- (3.4,-0.4);
  \draw[black, thick, dashed] (4.6,1.2) -- (4.4,-0.4);
  \node[acc, font=\scriptsize, align=center] at (3.5,2.0) {order preserved at every pairing};
\end{tikzpicture}
$$

> **Worked example (Back-and-forth, first stages).** Let $\fA$ and $\fB$ be
> countable dense linear orders without endpoints, enumerated
> $|\fA| = \{a_0, a_1, \dots\}$ and $|\fB| = \{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 $\fB$, 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 $\fB$ supplies a point
>   strictly between their images, and $a_i$ is matched to it.
>
> Even stages exhaust $|\fA|$ and odd stages exhaust $|\fB|$, so every point is
> matched, and each match respects $<$ by choice. The union of the stages is an
> isomorphism $\fA \cong \fB$; taking $\fB = (\mathbb{Q}, <)$ recovers Cantor's
> theorem.

By the test, $\Cn \delta$ is complete. Both $(\mathbb{Q}, <)$ and
$(\mathbb{R}, <)$ model $\delta$, so they are elementarily equivalent:
$(\mathbb{Q}; <) \equiv (\mathbb{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 $\Sigma_0$ be the field axioms for
characteristic $0$ and $\Lambda$ 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), \quad \dots
$$

> **Theorem (Completeness of algebraically closed fields of characteristic 0).** (a) The theory of algebraically closed fields of
> characteristic $0$ is complete. (b) The theory of the complex field
> $(\mathbb{C}; 0, 1, +, \cdot)$ is decidable.

> **Proof sketch.** The theory is axiomatizable, being $\Cn(\Sigma_0 \cup
> \Lambda)$ over a decidable axiom set. Its models are all infinite. By a theorem
> of Steinitz, two algebraically closed fields are isomorphic exactly when they
> share characteristic and transcendence degree; for an uncountable field the
> transcendence degree equals the cardinality. Hence any two algebraically closed
> fields of characteristic $0$ of the same uncountable cardinality $\kappa$ are
> isomorphic, so the theory is $\kappa$-categorical for every uncountable
> $\kappa$. The Łoś–Vaught test gives completeness, and completeness plus
> axiomatizability gives decidability. Part (b) follows: $\mathbb{C}$ is one such
> field, so $\Th(\text{algebraically closed char } 0) \subseteq \Th \mathbb{C}$,
> and completeness forces equality. $\square$

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 | $\aleph_0$-categoricity |
| algebraically closed, char $0$ | yes | yes | yes | uncountable categoricity |
| real field | yes | yes | yes | quantifier elimination (Tarski) |
| full arithmetic $\Th \fN$ | 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 \cdots Q_n x_n \, \alpha$ with each $Q_i$ a quantifier and $\alpha$
quantifier-free.

> **Theorem (Prenex normal form).** Every formula is logically equivalent to a
> prenex formula.

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 \, \alpha \;\equiv\; \exists x \, \neg\alpha,
\qquad
(\alpha \to \forall x \, \beta) \;\equiv\; \forall x \, (\alpha \to \beta),
\qquad
(\forall x \, \alpha \to \beta) \;\equiv\; \exists x \, (\alpha \to \beta).
$$

Renaming bound variables through alphabetic variants removes clashes before the
rules apply.[^prenex]

> **Worked example (Pulling quantifiers to the front).** Convert
> $(\forall x \, \exists y \, Rxy) \to \exists u \, Pu$ to prenex form, applying
> the movement rules one quantifier at a time.
> $$
> \begin{aligned}
> (\forall x \, \exists y \, Rxy \to \exists u \, Pu)
>   &\equiv \exists x \,(\exists y \, Rxy \to \exists u \, Pu)
>     && \text{(Q3a: } \forall x \, \alpha \to \beta \equiv \exists x(\alpha \to \beta)) \\
>   &\equiv \exists x \, \forall y \,(Rxy \to \exists u \, Pu)
>     && \text{(Q3b: } \exists y \, \gamma \to \beta \equiv \forall y(\gamma \to \beta)) \\
>   &\equiv \exists x \, \forall y \, \exists u \,(Rxy \to Pu)
>     && \text{(Q2b: } \alpha \to \exists u \, \beta \equiv \exists u(\alpha \to \beta)).
> \end{aligned}
> $$
> Each step lifts one quantifier out of the conditional, and a quantifier leaving
> an antecedent flips: $\forall x$ becomes $\exists x$, $\exists y$ becomes
> $\forall y$. The variable conditions hold throughout, since $u$ does not occur
> in $Rxy$ and neither $x$ nor $y$ occurs in $Pu$.

Prenex form is the starting point for Skolemization, which trades existential
quantifiers for
[Skolem functions](/logic/second-order-logic/skolem-functions-and-many-sorted-logic).

[^theories]: Enderton, §2.6 — theories as deductively closed sets, $\Th K$, $\Cn \Sigma$ (Theorem 26G), complete theories, and axiomatizable versus finitely axiomatizable theories (Theorem 26H).
[^decide]: Enderton, §2.6 — Corollary 26I linking axiomatizability to effective enumerability and completeness to decidability.
[^lv]: 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.
[^prenex]: Enderton, §2.6 — the prenex normal form theorem and the quantifier-manipulation rules Q1–Q3.