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!
Your argument is a bit unclear to me, but it sounds like it's got the right idea. The following I think is a snappier way of describing what you're doing:
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.