Elementary embedding

From Cantor's Attic
Jump to: navigation, search

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$.

Definition

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.

Tarski-Vaught Test

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:

  1. $j$ is injective (for any $x$ in $N$, there is at most one $y$ in $M$ such that $j(y)=x$).
  2. $j$ has the following properties:
    1. For any constant symbol $c\in\tau$, $j(c^\mathcal{M})=c^\mathcal{N}$.
    2. For any function symbol $f\in\tau$ and $a_0,a_1...\in M$, $j(f^\mathcal{M}(a_0,a_1...))=f^\mathcal{N}(j(a_0),j(a_1)...)$. For example, $j(a_0+^\mathcal{M}a_1)=j(a_0)+^\mathcal{N}j(a_1)$.
    3. For any relation symbol $r\in\tau$ and $a_0,a_1...\in M$, $r^\mathcal{M}(a_0,a_1...)\Leftrightarrow r^\mathcal{N}(j(a_0),j(a_1)...)$
  3. For any first-order formula $\psi$ and any $x_0,x_1...\in M$ such that there is $y\in N$ with $\psi^\mathcal{N}(y,j(x_0),j(x_1)...)$, there is $z\in M$ with $\psi^\mathcal{M}(z,x_0,x_1...)$.

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...)$.

Use in Large Cardinal Axioms

There are two ways of making the critical point as large as possible:

  1. Making $\mathcal{M}$ as large as possible, much larger than $\mathcal{N}$ (meaning that a "large" class can be embedded into a smaller class)
  2. Making $\mathcal{M}$ and $\mathcal{N}$ more similar (for example, $\mathcal{M} = \mathcal{N}$ yet $j$ is nontrivial)

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.