An absoluteness lemma for countable embeddings

If $W$ is a transitive set or class and it thinks that there is an elementary embedding $j$ between some first-order structures $\mathcal M$ and $\mathcal N$, then $j$ is an actual elementary embedding and so the universe $V$ agrees that this is the case. Technically speaking, the existence of elementary embeddings between first-order structures is upwards absolute between transitive sets or classes. At this point, the reader's well-honed set theoretic intuition should immediately warn against the possibility of downward absoluteness. If some larger model with lots more sets has an elementary embedding between two structures, there is no reason to suppose that a smaller poorer model would have one as well. It is not difficult to come up with counterexamples, so let's look at some, where the first-order structures are themselves models of set theory.

If $0^\sharp$ exists, then $V$ has a nontrivial elementary embedding $j:L_{\gamma}\to L_\delta$ for some $L$-cardinal $\gamma$ (with critical point $\kappa<\gamma$), but no such embedding can exist in $L$ because the ultrapower of $L$ by the ultrafilter $U$ generated from such an embedding $(U=\{A\mid \kappa\in j(A)\})$ is well-founded (this needs an argument), and therefore Mostowski collapses to give an elementary embedding $j:L\to L$ that is definable in $L$, which violates the Kunen Inconsistency [1].

Other examples can be obtained by collapsing cardinals in a forcing extension. One of the prettiest results in the model theory of set theoretic structures (and models of ${\rm PA}$) states that any two countable computably saturated models of ${\rm ZFC}$ with the same theory and standard system must be isomorphic. The standard system of a model of ${\rm ZFC}$ consists of the standard initial segments of its reals (viewed as sequences of 0s and 1s). A model of ${\rm ZFC}$ is computably saturated if it already realizes all finitely realizable computable types (with parameters), where a type is computable if the collection of Gödel codes of its formulas is computable. Obviously no model of size $\omega_1$ can embed into a countable model. So let's suppose we have a countable computably saturated $N\models{\rm ZFC}$ and a computably saturated $M\models{\rm ZFC}$ of size $\omega_1$ such that $M$ and $N$ are elementarily equivalent and have the same standard system. This is possible because fixing $N$, we can elementarily top-extend it $\omega_1$-many times to produce the required model $M$ (see this post on $\omega_1$-like models). To ensure that $M$ is computably saturated, we use a deep theorem stating that a countable model $N$ is computably saturated if and only if it has a truth predicate $T\subseteq N$ such that $(N,\in,T)\models{\rm ZFC}$ [2], and instead of top-extending just $(N,\in)$, we top-extend $(N,\in,T)$. Because the final model $M$ has a truth predicate, it must be computably saturated (this easy direction does not require countability). So now go to a forcing extension $V[G]$, where $\omega_1$ is collapsed to $\omega$. There $M$ and $N$ are countable elementarily equivalent computably saturated models with the same standard system and therefore isomorphic!

Now having the counterexamples out of the way, we can get to the point of this post. The existence of an elementary embedding between structures $\mathcal M$ and $\mathcal N$ is downward absolute so long as $M$ is countable!

Absoluteness Lemma: Suppose that $\mathcal M$ and $\mathcal N$ are countable first-order structures and $j:M\to N$ is an elementary embedding. If $W\subseteq V$ is a transitive (set or class) model of ${\rm ZFC}^-$ such that $\mathcal M$ is countable in $W$ and $\mathcal N\in W$, then $W$ has some elementary embedding $j^*:M\to N$. Furthermore, if $M$, $N$ are transitive models of set theory, $\text{cp}(j)=\gamma$ and $j(\gamma)=\delta$, we can additionally assume that $\text{cp}(j^*)=\gamma$ and $j^*(\gamma)=\delta$. Also, we can assume that $j$ and $j^*$ agree on some fixed finite number of values.

Proof: Fix some enumeration $M=\langle a_i\mid i\in\omega\rangle$ that exists in $W$. Say that a sequence $\langle b_0,\ldots,b_{n-1}\rangle$ of elements of $N$ is a finite partial embedding if for every formula $\varphi(x_0,\ldots,x_{n-1})$, we have that

$\mathcal M\models\varphi(a_0,\ldots,a_{n-1})\Leftrightarrow \mathcal N\models\varphi(b_0,\ldots,b_{n-1})$

Let $T$ consist of all finite partial embeddings. Observe that $T$ is clearly a tree under the natural ordering by extension and it has height at most $\omega$. Also, $T$ is an element of $W$. Clearly any cofinal branch through $T$ gives an embedding $h:M\to N$. Let $c_i=j(a_i)$. Every sequence $\langle c_0,\ldots,c_{n-1}\rangle$ is a partial finite embedding in $W$ and the collection $\langle c_i\mid i\in\omega\rangle$ is a cofinal branch through $T$ in $V$. Thus, the tree $T$ is ill-founded in $V$. But then $T$ must be ill-founded in $W$ as well because otherwise $W$ would have rank function for $T$ and this rank function would attest to its well-foundedness in $V$. Thus, $W$ has a cofinal branch through $T$ and this branch gives some embedding $j^*:M\to N$. To achieve that $j$ and $j^*$ agree on the critical point, we limit the tree $T$ to partial finite embeddings fixing all $\alpha$ below the critical point of $j$ and having $b_n=\delta$, where $a_n=\gamma$. An agreement on some finitely many values is achieved similarly. $\square$

I learned about this folklore absoluteness lemma while working with remarkable cardinals, many of whose remarkable properties tend to magically materialize out of its application. This proof came out of a discussion with Joel Hamkins, who interrupted my convoluted argument with his usual "but wait, isn't it like this...." and everything quickly became crystal clear.

References

  1. T. Jech, Set theory. Berlin: Springer-Verlag, 2003, p. xiv+769.
  2. R. Kaye, Models of Peano arithmetic, vol. 15. The Clarendon Press, Oxford University Press, New York, 1991, p. x+292.