Recursive representation of closed sets in Baire Space ($\Sigma^1_1$)

Question

These notes (pg 2) say that

A set $C \subseteq \omega^\omega$ is closed if and only if there is an $z \in \omega^\omega$ and a recursive predicate $R \subseteq \omega^{<\omega}\times\omega^{<\omega}$, such that for all $x$,

$$x \in A \iff \forall n R(x_{|n}, z_{|n})$$

I am garbage at recursion theory; can someone elucidate on how we obtain this result?

Bonus:

We know that an analytic set $A \subset \omega^\omega$ is a projection of a closed set $C \subset \omega^\omega\times\omega^\omega$.

An alternate formulation would be that a set $A \subseteq \omega^\omega$ is analytic if there is $z \in \omega^\omega$ and a recursive $R \subseteq \omega^{<\omega} \times \omega^{<\omega} \times \omega^{<\omega}$, such that $$x \in A \iff \exists y \in \omega^\omega \forall n\in \omega R(x_{|n}, y_{|n}, z_{|n})$$

Proving the result above would easily give us the equivalence between these two formulations.

Answer 1

The idea is that we can replace "arbitrary relation" with "recursive relation equipped with appropriate oracle." Specifically:

There is a recursive $R\subseteq\omega^{<\omega}\times\omega^{<\omega}$ such that for any $S\subseteq\omega^{<\omega}$ there is some $z\in\omega^\omega$ such that $$\{x: \forall n\in\omega(x_{\vert n}\in S)\}=\{x: \forall n\in\omega(\langle x_{\vert n}, z_{\vert n}\rangle\in R)\}.$$

It may be easier to prove this first without the recursivity condition - the $R$ you produce in the proof of the weaker result will actually have a good chance of already being recursive!

HINT: think about a way to "code" subsets of $\omega^{<\omega}$ by reals.

Let $f:\omega\rightarrow\omega^{<\omega}$ be some reasonable bijection. For $S\subseteq \omega^{<\omega}$ let $z_S$ be the characteristic function of $S$ composed with $f$. The real $z_S$ "codes" $S$ in an obvious way. Now, we have $\forall n\in\omega(x_{\vert n}\in S)$ iff there is no initial segment of $z_S$ which indicates that some initial segment of $x$ "falls off" of $S$; do you see how to make that precise, and turn it into an appropriate $R$? As long as the bijection $f$ is reasonable this $R$ will be recursive.

---

With this in hand we can in fact prove a stronger result:

There is a single recursive $R\subseteq\omega^{<\omega}\times\omega^{<\omega}$ such that for every $C\subseteq\omega^\omega$, $C$ is closed iff there is some $z\in\omega^\omega$ with $$A=\{x:\forall n(\langle x_{\vert n},z_{\vert n}\rangle\in R)\}.$$