I want to find the position of the language $\rm{BTot}:=\left\{e \ \colon \phi_{e} \ \text{bounded and total}\right\}$ in the Arithmetical Hierarchy.
It is easy to see that totality is a $\Pi_{2}$-relation and that boundedness is a $\Sigma_{2}$-relation and thus by writing the formula in PNF form (i.e. moving the quantifiers to the front of the formula), we see that $\rm{BTot}$ is a $\Delta_{3}$-relation, i.e. it is both $\Sigma_{3}$ and $\Pi_{3}$.
I claim that it is strictly $\Delta_{3}$.
- $\rm{BTot}\not\in\Pi_{2}$. Suppose, towards a contradiction, that $\rm{BTot}\in\Pi_{2}$. Then, there exists a primitive recursive relation $S(x,y,z)$ such that : $ x\in\rm{BTot} \iff$ $\forall y\exists z \ S(x,y,z).$
Consider then for each $y$ the set $R^{x}_{y}=\{w\leq y \colon \forall v\leq w\exists z\leq y \ S(x,v,z)\}.$ By the Recursion Theorem we get the total recursive function with code $e$ defined by $$ \phi_{e}(y):=\left\{\begin{matrix} \max R^{e}_{y}, & \text{if $R^{e}_{y}\neq\emptyset$} \\ 0 & \text{if $R^{e}_{y}=\emptyset$}\end{matrix}\right. $$ Then, obviously $\phi_{e}$ is total and $\phi_{e}$ is bounded if and only if $\exists y\forall z\neg S(e,y,z)$, which is equivalent to $e\not\in\rm{BTot}$, a contradiction.
- My problem is how to show that $\rm{BTot}\not\in\Sigma_{2}$ in this way. I mean, assuming that $\rm{BTot}\in\Sigma_{2}$, i.e. $ x\in\rm{BTot} \iff$ $\exists y\forall z \ S(x,y,z), $ for some primitive recursive relation $S(x,y,z)$, how can I define the appropriate $\phi_{e}$ in order to arrive at a contradiction?
I have another proof in mind for $\rm{BTot}$ not to be in $\Sigma_{2}$ by reducing the problem $\rm{Tot}=\left\{e \ \colon \phi_{e} \ \text{total}\right\}$ into $\rm{BTot}$, but I want to do it without using $\rm{Tot}$. This proof proceeds as follows: I know that $\rm{Tot}$ is $\Pi_{2}$-complete. Now, using the smn Theorem I can find the following total recursive function $x\mapsto f(x)$ such that $$ \phi_{f(x)}(y)= \left\{\begin{matrix} 1, & \text{if $\phi_{x}(y)$ is defined} \\ \text{undefined,} & \text{otherwise}\end{matrix}\right.$$ It is straightforward to see that $x\in\rm{Tot}$ $\iff f(x) \in\rm{BTot}$ and so $f$ is a many-one reduction from $\rm{Tot}$ to $\rm{BTot}$. Therefore, if $\rm{BTot}$ is $\Sigma_{2}$ then, every $\Pi_{2}$-relation is $\Sigma_{2}$, a contradiction to the Hierarchy Theorem.
Just a note for the notation, for a natural number $e$, $\phi_{e}$ is the recursive function with Gödel number $e$.