MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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. – Joel David Hamkins Jan 27 '12 at 2:25
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. – Asher M. Kach Jan 27 '12 at 15:00
up vote 4 down vote accepted

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.

share|cite|improve this answer
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)$. – James Miller Jan 27 '12 at 3:16
@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$. – Andreas Blass Jan 27 '12 at 3:31
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$. – Andreas Blass Jan 27 '12 at 3:34
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$. – Joel David Hamkins Jan 27 '12 at 11:57

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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