Non-decidable $\Pi^0_1$ (effectively closed) classes

139 Views Asked by At

Are there non-decidable $\Pi^0_1$ (effectively closed) classes? According to a draft of Effectively closed sets by Cenzer and Remmel, the class $$ P = \{ 0^n1^\omega \mid n \in B\} $$ is a non-decidable $\Pi^0_1$ class, where $B \subset \omega$ is a non-computable co-c.e. set.

According to the book, $P \subseteq \omega^{\omega}$ is a $\Pi^0_1$ class if there exists a computable tree $T \subseteq \omega^{<\omega}$ that is passed through exactly by the paths in $P$, i.e., $[T] = P$, and it is decidable, if $T_P$ is computable, where $T_P = \{\sigma \in \omega^{<\omega} \mid P \cap I(\sigma) \neq 0\}$ and $I(\sigma) = \{ x \in \omega^\omega \mid \sigma \prec x\}$.

However, I "proved" that, in general, $T_P$ is the set $\{x \upharpoonright n \mid x \in P, n \in \omega\}$; $[T_P] = P$ for closed $P$; and that if $[T] = P$, $T_P = T$, which deny the existence of non-decidable $\Pi^0_1$ classes.

Is it possible for you to point out counterexamples to the three claims I "proved"?

1

There are 1 best solutions below

3
On BEST ANSWER

You said, "If $[T] = P$ then $T_P = T$". Consider $T = \{ \langle\rangle, \langle 0 \rangle \} \cup \{ \langle 1^n \rangle : n \in \omega\}$. Then $T$ is a computable tree, $P = [T]$ is a one-point set and thus closed, and $T_P \not = T$. That is a counterexample of the kind you asked for. These counterexamples all come from trees with dead ends.

In general, the set that is called $T_P$ is the set of "extendible nodes" of $T$. Let's call it $E(T)$ for now: $$ E(T) = \{ \sigma \in T : (\exists x \in [T])[ \sigma \prec x] \} $$

An easy fact is that if $[T] \not = \emptyset$ and $E(T)$ is computable then $[T]$ has a computable member. The construction of the member is simple: under these assumptions $\langle \rangle \in E(T)$, and for all $\sigma \in E(T)$ at least one of the children of $\sigma$ is in $E(T)$, so we can build a computable sequence $\sigma_i$ where $\sigma_0 = \langle\rangle$ and $\sigma_{i+1}$ is the leftmost child of $\sigma_i$ that is in $E(T)$. Then $x = \bigcup \sigma_i$ is in $[T]$. So another way to find non-decidable $\Pi^0_1$ classes is to take classes with no computable members, e.g. the $\Pi^0_1$ class of all completions of Peano arithmetic.

We can verify that the example from Cenzer and Remmel is correct. Actually, the way they wrote the $\Pi^0_1$ class is a little odd. The point $0^\omega$ must also be in this class, because $B$ is infinite and the class is closed. So the class is really $\{0^\omega\} \cup \{0^n1^\omega : n \in B\} = \operatorname{cl}\{0^n1^\omega : n \in B\}$. Let's call this class $C$.

Given $n$, the only real extending $0^n1$ that could be in $C$ is $0^n1^\omega$. So for each $n$ we have that $0^n1$ is an extendible node if and only if $n$ is in our non-decidable set $B$, which means that if the set of extendible nodes is computable then so is $B$. The assumption that $B$ is $\Pi^0_1$ is just so that the class $C$ is $\Pi^0_1$

For this particular $\Pi^0_1$ class $C$ from the previous paragraph, the tree $$T_C = \{ x \upharpoonright n : x \in C, n \in \omega\}$$ is not computable. Nevertheless, this class is of the form $[T]$ for some computable $T$, which is defined as follows. $\sigma \in T$ if $\sigma = 0^n$ for some $n$, or if $\sigma = 0^n1^m$ and $n$ has not been enumerated out of $B$ within $m$ time-steps under some fixed r.e. enumeration of the complement of $B$. This is a computable definition, and we can verify that it gives a tree $T$ with $[T] = C$.