2

I'm curious by Arithmetic Hierarchy. I'm trying to do the following ones:

1) How to show that $\{e\mid \mathrm{dom}(\phi_e)\text{ is recursive}\}$ is $\Sigma_3^0$?

For showing this, I need to really relate it to the characteristic function.

2) $F=\{e\mid \mathrm{dom}(\phi_e)\text{ is finite}\}$ is $\Sigma_2^0$?

Is finite a synonym for recursive?

Thanks

Buddy Holly
  • 1,189
  • 1
    As the FAQ describes, we use MathJax to format mathematical notation. Please edit your post to use this; the FAQ links to the page http://www.onemathematicalcat.org/MathJaxDocumentation/TeXSyntax.htm that has some examples and documentation. This question also lacks a description of where you encountered the question and what you have tried already. – Carl Mummert Feb 18 '13 at 12:42
  • To apply the general plan of attack in arithmetical hierarchy classifications, you should try to (1) Show that your set is in $\Sigma_{3}^{0}$. (2) Show that it is $\Sigma_{3}^{0}$-complete by reducing any $\Sigma_{3}^{0}$-set reduces to it. – Elchanan Solomon Feb 18 '13 at 19:44
  • I don't see how to modify the below for #2. Can you please include #1? I dont seem to get the idea – Buddy Holly Feb 18 '13 at 20:07
  • Can you include #1? I'm not interested in solving these problems myself. I'm trying to better understand these example – Buddy Holly Feb 18 '13 at 20:08
  • How much recursion theory do you know, Buddy Holly? – Elchanan Solomon Feb 19 '13 at 01:04
  • Not too much. Can you please help out and include a solution for #1? Thanks – Buddy Holly Feb 19 '13 at 02:17
  • To be honest, I'm a little confused. If you don't know much recursion theory, what would the purpose be of writing out a solution? It'll be at least as complicated as the answer below, which requires some familiarity with the ideas of recursion theory. – Elchanan Solomon Feb 19 '13 at 03:48
  • I'm still reading up on it. Can you please post an answer for #1? – Buddy Holly Feb 19 '13 at 08:07

1 Answers1

3

Since it seems that you are interested in solving these problems yourself, I'll do a modified version of (2). You can adjust the proof to figure out (2), and that might give you some idea of how to attack (1). Let me just first clarify the notation I am using. $W_{e}$ is the domain of $\phi_{e}$. $T$ is the Kleene T-predicate. $S_{m}^{n}$ is Kleen's $S-m-n$ function, $\mu$ is the minimization operator, and $\# g$ is the code for a function $g$.

Classify in the arithmetical hierarchy the set $A = \{e|W_{e} \mbox{ is finite and nonempty}\}$.

Solution: This set $A$ is given by the $\Sigma_{2}^{0}$ relation

$$ (\exists w \exists c \forall w' \forall c' \forall (n > 0))[T(e,w,c) \wedge (w + n= w' \to \neg T(e,w',c'))] $$

I.e. there exists an input $w$, and a code for computation on $w$, written here as $c$, such that for any other input $w'$ and any other code for the potential convergence of that input, not only does $e$ convergene on $w$ (as witnessed by $c$), but if $w'$ is larger than $w$ (so that there is some $n > 0$where $w+n = w'$), then any $c'$ does not witness convergence on $w'$.

Now, we prove that $A$ is $\Sigma_{2}^{0}$-complete. To see this, let $B$ be the $\Sigma_{2}^{0}$ set $\exists u \forall v Q(u,v,x)$, with $Q$ recursive. Define

$$ g(x,t) = \left\{ \begin{array}{cc} 0 & t = 0\\ \sum_{u \leq t} \mu_v \neg Q(u,v,x) & \mbox{otherwise} \end{array} \right. $$

If $x \in B$, then for some $u$ and onward, this summation stops converging, as for that $u$ there is no $v$ such that $\neg Q(u,v,x)$ and so there is certainly no least such $v$! However, by construction, $g(x,t)$ always converges for $t= 0$, so the domain of $g$ is non-empty and finite. If $x \notin B$, then for every $u$, there is some $v$ such that $\neg Q(u,v,x)$, and so $g$ is total. Thus, the function

$$f :x \to S_{1}^{1}(\# g,x)$$

reduces $B$ to $A$.

Elchanan Solomon
  • 30,807