Shoenfield Absoluteness

Assume first $A$ is $\Pi^1_1$. There is a recursive tree $T$ on $\Nat \times \Nat$ (and hence, in $L$, since “being recursive” is definable) such that

Hence, $\alpha \in A$ if and only if there exists an order preserving map (with respect to the inverse prefix ordering) $\pi: T(\alpha) \to \omega_1$. We recast this now in terms of getting an infinite branch through a tree.

Let $\{\sigma_i \colon i \in \Nat\}$ be a recursive enumeration of $\Nstr$. We may assume for this enumeration that $|\sigma_i| \leq i$. We define a tree $\widetilde{T}$ on $\Nat \times \omega_1$ by

The tree $\widetilde{T}$ is in $L$, since it is definable from $T$ and $\omega_1$. Furthermore, if $\alpha \in A$, then the existence of an order-preserving map $\pi: T(\alpha) \to \omega_1$ implies that there is an infinite path $(\alpha,\eta)$ through $\widetilde{T}$.

Conversely, if such a path $(\alpha,\eta)$ exists, then there is an order preserving map $\pi: T(\alpha) \to \omega_1$. Hence we have

so $A$ is of the desired form.

Next, we extend the representation to $\Sigma^1_2$.

If $A$ is $\Sigma^1_2$, then there is a $\Pi^1_1$ set $B \subseteq \Baire\times\Baire$ such that $A = \exists^{\Baire} B$. Since $B \in \Pi^1_1$, we can employ the tree representation of $\Pi^1_1$ to obtain a tree $T$ over $\Nat \times \Nat \times \omega_1$ such that $B = \exists^{(\omega_1)^\Nat} [T]$.

Now we recast $T$ as a tree $T'$ over $\Nat \times \omega_1$ such that $\exists^{(\omega_1)^\Nat}[T'] = \exists^{(\omega_1)^\Nat} B$. This is done by using a bijection between $\Nat \times \omega_1$ and $\omega_1$.

This way we can cast the $\Nat \times \omega_1$ component of $T$ into a single $\omega_1$ component, and thus transform the tree $T$ into a tree $T'$ over $\Nat \times \omega_1$ such that $\exists^{(\omega_1)^\Nat}[T'] = \exists^{(\omega_1)^\Nat}[B]$.

Let $A \subseteq \Baire$ be $\Sigma^1_2$. By Theorem 1 there exists a tree $T$ on $\Nat \times \omega_1$ such that $A = \exists^{(\omega_1)^\Nat}[T]$. For any $\xi < \omega_1$ let

Since the cofinality of $\omega_1$ is greater than $\omega$ (this can be proved without using $\AC$), every $d: \omega \to \omega_1$ has its range included in some $\xi < \omega_1$. Thus we have

For all $\xi < \omega_1$, the set $\exists^{(\omega_1)^\Nat}[T^\xi]$ is $\PS{1}$, because the tree $T^\xi$ is a tree on a product of countable sets and hence is isomorphic to a tree on $\Nat \times \Nat$. By Corollary 2, each $\PS{1}$ set is the union of $\aleph_1$ many Borel sets, from which the result follows.

We show the theorem for $\Sigma^1_2$ predicates. For the relativized version, one uses the relative constructible universe $L[\gamma]$, see Jech (2003) or Kanamori (2003).

Let $A$ be a $\Sigma^1_2$ relation. For simplicity, we assume that $A$ is unary. Fix a tree representation of $A$ as a projection of a $\Pi^1_1$ set. So, let $T$ be a recursive tree on $\Nat \times \Nat \times \Nat$ such that

Note that $T$ is in $M$ (since it is recursive and hence definable).

Now assume $\alpha \in M$ and $A^M(\alpha)$. Hence there is a $\beta \in M$ such that $T(\alpha,\beta)$ is well-founded in $M$. This is equivalent to the fact that in $M$ there exists an order preserving mapping $\pi: T(\alpha,\beta) \to \mathbf{Ord}$.

Since $M$ is an inner model and $T$ is absolute, the mapping exists also in $V$. Hence $T(\alpha,\beta)$ is well-founded in $V$ and thus $A(\alpha)$.

For the converse assume that $\alpha \in M$ and $A(\alpha)$. Now we use the alternative tree representation of $A$ given by Theorem 1. Let $U \in L \subseteq M$ be a tree on $\Nat \times \omega_1$ such that $A = \exists^{(\omega_1)^\Nat} U$.

As before, let

Then, for any $\alpha \in \Baire$,

This means that there exists no order preserving map $U(\alpha) \to \omega_1$. But then such a map cannot exist in $M$ either. Thus, $U(\alpha)$ is a tree in $M$ which is ill-founded in the sense of $M$. Thus, by Shoenfield’s Representation Theorem relativized to $M$, $A^M(\alpha)$.

Absoluteness for $\Pi^1_2$ follows by employing the same reasoning, using that the complement is $\Sigma^1_2$.