Let $W_e$ be the c.e. set which is the domain of the p.c. function $\varphi_e$ and consider the equivalence $\sim$ such that $x \sim y$ if and only if $\varphi_x=\varphi_y$. I am wondering if $W_e$ infinite implies $W_e/\sim$ infinite.
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.
No. Fix any $k \in \mathbb{N}$. We can computably enumerate infinitely many $n$'s such that $\phi_k = \phi_n$. For example, given any $j$, let $n$ be the code of the program which is just like the program coded by $k$, except that it contains extra $j$ useless states. Let $W_e$ be the infinite c.e. set whose members are the $n$'s so enumerated. Then $W_e/{\sim}$ has just one element. 

