Climb into Cantor’s Attic, where you will find infinities large and small. We aim to provide a comprehensive resource of information about all notions of mathematical infinity.
View the Project on GitHub neugierde/cantors-attic
Quick navigation
The upper attic
The middle attic
The lower attic
The parlour
The playroom
The library
The cellar
Sources
Cantor's Attic (original site)
Joel David Hamkins blog post about the Attic
Latest working snapshot at the wayback machine
Given two transitive structures $\mathcal{M}$ and $\mathcal{N}$, an elementary embedding from $\mathcal{M}$ to $\mathcal{N}$ is a function $j:\mathcal{M}\to\mathcal{N}$ such that $j(\mathcal{M})$ is an elementary substructure of $\mathcal{N}$, i.e. satisfies the same first-order sentences as $\mathcal{N}$ does. Obviously, if $\mathcal{M}=\mathcal{N}$, then $j(x)=x$ is an elementary embedding from $\mathcal{M}$ to itself, but is then called a trivial embedding. An embedding is nontrivial if there exists $x\in\mathcal{M}$ such that $j(x)\neq x$.
The critical point is the smallest ordinal moved by $j$. By $j$’s elementarity, $j(\kappa)$ must also be an ordinal, and therefore it is comparable with $\kappa$. It is easy to see why $j(\kappa)\leq\kappa$ is impossible, thus $j(\kappa)>\kappa$.
Given two transitive classes $\mathcal{M}$ and $\mathcal{N}$, and a function $j:\mathcal{M}\rightarrow\mathcal{N}$, $j$ is an elementary embedding if and only if for every first-order formula $\varphi$ with parameters $x_1,…,x_n\in\mathcal{N}$, one has: \(\\mathcal{M}\\models\\varphi(x\_1,...,x\_2)\\iff\\mathcal{N}\\models\\varphi(j(x\_1),...,j(x\_2))\)
$j$ is nontrivial if and only if it has a critical point, i.e. $\exists\kappa(j(\kappa)\neq\kappa)$. Indeed, one can show by transfinite induction that if $j$ does not move any ordinal then $j$ does not move any set at all, thus a critical point must exists whenever $j$ is nontrivial.
If $\mathcal{M}$ and $\mathcal{N}$ are both $\tau$-structures for some language $\tau$, and $j:\mathcal{M}\rightarrow\mathcal{N}$, then $j$ is an elementary embedding iff:
The Tarski-Vaught test refers to the special case where $\mathcal{M}$ is a substructure of $\mathcal{N}$ and $j(x)=x$ for every $x$.
This test determines if $\mathcal{M}$ is an elementary substructure of $\mathcal{N}$. More specifically, $\mathcal{M}$ is an elementary substructure of $\mathcal{N}$ iff for any $\psi$ and $x_0,x_1…\in M$ such that there is $y\in N$ with $\psi^\mathcal{N}(y,x_0,x_1…)$, there is $z\in M$ with $\psi^\mathcal{M}(z,x_0,x_1…)$.
There are two ways of making the critical point as large as possible:
Using the first method, one can simply take $\mathcal{M}=V$ (the universe of all sets), and the resulting critical point is always a measurable cardinal, a very strong type of large cardinal, e.g. the first measurable is larger than infinitely many weakly compact cardinals (and much more).
Using the second method, one can take, say, $\mathcal{M} = \mathcal{N} = L$, i.e. create an embedding $j:L\to L$, whose existence has very important consequences, such as the existence of $0^#$ (and thus $V\neq L$) and implies that every ordinal that is an uncountable cardinal in V is strongly inaccessible in L. By taking $\mathcal{M}=\mathcal{N}=V_\lambda$, i.e. a rank of the cumulative hiearchy, one obtains the very powerful rank-into-rank axioms, which sit near the very top of the large cardinal hiearchy. However, this second method has its limits, as shown by Kunen, as he showed that $\mathcal{M}=\mathcal{N}=V$ leads to an inconsistency with the axiom of choice, a theorem now known as the Kunen inconsistency. He also showed that a natural strengthening of the rank-into-rank axioms, $\mathcal{M}=\mathcal{N}=V_{\lambda+2}$ for some $\lambda\in Ord$, was inconsistent with the $AC$.
Most large cardinal axioms inbetween measurables and rank-into-rank axioms are obtained by mixing those two methods: one usually sets $\mathcal{M}=V$ then requires $\mathcal{N}$ to satisfies strong closure properties to make it “larger”, i.e. closer to $V$ (that is, to $\mathcal{M}$). For example, $j:V\to\mathcal{N}$ is nontrivial with critical point $\kappa$ and the cumulative hiearchy rank $V_{j(\kappa)}$ is a subset of $\mathcal{N}$ then $\kappa$ is superstrong; if $\mathcal{N}$ contains all sequences of elements of $\mathcal{N}$ of length $\lambda$ for some $\lambda>\kappa$ then $\kappa$ is $\lambda$-supercompact, and so on.
The existence of a nontrivial elementary embedding $j:\mathcal{M}\to\mathcal{N}$ that is definable in $\mathcal{M}$ implies that the critical point $\kappa$ of $j$ is measurable in $\mathcal{M}$ (not necessarily in $V$). Every measurable ordinal is weakly compact and (strongly) inaccessible therefore its existence in any model is beyond $ZFC$, meaning that $ZFC$ cannot prove that such an embedding exists.
Here are some types of cardinals whose definition uses elementary embeddings:
The wholeness axioms also asserts the existence of elementary embeddings, though the resulting larger cardinal has no particular name. Vopěnka’s principle is about elementary embeddings of set models.
The following results can be used in theorems about remarkable cardinals and other virtual variants.
(section from (Bagaria, 2017) unless otherwise noted)
The existence of an embedding of a countable model into another fixed model is absolute:
Therefore an elementary embedding $j : B → A$ between first-order structures exists in some set-forcing extension iff it already exists in $V^{Coll(ω,B)}$. Specifically, the following are equivalent for structures $B$ and $A$:
Moreover, if $B$ and $A$ are transitive $∈$-structures, we can assume that the embeddings have the same critical point and agree on finitely many fixed values.
These are also equivalent to player II having a winning strategy in game $G(B, A)$ defined in the following subsection.
Next fact: For first-order structures $M$ and $N$ in a common language, if there is an elementary embedding $j : M → N$ in some set-forcing extension, then there is such an embedding $j^∗ : M → N$ in any forcing extension in which $M$ has been made countable. Moreover, one can arrange that $j^∗$ agrees with $j$ on any given finite set of values and that, if appropriate, $crit(j) = crit(j^*)$.(Gitman & Hamkins, 2018)
To every pair of structures B and A of the same type, one can associate a closed game $G(B, A)$ (variant of an Ehrenfeucht-Fraı̈ssé game) such that $B$ elementarily embeds into $A$ in $V^{Coll(ω,B)}$ precisely when a particular player has a winning strategy in that game. Namely:
The game $G(B, A)$ is a game of length $ω$, where player I starts by playing some $b_0 ∈ B$ and player II responds by playing $a_0 ∈ A$. Players I and II continue to alternate, choosing elements $b_n$ and $a_n$ from their respective structures at stage $n$ of the game. II wins if for every $(n+1)$-parameter formula $φ$
$B \models φ(b_0 , . . . , b_n ) \iff A \models φ(a_0 , . . . , a_n)$
and I wins otherwise.
Since if II loses he must do so at some finite stage of the game, the game $G(B, A)$ is closed and hence determined by the Gale-Stewart theorem (Gale and Stewart, 1953). Thus, either I or II has a winning strategy.
Player II has a winning strategy precisely when $B$ elementarily embeds into $A$ in $V^{Coll(ω,B)}$. It follows that each first-order fragment of Generic Vopěnka’s Principle is characterised by the existence of certain winning strategies in its associated class of closed games.