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?



Infinite set with/without infinite c.e. subsets
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.


