1
$\begingroup$

I've been given the set $INF=\{e\in\mathbb{N}:dom(\varphi_e)$ is infinite$\}$, where $\varphi_e$ denotes the $e$-th computable function.

I'm trying to prove that it is not recursively enumerable. I tried to follow the same strategy as with the complementary set, $FIN$, for which I assumed it was r.e. and then defined the function

$$ f(e,x)=\begin{cases} x & e\in FIN\\ \uparrow & otherwise \end{cases} $$

Which is computable because its graph is r.e. by assumption, carrying me to a contradiction by examining the possible cases. But in this case, if I define

$$ g(e,x)=\begin{cases} x & e\in INF\\ \uparrow & otherwise \end{cases} $$

Then there is no contradiction with the fact of $g$ being computable. What strategy should I follow then?

$\endgroup$
  • 2
    $\begingroup$ Try a regular diagonalization. Assume that the set INF is r.e. via an index $e$. Make a program $j$ that has an infinite domain if and only if $e$ does not enumerate $j$. Here $j$ can depend on $e$. $\endgroup$ – Carl Mummert Jan 7 '18 at 0:34
3
$\begingroup$

This can be done with a "regular" (i.e. usual) diagonalization, using what I would call a "watch and wait" method.

Choose any $e$ and look at $W_e$. Make a program $j$ that simulates the enumeration of $W_e$, and so that $\phi_j(n)$ halts if and only if $j$ does not enter $W_e$ within the first $n$ steps of the simulation. This uses the recursion theorem to allow $j$ to know its own index.

Then we can show that $j \in W_e$ if and only if the domain of $\phi_j$ is finite. So $W_e$ does not enumerate INF. Now $e$ was arbitrary, so INF is not r.e.

There is a more principled way to solve this problem. We should always begin this type of problem with a Tarski-Kuratowski computation to guess the complexity of the set within the arithmetical hierarchy. One definition of INF is: $$ \text{INF} = \{e : (\forall n)(\exists m)(\exists t)[ n > m \land \phi_{e,t}(n)\downarrow]\} $$ So we would guess that INF is a $\Pi^0_2$ set. Thus, a better way to show INF is not r.e. (that is, not $\Sigma^0_1$) would be to show that INF is $\Pi^0_2$ complete. It is not hard to do this - to show that every $\Pi^0_2$ set is many-one reducible to INF. Then we know that INF cannot be r.e. because of Post's theorem, but we actually have a sharp computation of the location of INF in the arithmetical hierarchy.

Similarly, FIN can be defined as $$ \text{FIN} = \{ e : (\exists m)(\forall n)(\forall t)[n > m \to \phi_{e,t}(n)\uparrow]\}.$$ So we would guess that FIN is $\Sigma^0_2$, and try to prove that every $\Sigma^0_2$ set is many-one reducible to FIN. This gives more information than just "FIN is not r.e." but it also gives a suggestion for where to start the proof.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you! I read your comment, but I didn't have time to try it. The first method is fine for me, because I haven't been taught yet about Tarski-Kuratowski computation nor Post's theorem. $\endgroup$ – Javi Jan 7 '18 at 20:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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