Elementary embedding

From Cantor's Attic
Revision as of 02:57, 28 September 2019 by BartekChom (Talk | contribs) (Use in Large Cardinal Axioms: fact)

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.

Absoluteness

(section from [1])

The existence of an embedding of a countable model into another fixed model is absolute:

  • For a countable first-order structure $M$ and an elementary embedding $j : M → N$, if $W ⊆ V$ is a transitive (set or class) model of (some sufficiently large fragment of) ZFC such that $M$ is countable in $W$ and $N ∈ W$, then $W$ has some elementary embedding $j^∗ : M → N$.
  • If additionally both $M$ and $N$ are transitive $∈$-structures, we can assume that $crit(j^∗) = crit(j)$.
  • We can also require that $j$ and $j^∗$ agree on some fixed finite number of values.

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

  • There is a complete Boolean algebra $\mathbb{B}$ such that
    $V^\mathbb{B} \models$ “There is an elementary embedding $j : B → A$.”
  • In $V^Coll(ω,B)$ there is an elementary embedding $j : B → A$.
  • For every complete Boolean algebra $\mathbb{B}$,
    $V^\mathbb{B} \models$ “$|B| = \aleph_0 \implies$ There is an elementary embedding $j : B → 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.