A Zoo of Maps Between Models
Partial isomorphism, embedding, elementary embedding, isomorphism, elementary submodel, automorphism, homogeneity, the Ehrenfeucht–Fraïssé game — one picture.
What's going on here
Every notion on this page is built from the same raw material: a map \(f:A\to N\), where \(A\subseteq M\).
Each notion is a conjunction of a handful of atomic conditions on that map
(what its domain is, whether it's injective, exactly what it must preserve). On top of the definitions
sit key theorems that link the notions not by definition, but substantively —
and that's where the real mathematics of this subject lives.
solid card border — the notion is the listed conditions, by definition
dashed and colored — a theorem: follows from the conditions, but not by definition
Atomic conditions — everything else is built from these
fin — domain is finite: \(|A|<\omega\)
partκ — domain is partial, bounded by a cardinal κ: \(A\subseteq M\), \(|A|<\kappa\)
tot — domain is total: \(\operatorname{dom} f = M\)
inj — injectivity of \(f\)
surj — surjectivity onto \(N\) (bijection)
atom — preserves atomic formulas (= the signature)
allf — preserves all formulas (elementarity)
M=N — a model mapped into itself
M⊆N,id — \(M\subseteq N\), \(f=\mathrm{id}_M\)
ext — \(M,N\) arbitrary (external) domains
inj isn't an independent condition here: preserving the atomic formula \(x=y\) means the
equivalence \(a=b \iff f(a)=f(b)\) holds, and the reverse implication \(f(a)=f(b)\Rightarrow a=b\) is exactly
injectivity. So inj is an automatic consequence of atom (and hence of allf
too), not an independent tag. For the same reason, surj together with atom or
allf immediately gives a bijection, not just a surjection — hence the "(bijection)" in the
description of surj above.
1Level 1 — basic notions: domain + injectivity + depth of preservation
Partial isomorphism
\(f:A\to N\)
partκatom
e.g. any finite increasing \(f:A\to\Q\), \(A\subseteq\Q\)
Elementary partial map
\(f:A\to N\)
partκallf
Embedding
\(f:\mathcal M\hookrightarrow\mathcal N\)
totatom
Elementary embedding
\(f:\mathcal M\preccurlyeq\mathcal N\)
totallf
Isomorphism
\(f:\mathcal M\cong\mathcal N\)
totsurjatom
e.g. \(x\mapsto x/2\): \(2\Z\cong\Z\) —
more
Theorem (preservation under isomorphisms): every isomorphism automatically preserves
all formulas, not just the atomic ones — i.e. Isomorphism ⟹ Elementary embedding, even though
elementarity is never mentioned in the definition of isomorphism.
2Level 2 — specializing the carrier sets
Elementary submodel
\(\mathcal M\preccurlyeq\mathcal N\), \(M\subseteq N\)
elem. embedding+ M⊆N,id
Proper elem. self-embedding
\(M\hookrightarrow M\), not a bijection
elem. embedding+ M=N
Automorphism
\(\alpha\in \operatorname{Aut}(\mathcal M)\)
isomorphism+ M=N
e.g. \(\alpha(x)=x+c\) on \(\langle\Z;<\rangle\)
3Level 3 — the third dimension: extendability ("back-and-forth")
\(\kappa\)-homogeneity
every \(f\) extends to \(A\cup\{c\}\)
elem. partial map+ M=N
Strong \(\kappa\)-homogeneity
every \(f\) extends to an automorphism
elem. partial map+ M=N+ automorphism
EF game
partial isomorphism extends "back-and-forth" \(\forall n<\omega\)
partial isomorphism+ fin+ ext
Key theorems — elementarity, homogeneity, saturation
Ehrenfeucht–Fraïssé theorem
The EF game is won at every round ⟹ \(\mathcal M\equiv\mathcal N\) (elementary equivalence).
Mono-orbitality of types
Strong homogeneity ⟹ \(\operatorname{Orb}_{\operatorname{Aut}(\mathcal M)}(\vec a) = P[\operatorname{tp}(\vec a)]\) — automorphism orbits coincide with the sets of realizations of a type.
Universality of the monster model
If \(\mathfrak M\models T\) and \(|M|<\kappa\), there is an elementary embedding
\(f:\mathfrak M\preccurlyeq\mathfrak C\) into any fixed \(\kappa\)-saturated model \(\mathfrak C\models T\)
(a "monster model"). The monster model, in effect, pulls in every model of \(T\) of bounded cardinality —
each of them lives inside \(\mathfrak C\) as an elementary submodel.
Isomorphism of saturated models
\(\mathcal M,\mathcal N\) saturated, same cardinality, \(\mathcal M\equiv\mathcal N\) ⟹ \(\mathcal M\cong\mathcal N\).
⟲ and we're back to the isomorphism Level 1 started with — the loop closes: under saturation, syntax (elementary equivalence) fully determines algebra (isomorphism).
Examples — what this looks like on concrete models
\(\mathrm{id}:\Z\to\R\) — an embedding that isn't elementary
The identity map from the ring \(\langle\Z;+,\cdot\rangle\) into the field \(\langle\R;+,\cdot\rangle\)
preserves the signature and so is an embedding. But the formula \(\exists y(y\cdot y=x)\) is true in \(\R\)
at \(x=2\) (witness \(\sqrt2\)), while it's false in \(\Z\): \(2\) simply has no integer square root. The
type of the element \(2\) changes when passing from \(\Z\) to \(\R\): \(\mathrm{id}\) is an embedding, but
not an elementary one. The gap between the atom and allf badges is exactly one
formula like this with a quantifier.
\(2\Z\subseteq\Z\) — a submodel, but not an elementary one
\(2\Z=\{\dots,-4,-2,0,2,4,\dots\}\) with the same operations is a submodel of \(\langle\Z;+,\cdot\rangle\),
and the map \(x\mapsto x/2\) is an isomorphism \(2\Z\cong\Z\), hence \(2\Z\equiv\Z\). But the identity
embedding \(\mathrm{id}:2\Z\subseteq\Z\) is not elementary: the formula \(\exists y(y+y=x)\) ("\(x\) is
divisible by \(2\)") is true in \(\Z\) at \(x=2\) (\(y=1\)), but false inside \(2\Z\) itself at the same
\(x=2\) — the only candidate \(y=1\) doesn't lie in \(2\Z\). The existence of some elementary
embedding (an isomorphism, here) does not make \(2\Z\) an elementary submodel — that requires the identity
inclusion itself to be elementary.
\(\Q\to\Q\) — a proper elementary self-embedding
On \(\langle\Q;<\rangle\) (in \(\mathrm{DLO}\), elementarity of an embedding reduces to preserving the
order), the map \(f(x)=\dfrac{x}{1+|x|}\) is strictly increasing and injects \(\Q\) into
\((-1,1)\cap\Q\subsetneq\Q\). So \(f:\Q\hookrightarrow\Q\) preserves every formula but isn't surjective —
a proper elementary self-embedding, with no transfinite construction needed.
\(\langle\Z;<\rangle\) — homogeneity and mono-orbitality
The automorphisms of \(\langle\Z;<\rangle\) are exactly the shifts \(\alpha(x)=x+c\), \(c\in\Z\). Any finite
elementary map \(f:A\to\Z\) preserves pairwise distances (the formula "exactly \(k\) apart" for each \(k\)),
so \(f(a)-a\) is the same constant for every \(a\in A\): \(f\) is a restriction of a shift, and a shift is
already a global automorphism. The model is strongly \(\aleph_0\)-homogeneous with no transfinite recursion
needed at all, and by mono-orbitality every \(n\)-type is realized by exactly one orbit of
\(\operatorname{Aut}(\langle\Z;<\rangle)\) — there are infinitely many of them, one per distance
\(d\in\Z\) between a pair of points.
\(\langle\R\setminus\{0\};<\rangle\) — homogeneous without being strongly homogeneous
The map \(1\mapsto-1\) is elementary (in \(\mathrm{DLO}\), elementarity of a partial map reduces to
preserving the order), and the model is \(\aleph_0\)-homogeneous — any finite map extends to a new point.
But \(1\mapsto-1\) does not extend to an automorphism: the gap at zero is the model's only unfilled "hole,"
an automorphism must send a gap to a gap, and so it can't swap the negative and positive halves. The gap
between homogeneity and strong homogeneity isn't pedantry over definitions — it's a real fact,
already visible at this countable, purely local check.
\(\Q\preccurlyeq\R\) — an elementary submodel
\(\langle\Q;<\rangle\preccurlyeq\langle\R;<\rangle\) in the theory \(\mathrm{DLO}\): any equation with
parameters from \(\Q\) that's solvable in \(\R\) is solvable in \(\Q\) too — density of the rationals
guarantees a witness. This immediately gives \(\Q\equiv\R\), even though \(|\Q|\ne|\R|\) and hence
\(\Q\not\cong\R\) — the hierarchy "isomorphism \(\Rightarrow\) elementary embedding \(\Rightarrow\)
elementary equivalence" strictly weakens in strength already on this one pair.