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?



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.

  • $\begingroup$ Thank you! This is indeed a snappier way of describing my approach, and precisely what I was looking for. $\endgroup$ – EBP Dec 30 '20 at 15:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.