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?
1 Answer
$\begingroup$
$\endgroup$
4
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.
answered Jan 27, 2012 at 2:41
-
$\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$ Commented 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$ Commented 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$ Commented 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$ Commented Jan 27, 2012 at 11:57
$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$