3
$\begingroup$

Let $\varphi_e$ denote the p.c. function computed by the Turing Machine with code number $e$. I am looking at the set $M = \lbrace x : \neg (x < y)[\varphi_x=\varphi_y] \rbrace$. This set is clearly infinite. Now $M$ has an infinite c.e. subset if and only if there exists a one-to-one computable function $f$ such that $f(\omega) \subseteq M$. But it seems like the Recursion Theorem should furnish a fixed point $x_0$ such that $\varphi_{x_0}=\varphi_{f(x_0)}$ and $x_0 < f(x_0)$. This would mean that $M$ has no infinite c.e. subset, but I cannot seem to prove this. Can anyone help me resolve this question in either direction?

$\endgroup$
2
  • $\begingroup$ Do you mean that $M$ is the set of $y$ with the property that there is no smaller $x$ with $\varphi_x=\varphi_y$? This is not quite what you wrote, since you've mixed up $x$ and $y$ and also you're missing a quantifier. $\endgroup$ Jan 27, 2012 at 2:25
  • 1
    $\begingroup$ It might be worth noting that the set $M := \{ y : \neg (\exists x < y) \left[ \varphi_x = \varphi_y \right] \}$ has been studied in the literature. For example, in A Guided Tour of Minimal Indices and Shortest Descriptions (Archive for Mathematical Logic, Volume 37, Number 8, Pages 521-548), Marcus Schaefer shows not only that this set is immune (as you show), but also strongly effectively immune, $\omega$-immune, not hyperimmune, wtt above $0'$, not btt above $0'$, and so on. $\endgroup$ Jan 27, 2012 at 15:00

1 Answer 1

5
$\begingroup$

I assume that you mean $M=\{ y\mid \neg\exists x\lt y\ \varphi_x=\varphi_y\}$. And in this case, the argument you've already given seems to solve the problem. If $M$ had an infinite c.e. subset $A$, then let $f(n)$ be the first element enumerated into $A$ above $n$. So $n\lt f(n)\in A\subset M$ for every $n$. By the Kleene recursion theorem, as you mentioned, there is $x_0$ with $\varphi_{x_0}=\varphi_{f(x_0)}$, but as $f(x_0)\in A\subset M$ and $x_0\lt f(x_0)$, this contradicts the definition of $M$. Thus, $M$ can have no infinite c.e. subset.

$\endgroup$
4
  • $\begingroup$ That is the collection I am looking at; I am sorry about the poor notation. My question is how can we guarantee that if there is an infinite c.e. set A, then there exists a computable function $f$ such that $n < f(n)$? The existence of a one-to-one computable function enumerating $A$ is clear, but I am unsure how to get the condition $n < f(n)$. $\endgroup$ Jan 27, 2012 at 3:16
  • 1
    $\begingroup$ @James: Look more closely at Joel's explicit definition of $f$. The very definition ensures that $n<f(n)$ for all $n$. Your comment sounds as if you expect $f$ to be a one-to-one enumeration of $A$, but that expectation is not supported by Joel's definition. Unless the hypothetical $A$ were quite special, Joel's $f$ would not be one-to-one and would not enumerate all of $A$. $\endgroup$ Jan 27, 2012 at 3:31
  • $\begingroup$ Another way to arrange the same argument is to first invoke the theorem that every infinite c.e. set has an infinite computable subset. Then taking $A$ to be computable and (w.l.o.g.) not containing 0, we can use the function that enumerates $A$ in increasing order to satisfy all of James's wishes: computable, one-to-one enumeration of $A$ with $n<f(n)$ for all $n$. $\endgroup$ Jan 27, 2012 at 3:34
  • $\begingroup$ James, it was not important that $f$ is one-to-one in your argument, but only that $n\lt f(n)$ and $f(n)\in M$. $\endgroup$ Jan 27, 2012 at 11:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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