Shoenfield Absoluteness and Choice

Absoluteness of wellfoundedness and Shoenfield absoluteness are two absoluteness results in set theory that are both used incredibly often. But what if we want to apply the result to absoluteness between arbitrary models $M$ and $N$, rather than absoluteness between $V$ and $L$? It turns out that our models have to satisfy dependent choice in both absoluteness results, and in Shoenfield absoluteness we have to ensure that the models are of “similar height”.

We start with the absoluteness of wellfoundedness, where the following standard proof turns out to not require power set, but do require DC.

Theorem (Absoluteness of wellfoundedness). Let $R\subseteq X\times X$ be a binary relation on some set $X$. Then wellfoundedness of $R$ is absolute between transitive models of $\textsf{ZF}^-+\textsf{DC}$.

Proof. It suffices to show that wellfoundedness of a binary relation $R$ can be described in a $\Delta_1^{\textsf{ZF}^-+\textsf{DC}}$ fashion.

Firstly wellfoundedness of $R$ is equivalent (over $\textsf{ZF}^-+\textsf{DC}$) to there being no function $f:\omega\to X$ such that $f(n+1)Rf(n)$ for all $n<\omega$, which is clearly a $\Pi_1$ statement. Secondly, wellfoundedness of $R$ is also equivalent (over $\textsf{ZF}^-$) to there existing a ranking function $r:X\to\textsf{On}$; i.e., that $r(x)=\sup\{r(y)+1\mid yRx\}$, which is a $\Sigma_1$ statement. QED

In the above proof we only needed DC to show the $\Pi_1$ part, meaning that wellfoundedness is always downwards absolute between transitive models of $\textsf{ZF}^-$. The next few lemmas lead up to Shoenfield absoluteness, where they treat $\Pi^0_1(x)=\Pi^1_0(x)$ sets and $\Pi^1_1(x)$ sets, respectively.

Lemma (ZF+DC). Let $x\in\mathbb R$. Then for every $\Pi^0_1(x)$ set $A\subseteq\mathbb R^n$ there’s a tree $T\in L[x]$ on $\omega^n$ such that $A=[T]$.

Proof. For notational ease let’s assume that $n=1$. Let $A=\{z\in\mathbb R\mid\forall k<\omega:\varphi(z\upharpoonright k,x)\}$ for $\varphi(u,v)$ a $\Pi^0_1$ formula, and define

$$ T:=\{s\in{^{<\omega}\omega}\mid\exists y\in A: s\subseteq y\}. $$

Note that $T\in L[x]$ and clearly $A\subseteq[T]$, so let $y\in [T]$. Then $y\upharpoonright n\in T$ for all $n<\omega$, so that $\textsf{DC}$ implies that there’s a sequence $\left< y_k\mid k<\omega\right<$ of $y_k\in A$ such that $y\upharpoonright k\subseteq y_k$, which implies that $\varphi(y\upharpoonright k,x)$ holds for all $k<\omega$, making $y\in A$. QED

Lemma (ZF+DC). Let $x\in\mathbb R$. Then every $\Pi^1_1(x)$ set $A\subseteq\mathbb R^n$ is the projection of a tree $S\in L[x]$ on $\omega^n\times\omega_1$.

Proof. Assume for notational simplicity that $n=1$. Let $A\subseteq\mathbb R$ be $\Pi^1_1(x)$, so that $\mathbb R\setminus A=pB$ for some $\Pi^0_1(x)$ set $B$. By the above lemma there’s a tree $T\in L[x]$ such that $B=[T]$, so that $\mathbb R\setminus A=p[T]$, meaning that $y\in A$ iff $T_y$ is wellfounded.

Note that, using replacement, $T_y$ is wellfounded iff it can be ranked by a function $f:T_y\to\omega_1$, meaning that $s\supsetneq t$ implies that $f(s) < f(t)$ for all $s,t\in T_y$. We can pick such a ranking function with codomain $\omega_1$ since wellfoundedness of $T_y$ implies that $|T_y|=\aleph_0$.

Now define a tree $S\in L[x]$ on $\omega\times\omega_1$ as follows. Fix a bijection $e:\omega\to{^{<\omega}\omega}$ such that, for every $s\in{^{<\omega}\omega}$, $n<\text{lh}(s)$ implies that $e^{-1}(s\upharpoonright n) < e^{-1}(s)$. For $s\in{^{<\omega}\omega}$ define

$$ T_s := \{t\in{^{<\omega}\omega} \mid \text{lh}(t)\leq\text{lh}(s)\land(s\upharpoonright\text{lh}(t),t)\in T\} $$

and then define $S\subseteq{^{<\omega}\omega}\times{^{<\omega}\omega_1}$ as $(s,t)\in S$ iff $\text{lh}(s)=\text{lh}(t)$ and that

$$ \forall k,l<\text{lh}(s)[(e(k)\in T_s\land e(l)\in T_s\land e(k)\supsetneq e(l))\Rightarrow t(k) < t(l)]. $$

Note that $S\in L[x]$ since $T\in L[x]$. For $(s,t),(s’,t’)\in S$ we set $(s,t)\leq_S(s’,t’)$ iff $s\supseteq s’$ and $t\supseteq t’$. Then $y\in A$ iff $S_y$ is illfounded iff $y\in p[S]$. QED

Theorem (Shoenfield absoluteness). Let $x\in\mathbb R$. Then every $\Sigma^1_2(x)$ sentence is absolute between transitive models $M\subseteq N$ of $\textsf{ZF}+\textsf{DC}$ such that $\omega_1^N,x\in M$.

Proof. Let $\varphi(v)$ be a $\Sigma^1_2$ formula, so that $\varphi(v)\equiv\exists y\in\mathbb R\psi(v,y)$ for a $\Pi^1_1$-formula $\psi(v,w)$. If $M\models\varphi[x]$ then trivially $N\models\varphi[x]$ by upwards absoluteness of $\Pi_1$-formulas, so assume instead that $N\models\varphi[x]$. Define

$$ A:=\{y\in\mathbb R^N\mid N\models\psi[x,y]\}\in N, $$

so that $A\neq\emptyset$ by assumption. As $A$ is a $\Pi^1_1(x)$ set in $N$, the above lemma implies that we get that $A=p[T]$ for a tree $T\in L[x]^N$ on $\omega\times\omega_1^N$, so that $y\in A$ iff $T_y$ is illfounded in $N$.

Pick some $y\in A$. Then $T_y$, and in particular also $T$, is illfounded in $N$. Since $\omega_1^N,x\in M$ we get that $T\in M$ as well, so that absoluteness of wellfoundedness yields some $y’\in A\cap M\neq\emptyset$, concluding $M\models\varphi[x]$. QED

We see that the only thing we needed $\omega_1^N,x\in M$ for was to ensure that the resulting tree was in indeed in $M$, to make sure that we could use absoluteness of wellfoundedness.