The following exercises are from Recursion Theory by Chong & Yu.

  • Exercise 4.3.1: Assume $\omega_1^L=\omega_1$. Show that there is no largest countable $\Pi^1_1$ set of reals.
  • Exercise 4.4.3: Assume $\omega_1^L=\omega_1$. Show that there is no largest countable $\Sigma^1_2$ set of reals.

In case any future student is desparately googling for a solution, I’ll write down my take here.

Let’s begin with a warm-up exercise. We show that there is no largest countable $\Sigma^1_1$ set of reals: if $A$ is a countable $\Sigma^1_1$ set of reals, then by the :effective perfect set theorem, it contains only hyperarithmetic reals. But it cannot be all of them since the set of hyperarithmetic reals is properly $\Pi^1_1$. So there is always a hyperarithmetic real $x$ outside of $A$. But then $A\cup\{x\}$ is a countable $\Sigma^1_1$ set of reals that strictly contains $A$, so $A$ cannot be the largest.

So that’s roughly the idea. Find a kind of definable cover for your countable set that’s nevertheless not exhausted by it, and then something new from the cover to get a strictly larger set. The same idea works for the two exercises above, but the details are a bit more involved.

Exercise 4.3.1: Assume $\omega_1^L=\omega_1$. Show that there is no largest countable $\Pi^1_1$ set of reals.

Proof. We use as our “cover” the largest $\Pi^1_1$ thin set \(C:=\{x\in 2^\omega \mid x\in L_{\omega_1^x}\}.\) Details about this set can be found in the textbook. The point is that if $A$ is $\Pi^1_1$ and countable then it is a subset of $C$. But $C$ is uncountable, so there is some $x\in C\smallsetminus A$. So now we need to find a way to carve something out of $C$ that we will add to $A$ to get a strictly larger $\Pi^1_1$ set.

To do this we’ll use a $\Pi^1_1$ norm $\rho$ on $C$. Note that for each $y\in C$ the sets $I_y:=\{x\in C\mid \rho(x)<\rho(y)\}$ and $E_y:=\{x\in C\mid \rho(x)=\rho(y)\}$ are both $\Delta^1_1(y)$ (this is standard and can be easily seen by a definition chase). So they are Borel subsets of $C$, and hence countable.

Now for our countable $\Pi^11$ set $A$, consider $B_A := \{y\in C\mid I_y\subseteq A\}$. Let \(\gamma = \min\{\rho(y) : y \in C \setminus A\},\) and choose $y* \in C \smallsetminus A$ with $\rho(y_*) = \gamma$.

Then:

  1. Since every $x \in I_{y_}$ has $\rho(x) < \gamma$, minimality of $\gamma$ gives $x \in A$. Hence [ y_ \in B_A \setminus A. ]
  2. If $y \in B_A$ and $\rho(y) > \gamma$, then $y_* \in I_{y}$, contradicting $I_{y} \subseteq A$. Therefore every $y \in B_A$ has $\rho(y) \le \gamma$.
  3. If $y \in B_A$ and $\rho(y) < \gamma$, then the minimality of $\gamma$ gives $y \in A$.

Consequently, \(B_A \subseteq A \cup E_{y_*}.\) Both $A$ and $E_{y_*}$ are countable, so $B_A$ is countable and nevertheless contains a real outside $A$.

But $B_A$ is $\Pi^1_1$: $y\in B_A \Leftrightarrow C(y) \wedge (\forall x)(x\in I_y\rightarrow A(x))$. And so $A\cup B_A$ is a countable $\Pi^1_1$ set of reals that strictly contains $A$. Hence $A$ cannot be the largest.

The other exercise is similar. We just have to be more careful about proving the complexity of $B_A$.

Exercise 4.4.3. Assume that $\omega_1=(\omega_1)^L$. Then there is no largest countable $\Sigma^1_2$ set of reals.

Proof. Same setup as before. We get a countable set $B_A$ that contains a real not in $A$.

It remains to prove that $B_A$ is $\Sigma^1_2$. Write

\[x\in A \quad\Longleftrightarrow\quad (\exists u)\,R(x,u),\]

where $R\in\Pi^1_1$.

Let $I^\Sigma(x,y)$ denote the $\Sigma^1_1$ definition of $x\in I_y$:

\[I^\Sigma(x,y) \quad\Longleftrightarrow\quad Q(x,y)\wedge\neg P(y,x).\]

A real $e$ may be viewed as coding a sequence of reals

\[\langle e_n:n\in\omega\rangle.\]

Define $\operatorname{Cover}(e,y)$ to mean that this sequence covers $I_y$:

\[\operatorname{Cover}(e,y) \quad\Longleftrightarrow\quad (\forall x)\bigl( I^\Sigma(x,y)\rightarrow(\exists n)\,x=e_n \bigr).\]

Since $I^\Sigma$ is $\Sigma^1_1$, the relation $\operatorname{Cover}(e,y)$ is $\Pi^1_1$.

Now, because $I_y$ is countable, $I_y\subseteq A$ if and only if there exist reals $e$ and $U$, where $e$ codes a sequence $\langle e_n:n\in\omega\rangle$ and $U$ codes a sequence $\langle u_n:n\in\omega\rangle$, such that

\[\operatorname{Cover}(e,y)\]

and

\[(\forall n)\bigl( I^\Sigma(e_n,y)\rightarrow R(e_n,u_n) \bigr).\]

Indeed, if $I_y\subseteq A$, choose a sequence covering $I_y$, and for each $e_n\in I_y$ choose $u_n$ witnessing $e_n\in A$. Conversely, if such $e$ and $U$ exist and $x\in I_y$, then $x=e_n$ for some $n$, and hence $R(e_n,u_n)$, so $x\in A$.

Thus

\[\begin{aligned} y\in B_A \quad\Longleftrightarrow\quad (\exists e)(\exists U)\bigl[ &C(y)\wedge \operatorname{Cover}(e,y)\\ &\wedge (\forall n)\bigl( I^\Sigma(e_n,y)\rightarrow R(e_n,u_n) \bigr) \bigr]. \end{aligned}\]

The expression inside the brackets is $\Pi^1_1$: $C(y)$ is $\Pi^1_1$, $\operatorname{Cover}(e,y)$ is $\Pi^1_1$, and

\[(\forall n)\bigl( I^\Sigma(e_n,y)\rightarrow R(e_n,u_n) \bigr)\]

is $\Pi^1_1$ because $I^\Sigma$ is $\Sigma^1_1$ and $R$ is $\Pi^1_1$.

Therefore

\[B_A\in\Sigma^1_2.\]

Finally,

\[A^+=A\cup B_A\]

is a countable $\Sigma^12$ set, and since $y*\in B_A\setminus A$,

\[A\subsetneq A^+.\]

Thus every countable $\Sigma^1_2$ set has a proper countable $\Sigma^1_2$ extension. Hence there is no largest countable $\Sigma^1_2$ set of reals.

:x EPST

which says if a $\Sigma^1_1$ set doesn’t have a perfect subset, then there is some computable ordinal $\alpha$ such that the $\alpha$-th Turing jump computes every element of it. See e.g., Notes on Effective Descriptive Set Theory

:x NormDef

$\Pi^1_1$ sets have $\Pi^1_1$ norms with height $\omega_1$. That is, there is a surjective function \(\rho: C \longrightarrow \omega_1\)and relations\(P(x,y) \in \Pi^1_1, \quad Q(x,y) \in \Sigma^1_1\)such that, whenever $y \in C$,\(x \in C \land \rho(x) \le \rho(y) \iff P(x,y) \iff Q(x,y).\)