Return to Revisions

Re question 3: Not every arithmetic real is h.c.e.. In fact, every h.c.e. real is $\Sigma_2^\mathbb{N}$. For fix a program $e$ such that $x_e\subseteq\omega$. Let $n\in\omega$. Then $n\in x_e$ iff there is some $f$ enumerated by $e$ such that $n=x_f$. But we can express "$n=x_f$" here in a $(\Sigma_1\wedge\Pi_1)^{\mathbb{N}}$ manner (this uses the assumption that $x_e\subseteq\omega$). For given $n\in\omega$ and a program $f$, we have $n=x_f$ iff there is a tuple $(f_0,f_1,\ldots,f_{n-1})$ of programs such that $f$ enumerates $f_{n-1}$, $f_{n-1}$ enumerates $f_{n-2}$, $\ldots$, $f_1$ enumerates $f_0$, and there is no tuple $(g_0,g_1,\ldots,g_n)$ such that $f$ enumerates $g_n$, $g_n$ enumerates $g_{n-1}$, $\ldots$, $g_1$ enumerates $g_0$.