---
title: Definability and Elementary Equivalence
module: First-Order Languages and Structures
moduleNumber: 3
lessonNumber: 3
order: 303
summary: >
  Fix a structure and ask which relations a formula can pick out: the definable
  ones. A set of sentences picks out a class of structures, the elementary
  classes. Homomorphisms and isomorphisms compare structures, and the
  homomorphism theorem shows isomorphic structures satisfy the same sentences.
  Automorphisms bound what first-order logic can distinguish, giving a tool for
  proving relations undefinable.
topics: [First-Order Languages and Structures]
sources:
  - book: Enderton
    ref: "Ch. 2 — First-Order Logic; §2.2 Truth and Models (definability, homomorphisms, elementary equivalence)"
draft: false
---

[Satisfaction](/logic/first-order-languages/structures-truth-and-satisfaction)
relates a formula to a structure, and each side of the relation is worth
holding fixed. Fix a structure and vary the formula, and the subsets and
relations of the universe a formula can describe are the **definable** ones.
Fix a set of sentences and vary the structure instead, and the structures
satisfying all of them form the class those sentences define, the object of
model theory. Both notions are sharply limited, and the limits are what make
first-order logic tractable.

## Definability in a structure

A formula with free variables, evaluated in a fixed structure, sorts the tuples
of the universe into those that satisfy it and those that do not. The satisfying
tuples form a relation.

> **Definition (Definable relation).** Let $\fA$ be a structure and
> $\varphi$ a formula whose free variables are among $v_1, \dots, v_k$. The
> $k$-ary relation $\varphi$ **defines** in $\fA$ is
> $$
> \{\langle a_1, \dots, a_k\rangle : \models_{\fA} \varphi[[a_1, \dots, a_k]]\}.
> $$
> A relation on $|\fA|$ is **definable in** $\fA$ iff some
> formula defines it.

Definability lets a structure express more than its named parameters suggest.
Take the real field $\fR = (\mathbb{R};\, 0, 1, +, \cdot)$, whose
language has no ordering symbol. The order is definable anyway: a real is
nonnegative exactly when it has a square root, so

$$
\models_{\fR} \exists v_2\; v_1 = v_2 \cdot v_2\ [[a]]
\iff a \ge 0,
$$

and the formula $\exists v_3\; v_2 = v_1 + v_3 \cdot v_3$ defines $\{\langle a,
b\rangle : a \le b\}$. The ordering was there implicitly, recoverable from
addition and multiplication.

$$
% caption: A defining formula $\varphi(x)$ splits the universe $|\fA|$
% into the tuples that satisfy it — the set $\varphi$ defines, shaded — and
% those that do not.
\begin{tikzpicture}[font=\small]
  \definecolor{acc}{HTML}{4A6FA5}
  \draw[black] (0,0) ellipse (3.4 and 2.1);
  \node[font=\footnotesize, black] at (0,1.7) {the universe};
  \begin{scope}
    \clip (0,0) ellipse (3.4 and 2.1);
    \fill[acc!12] (0.2,-0.2) ellipse (1.7 and 1.3);
  \end{scope}
  \draw[acc, thick] (0.2,-0.2) ellipse (1.7 and 1.3);
  \node[acc, font=\footnotesize] at (0.2,-0.2) {the formula holds};
  \node[acc, font=\footnotesize, align=center] at (0.2,-2.55)
    {the set the formula cuts out};
\end{tikzpicture}
$$

In the standard structure of arithmetic $\fN = (\mathbb{N};\, 0, S, +,
\cdot)$ a great many relations are definable.

- The order $\{\langle m, n\rangle : m < n\}$ is defined by $\exists v_3\; v_1 +
  S v_3 = v_2$.
- Each singleton $\{n\}$ is definable; $\{2\}$ by $v_1 = S S 0$. Such an $n$ is
  a **definable element**.
- The primes are definable: "$1 < v_1$ and every factorization is trivial,"
  written with the definable $1$ and $<$ substituted for, becomes
  $$
  \exists v_3\, (S 0 + S v_3 = v_1) \wedge
  \forall v_2 \forall v_3\, (v_1 = v_2 \cdot v_3 \rightarrow v_2 = S 0 \vee v_3 = S 0).
  $$
- Even exponentiation $\{\langle m, n, p\rangle : p = m^n\}$ is definable,
  though the proof needs the Chinese remainder theorem and waits until
  [representing exponentiation](/logic/computability-and-representability/representing-exponentiation).

The prime formula shows the technique in miniature: express the property using
$1$ and $<$, then eliminate those helpers by substituting their own defining
formulas.

> **Worked example.** Define the set of primes in $\fN = (\mathbb{N};\, 0, S,
> +, \cdot)$, whose language has no symbol for $1$ or for $<$.
>
> A prime is a number exceeding $1$ whose only factorizations are trivial. With
> parameters for $1$ and $<$ this reads
> $$
> 1 < v_1 \wedge \forall v_2 \forall v_3\, (v_1 = v_2 \cdot v_3 \rightarrow v_2 =
> 1 \vee v_3 = 1).
> $$
> Neither $1$ nor $<$ is available, but both are already definable: $1$ is named
> by the term $S 0$, and $m < n$ is defined by $\exists v_3\, (m + S v_3 = n)$,
> which for "$1 < v_1$" instantiates to $\exists v_3\, (S 0 + S v_3 = v_1)$.
> Substituting these in place of the helpers gives a formula in the bare
> language:
> $$
> \exists v_3\, (S 0 + S v_3 = v_1) \wedge
> \forall v_2 \forall v_3\, (v_1 = v_2 \cdot v_3 \rightarrow v_2 = S 0 \vee v_3 =
> S 0).
> $$
> Its satisfying assignments are the primes and nothing else, so the set of primes is
> definable in $\fN$.

Not everything is definable, and a counting argument shows why without
exhibiting a single example: there are uncountably many relations on
$\mathbb{N}$ but only countably many formulas, so most relations have no
defining formula. Naming a specific undefinable relation is genuinely hard (if
it were definable it would be easy to describe); the cleanest example, the set
of Gödel numbers of truths of $\fN$, comes with
[Tarski's theorem](/logic/incompleteness/incompleteness-and-undecidability).

## Definability of a class of structures

Turn the relation around. A mathematics course usually opens by _defining_ its
objects: a group is a set with an operation satisfying certain axioms, a graph
is a set with a symmetric irreflexive edge relation, and so on. In each case
the objects are structures for a language, singled out as the models of a set
of sentences.

> **Definition (Elementary class).** For a set $\Sigma$ of sentences,
> $\mathbf{Mod}\,\Sigma$ is the class of all structures in which every member
> of $\Sigma$ is true. A class $K$ is an **elementary class** (EC) iff $K =
> \mathbf{Mod}\,\tau$ for a single sentence $\tau$, and an **elementary class in
> the wider sense** (EC$_\Delta$) iff $K = \mathbf{Mod}\,\Sigma$ for some set
> $\Sigma$. ("Elementary" is a synonym for "first-order.")

Many familiar classes are elementary. The graphs form $\mathbf{Mod}\,\tau$
where $\tau$ says $E$ is symmetric and irreflexive; the nonempty ordered sets
form $\mathbf{Mod}\,\tau$ for $\tau$ the conjunction of transitivity,
trichotomy, and asymmetry; the groups form $\mathbf{Mod}\,\tau$ for the
conjoined group axioms. The distinction between EC and EC$_\Delta$ is real. The
class of **infinite** groups is EC$_\Delta$ but, as
[compactness](/logic/models-and-theories/compactness-and-lowenheim-skolem) will
show, not EC: take the group axioms together with the sentences

$$
\lambda_n : \exists x_1 \cdots \exists x_n \bigwedge_{i < j} x_i \neq x_j
\quad(\text{``at least } n \text{ things''}),
$$

one for each $n$; their models comprise the infinite groups and nothing else, but no _single_
sentence has that class of models. Likewise the fields of characteristic zero
are EC$_\Delta$ (field axioms plus $\underbrace{1 + \cdots + 1}_{p} \neq 0$ for
every prime $p$) but not EC.

## Homomorphisms and isomorphisms

To compare two structures we map one universe into the other, asking the map to
respect the interpreted symbols.

> **Definition (Homomorphism).** A homomorphism $h$ of $\fA$ into
> $\fB$ is a function $h : |\fA| \to |\fB|$ such that
> for every predicate parameter $P$ and every tuple,
> $$
> \langle a_1, \dots, a_n\rangle \in P^{\fA} \iff
> \langle h(a_1), \dots, h(a_n)\rangle \in P^{\fB},
> $$
> and for every function symbol $f$, $\ h(f^{\fA}(a_1, \dots, a_n)) =
> f^{\fB}(h(a_1), \dots, h(a_n))$, which for a constant reads
> $h(c^{\fA}) = c^{\fB}$.

A one-to-one homomorphism is an **isomorphic embedding**; if it is also onto,
$\fA$ and $\fB$ are **isomorphic**, written $\fA
\cong \fB$. When $|\fA| \subseteq |\fB|$ and the
identity map is an isomorphic embedding — each $P^{\fA}$ is the
restriction of $P^{\fB}$, and likewise for functions and constants —
we call $\fA$ a **substructure** of $\fB$ and $\fB$
an **extension** of $\fA$. A substructure's universe must be closed
under every operation of the larger structure, constants included.

$$
% caption: An isomorphism relabels one structure onto another, sending the edge
% relation to the edge relation; the two carry identical first-order content.
\begin{tikzpicture}[font=\small, >=stealth,
  v/.style={draw, circle, minimum size=7mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{4A6FA5}
  % left structure
  \node[v] (a1) at (0,1.2) {$a$};
  \node[v] (a2) at (0,-0.4) {$b$};
  \node[v] (a3) at (1.4,0.4) {$c$};
  \draw[->] (a1) -- (a3);
  \draw[->] (a2) -- (a3);
  \node[font=\footnotesize, black] at (0.6,-1.4) {the structure $A$};
  % right structure
  \begin{scope}[xshift=6cm]
    \node[v] (b1) at (0,1.2) {$1$};
    \node[v] (b2) at (0,-0.4) {$2$};
    \node[v] (b3) at (1.4,0.4) {$3$};
    \draw[->] (b1) -- (b3);
    \draw[->] (b2) -- (b3);
    \node[font=\footnotesize, black] at (0.6,-1.4) {the structure $B$};
  \end{scope}
  % mapping arrows
  \draw[acc, ->, dashed] (a1) to[bend left=12] (b1);
  \draw[acc, ->, dashed] (a2) to[bend right=12] (b2);
  \draw[acc, ->, dashed] (a3) to[bend left=6] (b3);
  \node[acc, font=\footnotesize] at (3.6,1.9) {isomorphism $h$};
\end{tikzpicture}
$$

These are algebraic notions, but the following theorem ties them to
satisfaction.

> **Theorem (Homomorphism theorem).** Let $h$ be a homomorphism of
> $\fA$ into $\fB$ and $s : V \to |\fA|$.
>
> - **(a)** For any term $t$, $\ h(\bar{s}(t)) = \overline{h \circ s}(t)$.
> - **(b)** For any quantifier-free $\alpha$ without equality,
>   $\models_{\fA} \alpha[s]$ iff $\models_{\fB} \alpha[h
>   \circ s]$.
> - **(c)** If $h$ is one-to-one, part (b) holds with equality allowed.
> - **(d)** If $h$ is onto, part (b) holds with quantifiers allowed.

> **Proof.** Induction. Part (a) climbs the term. In (b), for an atomic
> $P t$, the homomorphism condition passes $\bar{s}(t) \in P^{\fA}$ to
> $h(\bar{s}(t)) \in P^{\fB}$, which by (a) is $\overline{h \circ s}(t)
> \in P^{\fB}$; connectives follow. Part (c) reverses the equality step,
> which needs injectivity. Part (d) adds the quantifier step, where surjectivity
> supplies, for each element of $|\fB|$, a preimage in $|\fA|$
> to instantiate.

## Elementary equivalence

Combining the strongest hypotheses of the homomorphism theorem — a bijection
respecting everything — gives the key semantic conclusion.

> **Definition (Elementary equivalence).** Structures $\fA$ and
> $\fB$ are **elementarily equivalent**, written $\fA \equiv
> \fB$, iff they satisfy the same sentences: $\models_{\fA}
> \sigma$ iff $\models_{\fB} \sigma$ for every $\sigma$.

> **Corollary.** Isomorphic structures are elementarily equivalent:
> $\fA \cong \fB \implies \fA \equiv \fB$.

An isomorphism is a bijective homomorphism, so parts (c) and (d) of the theorem
apply with no restriction, and every sentence transfers. In fact more is true:
isomorphic structures agree on second-order and higher sentences too. First-
order sentences cannot distinguish structures that are "the same up to
relabeling."

The converse fails, and its failure is central to model theory. The ordered
reals $(\mathbb{R}; <)$ and the ordered rationals $(\mathbb{Q}; <)$ are
elementarily equivalent — no first-order sentence in the language of order
separates them, a fact from
[Löwenheim–Skolem](/logic/models-and-theories/compactness-and-lowenheim-skolem).
But $\mathbb{Q}$ is countable and $\mathbb{R}$ is not, so they are not
isomorphic. First-order logic cannot distinguish cardinalities above the
finite range.

> **Worked example.** In the language of order, compare the positive integers
> $(\mathbb{P}; <)$ and the naturals $(\mathbb{N}; <)$. Show they are
> elementarily equivalent, then show the identity embedding of $\mathbb{P}$ into
> $\mathbb{N}$ transfers quantifier-free formulas but not quantified ones.
>
> The map $h(n) = n - 1$ is a strictly increasing bijection from $\mathbb{P}$
> onto $\mathbb{N}$, so it is an isomorphism: $(\mathbb{P}; <) \cong (\mathbb{N};
> <)$. By the corollary, $(\mathbb{P}; <) \equiv (\mathbb{N}; <)$; no
> first-order sentence separates them.
>
> The identity map $\mathrm{Id}: \mathbb{P} \to \mathbb{N}$ is an isomorphic
> embedding — every $\langle a, b\rangle$ with $a < b$ in $\mathbb{P}$ still has
> $a < b$ in $\mathbb{N}$. Part (c) of the homomorphism theorem gives, for
> quantifier-free $\varphi$ and any $s : V \to \mathbb{P}$,
> $$
> \models_{(\mathbb{P}; <)} \varphi[s]
> \quad\text{iff}\quad
> \models_{(\mathbb{N}; <)} \varphi[s].
> $$
> The equivalence breaks once quantifiers enter, because the embedding is not
> onto. Consider $\varphi = \forall v_2\,(v_1 \neq v_2 \rightarrow v_1 < v_2)$,
> "$v_1$ is a least element." Then
> $$
> \models_{(\mathbb{P}; <)} \varphi[[1]]
> \quad\text{but}\quad
> \not\models_{(\mathbb{N}; <)} \varphi[[1]],
> $$
> since $1$ is least in $\mathbb{P}$ but $0 < 1$ in $\mathbb{N}$. Passing to the
> larger universe adds a witness the quantifier can reach, so surjectivity —
> part (d) — supplies the hypothesis quantified formulas require.

$$
% caption: The ordered rationals and ordered reals satisfy exactly the same
% first-order sentences of order, yet differ in size, so they are elementarily
% equivalent without being isomorphic.
\begin{tikzpicture}[font=\small,
  b/.style={draw, minimum width=44mm, minimum height=17mm, align=center}]
  \definecolor{acc}{HTML}{4A6FA5}
  \node[b] (q) at (0,0) {ordered rationals $(\mathbb{Q}; <)$\\countable};
  \node[b] (r) at (7.2,0) {ordered reals $(\mathbb{R}; <)$\\uncountable};
  \draw[acc, thick, <->] (q) -- (r);
  \node[font=\footnotesize, acc] at (3.6,1.2) {same sentences};
  \node[font=\footnotesize, black] at (3.6,-1.5) {not isomorphic};
\end{tikzpicture}
$$

## Automorphisms and undefinability

An **automorphism** is an isomorphism of a structure onto itself. The identity
is always one; a structure with no others is **rigid**. Automorphisms give the
sharpest practical test for _un_-definability, because they must respect every
definable relation.

> **Corollary (Automorphisms preserve definability).** If $h$ is an
> automorphism of $\fA$ and $R$ is definable in $\fA$, then
> $\langle a_1, \dots, a_n\rangle \in R$ iff $\langle h(a_1), \dots,
> h(a_n)\rangle \in R$.

> **Proof.** One line from the homomorphism theorem: if $\varphi$ defines $R$,
> then $\models_{\fA} \varphi[[\bar{a}]]$ iff $\models_{\fA}
> \varphi[[h(\bar{a})]]$.

To prove a relation _not_ definable, exhibit an automorphism that moves it.

- In the ordered reals $(\mathbb{R}; <)$, the cubing map $h(a) = a^3$ is a
  strictly increasing bijection, hence an automorphism, and it sends points
  outside $\mathbb{N}$ into $\mathbb{N}$. So $\mathbb{N}$ is **not definable**
  in $(\mathbb{R}; <)$.
- In the small digraph $\fA = (\{a, b, c\};\, \{\langle a, b\rangle,
  \langle a, c\rangle\})$, the range $\{b, c\}$ is definable by $\exists v_2\,
  E v_2 v_1$, but the singleton $\{b\}$ is not: the map swapping $b$ and $c$ and
  fixing $a$ is an automorphism, so no formula can tell $b$ from $c$.

$$
% caption: In the digraph with edges from $a$ to $b$ and to $c$, swapping $b$
% and $c$ is an automorphism; it moves $\{b\}$, so $\{b\}$ is undefinable, while
% the fixed set $\{b,c\}$ is definable.
\begin{tikzpicture}[font=\small, >=stealth,
  v/.style={draw, circle, minimum size=8mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{4A6FA5}
  \node[v] (a) at (0,0.9) {$a$};
  \node[v] (b) at (-1.5,-0.9) {$b$};
  \node[v] (c) at (1.5,-0.9) {$c$};
  \draw[->] (a) -- (b);
  \draw[->] (a) -- (c);
  \draw[acc, <->, dashed, bend right=32] (b) to node[below, font=\footnotesize, acc] {swap preserves structure} (c);
\end{tikzpicture}
$$

> **Worked example.** In the digraph $\fA = (\{a, b, c\};\, E^{\fA})$ with
> $E^{\fA} = \{\langle a, b\rangle, \langle a, c\rangle\}$, prove $\{b\}$ is not
> definable, and contrast with $\{b, c\}$, which is.
>
> Let $h$ swap $b$ and $c$ and fix $a$. Check it is an automorphism: the edge
> set $\{\langle a, b\rangle, \langle a, c\rangle\}$ maps to $\{\langle a,
> c\rangle, \langle a, b\rangle\}$, the same set, so $h$ preserves $E^{\fA}$
> and is a bijection of the universe. Suppose some $\varphi(v_1)$ defined
> $\{b\}$. By the corollary an automorphism preserves every definable relation,
> so $b \in \{b\}$ would force $h(b) = c \in \{b\}$ — false. No such $\varphi$
> exists, and $\{b\}$ is undefinable.
>
> The set $\{b, c\}$ escapes the obstruction because $h$ fixes it setwise:
> $h(\{b, c\}) = \{c, b\} = \{b, c\}$. And it is definable outright, as the range
> of the edge relation:
> $$
> \{b, c\} = \{x : \models_{\fA} \exists v_2\, E v_2 v_1\,[[x]]\}.
> $$
> Definability needs a formula invariant under every automorphism; $\{b, c\}$
> has one and $\{b\}$ cannot.

The same reasoning shows the length of a plane vector is not definable from
vector addition and scalar multiplication: doubling every vector is an
automorphism of that structure but changes lengths, so the set of unit vectors
is undefinable.

$$
% caption: The cubing map is a strictly increasing bijection of the real line,
% hence an automorphism of $(\mathbb{R}; <)$; it carries the non-integer point
% $\sqrt[3]{2}$ onto the integer $2$, so the set of naturals is not preserved and
% cannot be definable.
\begin{tikzpicture}[font=\small, >=stealth]
  \definecolor{acc}{HTML}{4A6FA5}
  \draw[->, black] (-0.4,0) -- (5.0,0);
  \foreach \x in {0,1,2,3,4} \draw[black] (\x,0.08) -- (\x,-0.08);
  \foreach \x in {0,1,2,3,4} \node[font=\footnotesize, black, anchor=north] at (\x,-0.12) {$\x$};
  \foreach \x in {0,1,2,3,4} \fill[black] (\x,0) circle (1.6pt);
  \fill[acc] (1.26,0) circle (2pt);
  \node[acc, font=\footnotesize, anchor=south] at (1.26,0.1) {a cube root};
  \draw[acc, ->, thick] (1.26,0.34) .. controls (1.6,1.1) and (1.7,1.1) .. (2,0.34);
  \node[acc, font=\footnotesize, anchor=south] at (1.7,0.95) {cubing};
  \node[black, font=\footnotesize, anchor=north] at (2.4,-0.9) {a non-integer lands on an integer};
\end{tikzpicture}
$$

## Two kinds of definability

Definability of a relation and definability of a class run in parallel, and
keeping them apart prevents confusion.

| | Definable relation | Elementary class |
| --- | --- | --- |
| Fixed | one structure $\fA$ | one language |
| Varies | the formula $\varphi$ | the structure |
| Object defined | a relation on $\lvert\fA\rvert$ | a class of structures |
| Tool for limits | automorphisms move it | compactness (later) |
| Example | primes in $\fN$ | groups, ordered sets |

The obstruction in each column is a symmetry the language cannot detect.
Automorphisms bound what one structure's formulas distinguish; compactness,
developed with the
[completeness theorem](/logic/deductive-calculus/completeness-and-consistency),
bounds which classes a set of sentences can axiomatize. Both definability notions,
and the satisfaction recursion behind them, rest on unique readability — the
[parsing and substitution](/logic/first-order-languages/terms-substitution-and-parsing)
results that justify defining a function by recursion on a wff.