Definability and Elementary Equivalence

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.

Definability lets a structure express more than its named parameters suggest. Take the real field $R = (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

⊨_{R} \exists v_{2} v_{1} = v_{2} \cdot v_{2} [[a]] \leftrightarrow a \geq 0,

and the formula $\exists v_{3} v_{2} = v_{1} + v_{3} \cdot v_{3}$ defines ${⟨ a, b ⟩ : a \leq b}$ . The ordering was there implicitly, recoverable from addition and multiplication.

A defining formula

φ (x)

splits the universe

∣ A ∣

into the tuples that satisfy it — the set

φ

defines, shaded — and those that do not.

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

The order ${⟨ m, n ⟩ : 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}) \land \forall v_{2} \forall v_{3} (v_{1} = v_{2} \cdot v_{3} \to v_{2} = S 0 \lor v_{3} = S 0) .$
Even exponentiation ${⟨ m, n, p ⟩ : p = m^{n}}$ is definable, though the proof needs the Chinese remainder theorem and waits until 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.

Not everything is definable, and a counting argument shows why without exhibiting a single example: there are uncountably many relations on $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 $N$ , comes with Tarski's theorem.

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.

Many familiar classes are elementary. The graphs form $Mod τ$ where $τ$ says $E$ is symmetric and irreflexive; the nonempty ordered sets form $Mod τ$ for $τ$ the conjunction of transitivity, trichotomy, and asymmetry; the groups form $Mod τ$ for the conjoined group axioms. The distinction between EC and EC $_{Δ}$ is real. The class of infinite groups is EC $_{Δ}$ but, as compactness will show, not EC: take the group axioms together with the sentences

λ_{n} : \exists x_{1} \dots \exists x_{n} i < j ⋀ x_{i} \neq = x_{j} (“at least n 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 $_{Δ}$ (field axioms plus $p 1 + \dots + 1 \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.

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

An isomorphism relabels one structure onto another, sending the edge relation to the edge relation; the two carry identical first-order content.

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

Elementary equivalence

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

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 $(R; <)$ and the ordered rationals $(Q; <)$ are elementarily equivalent — no first-order sentence in the language of order separates them, a fact from Löwenheim–Skolem. But $Q$ is countable and $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 $(P; <)$ and the naturals $(N; <)$ . Show they are elementarily equivalent, then show the identity embedding of $P$ into $N$ transfers quantifier-free formulas but not quantified ones.

The map $h (n) = n - 1$ is a strictly increasing bijection from $P$ onto $N$ , so it is an isomorphism: $(P; <) ≅ (N; <)$ . By the corollary, $(P; <) \equiv (N; <)$ ; no first-order sentence separates them.

The identity map $Id : P \to N$ is an isomorphic embedding — every $⟨ a, b ⟩$ with $a < b$ in $P$ still has $a < b$ in $N$ . Part (c) of the homomorphism theorem gives, for quantifier-free $φ$ and any $s : V \to P$ ,

⊨_{(P; <)} φ [s] iff ⊨_{(N; <)} φ [s] .

The equivalence breaks once quantifiers enter, because the embedding is not onto. Consider $φ = \forall v_{2} (v_{1} \neq = v_{2} \to v_{1} < v_{2})$ , $v_{1}$ is a least element. Then

⊨_{(P; <)} φ [[1]] but \neq ⊨_{(N; <)} φ [[1]],

since $1$ is least in $P$ but $0 < 1$ in $N$ . Passing to the larger universe adds a witness the quantifier can reach, so surjectivity — part (d) — supplies the hypothesis quantified formulas require.

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.

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.

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

In the ordered reals $(R; <)$ , the cubing map $h (a) = a^{3}$ is a strictly increasing bijection, hence an automorphism, and it sends points outside $N$ into $N$ . So $N$ is not definable in $(R; <)$ .
In the small digraph $A = ({a, b, c}; {⟨ a, b ⟩, ⟨ a, c ⟩})$ , 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$ .

In the digraph with edges from

a

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.

Worked example. In the digraph $A = ({a, b, c}; E^{A})$ with $E^{A} = {⟨ a, b ⟩, ⟨ a, c ⟩}$ , 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 ${⟨ a, b ⟩, ⟨ a, c ⟩}$ maps to ${⟨ a, c ⟩, ⟨ a, b ⟩}$ , the same set, so $h$ preserves $E^{A}$ and is a bijection of the universe. Suppose some $φ (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 $φ$ 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 : ⊨_{A} \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.

The cubing map is a strictly increasing bijection of the real line, hence an automorphism of

(R; <)

; it carries the non-integer point

32

onto the integer

2

, so the set of naturals is not preserved and cannot be definable.

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 $A$	one language
Varies	the formula $φ$	the structure
Object defined	a relation on $∣ A ∣$	a class of structures
Tool for limits	automorphisms move it	compactness (later)
Example	primes in $N$	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, 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 results that justify defining a function by recursion on a wff.