Let [itex]\varphi_e[/itex] denote the p.c. function computed by the Turing Machine with code number [itex]e[/itex]. Given [itex]M=\{x : \neg(y<x)[\varphi_y=\varphi_x]\}[/itex] prove that [itex]M[/itex] is infinite and contains no infinite c.e. subset.(adsbygoogle = window.adsbygoogle || []).push({});

I have already proved that [itex]M[/itex] is infinite. A necessary and sufficient condition to prove that [itex]M[/itex] has no c.e. subset is that given any one-to-one computable function [itex]f[/itex] it follows that [itex]f(\omega) \nsubseteq M[/itex]. One way to demonstrate that this holds is to use the Recursion Theorem to show that there is some index [itex]x_0[/itex] such that [itex]\varphi_{x_0}=\varphi_{f(x_0)}[/itex] but [itex]x_0 < f(x_0)[/itex]. I am having trouble doing this however and was wondering is someone here could help.

I think that this is the right way to approach the problem since the text suggested we use the Recursion Theorem to tackle it.

**Physics Forums | Science Articles, Homework Help, Discussion**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Recursion Theorem and c.e. sets

Can you offer guidance or do you also need help?

Draft saved
Draft deleted

**Physics Forums | Science Articles, Homework Help, Discussion**