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 exactly three 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
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
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
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
Three theorems — what all of this was built for
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.
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
\(\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.