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 onetoone 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?
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.
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. 


$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 521548), 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. – Asher M. Kach Jan 27 '12 at 15:00