# The power set of a $\Pi_1^0$ set is a $\Pi_1^0$ class.

I'm working through the syllabus of our Computability Theory course in preparation of the exam, and came across the following exercise for which I want to check whether my construction is correct or not.

The statement is the following: if $$A$$ is a $$\Pi_1^0$$-set, then $$P(A)$$ is a $$\Pi_1^0$$-class.

Small elaboration; $$\Pi_1^0$$-sets are sets of the form $$A=\{x\mid \forall yR(x,y)\}$$ for some computable relation $$R$$. $$\Pi_1^0$$ classes are of the form $$\mathcal{A}=[T]=\{X\in 2^\omega\mid \forall n(X\restriction n \in T)\}$$, for some computable $$T\subseteq 2^{<\omega}$$. So it consists of all infinite paths in a computable tree.

So, given such a set $$A$$ we want to construct some computable tree $$T$$. If $$A$$ were computable; we would define the tree by starting at node $$0$$. If $$0$$ were in $$A$$, we would start two seperate trees; one with a $$0$$ in the first bit, and one with a $$1$$ in the first bit. If $$0$$ weren't in $$A$$, we only start a tree with the $$0$$ in the first bit. Then we proceed to the second bit, and do the same construction; we extend both our existing trees by two branches if $$1$$ is in $$A$$, and by only one branch if $$1$$ is not in $$A$$. This construction clearly gives us a computable tree for which the paths are models for all subsets of $$A$$.

Unfortunately, the set $$A$$ we are considering is not computable and hence we have to do an alternative construction of our tree. My idea now is the following; we start at the bottom, and check whether $$R(0,0)$$ holds. If it holds; we start two trees, if it doesn't, we only start one with $$0$$ in the first bit. Then, we move to the second bit. First, we check whether $$R(0,1)$$ holds. If it holds, we do nothing extra and proceed to check whether $$R(1,0)$$ and $$R(1,1)$$ hold (and then add two branches if both hold, and only one if it doesnt). If checken $$R(0,1)$$ would have shown that it doesn't hold, then we destroy the entire tree that starts with a $$1$$ in the first bit. We then continue inductively, and at step $$n$$ we check $$R(m,n)$$ for every $$m\leq n$$ and destroy branches 'in hindsight' if this doesn't work.

Sorry, this might be totally unreadable, but I could not really find another way to describe the approach. Do you think this construction gives a correct answer to the exercise, or is there something I am missing in my approach?

Thanks!

Suppose $$A$$ is $$\Pi^0_1$$, and fix some computable $$R\subseteq\omega^2$$ such that $$A=\{x:\forall y(R(x,y))\}$$. Say that a finite binary string $$\sigma$$ is a plausible subset of $$A$$ iff for each $$x<\vert\sigma\vert$$ such that $$\sigma(x)=1$$ the relation $$R(x,y)$$ holds for all $$y<\vert\sigma\vert$$. The set $$T$$ of plausible subsets is a computable tree - the point being that the "$$<\vert\sigma\vert$$" clauses make all the relevant searches finite.
Now suppose $$f$$ is an infinite path through $$T$$ and $$f(x)=1$$. Then for each $$n$$ we have $$f\upharpoonright (n+1)$$ is a plausible subset of $$A$$, and so $$R(x,n)$$ holds. This means in fact that we have $$\forall y(R(x,y))$$, and so we get $$\{x: f(x)=1\}\subseteq A$$ as desired.