Arithmetical Hierarchy - Classification of sets

Question

I am currently working on a problem to classify the following set:

$A = \{e \mid W_e \subset \{0,1\}\}$, where $W_e$ is the domain of some recursive function with code $e$.

I originally formulated it as the following FOL:

$e \in A \iff (\forall x)[ x \in W_e \implies x \leq 1] \iff (\forall x)(\exists y)[ T(e,x,y) \implies x \leq 1 ]$

EDIT: I have since found a better upper bound:

$e \in A \iff (\forall z)[ (z)_0 \leq 1 \lor \lnot T(e,(z)_0, (z)_1)]$

Where $T$ predicate is true when the program $e$ taking in $x$ halts with some intermediate computations $y$. Since $T$ is (primitive) recursive, this is in canonical form. I stated that the upper bound for $A$ is $\Pi_1^0$, but am having trouble proving that the lower bound is $\Pi_1^0$ as well.

Is this upper bound tight? And if so, any hints on approaches to prove the problem would be greatly appreciated.

Answer 1

First, a slight correction. The calculation $$e \in A \iff (\forall x)[ x \in W_e \implies x \leq 1] \iff (\forall x)(\exists y)[ T(e,x,y) \implies x \leq 1 ]$$ is not quite correct. The existential quantifier is in the wrong place. It should be $$e \in A \iff (\forall x)[ x \in W_e \implies x \leq 1] \iff (\forall x)[(\exists y) T(e,x,y) \implies x \leq 1 ]$$

---

Now, using the rule that $[(\exists x) \phi] \to \psi$ is equivalent to $(\forall x)[ \phi \to \psi]$ (when $\psi$ doesn't mention $x$), we get $$e \in A \iff (\forall x)[ x \in W_e \implies x \leq 1] \iff (\forall x)(\forall y)[ T(e,x,y) \implies x \leq 1 ]$$

This is a $\Pi^0_1$ statement, just like your second calculation.

To show that this bound is tight, you need to find an $m$-reduction from some other $\Pi^0_1$-hard set to your set. One typical $\Pi^0_1$ hard set is the set of $e$ so that $W_e = \emptyset$, and you can make a reduction from that set to that set in the question. In other words you want a computable $f$ so that, for all $e$, $W_e = \emptyset$ if and only if $W_{f(e)} \subseteq \{0,1\}$.

Answer 2

To build up from Carl's hints, here's my attempt at a solution:

Choose the $\Pi_1^0$ set $B = \{e \mid W_e = \emptyset\}$. We wish to show $B \leq_m A$, thus proving $A$ is $\Pi_1^0$. To do this, we need to construct $f: \mathbb{N} \to \mathbb{N}$ s.t. $e \in B \iff f(e) \in A$, where $A$ is our set defined in the problem.

Define such $g$ as: $g(e, x) = \begin{cases} 0 & x \leq 1 \\ \phi_e(x-2) &\text{else} \end{cases}$

It is obvious that the domain of $g$, fixed on $e$, on the parameter $x$ is $\{0,1\} \cup \{x+2 \mid x \in W_e\}$. We let $f$ be the function that generates the hardcoded $e$: $f(e) = S^1_1(\hat{g},e)$, so that $\phi_{f(e)}(x) = \phi_{S^1_1(\hat{g},e)}(x) = g(e,x)$

$e \in B \iff W_e = \emptyset \iff \{0,1\} \cup \{x+2 \mid x \in W_e\} = \{0,1\} \iff W_{f(e)} = \{0,1\} \iff f(e) \in A$

And so we're done.