Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?


share|cite|improve this question
As the FAQ describes, we use MathJax to format mathematical notation. Please edit your post to use this; the FAQ links to the page 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. – Isaac 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? – Isaac Solomon Feb 19 '13 at 1:04

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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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