[Math] Prove every infinite recursively enumerable subset of $\Bbb N$ contains an infinite recursive subset

computabilitycomputer sciencelogicrecursion

Given that:

An infinite subset of $\Bbb N$ is recursive if and only if it is the range of a strictly increasing recursive function.

Now I wonder if It can be proved that:

Every infinite recursively enumerable subset of $\Bbb N$ contains an infinite recursive subset.

From the definition of recursively enumerable set, it is the range of a recursive function $f$. Although in the definition, the $f$ is not necessarily strictly increasing, I wonder if I can use this function to define a new one which is strictly increasing recursive function and whose image is a subset of $im(f)$. And hence reach the conclusion.

So may I please ask if it can be done? How to do that exactly? Thanks in advance!

Note: It is from a math course. And I have not learnt about the related things about computer science (for instance, I have not learnt about the Turing machine). So sorry I cannot understand explanations which involves the usage of terms in computer science. May I please ask for a mathematical approch please?
Thanks!

EDIT: The definition of recursive function is given by:

enter image description here

enter image description here

Best Answer

Actually, it looks like your definition of partial recursive function is indeed incorrect: it is missing the primitive recursion clause. Without this clause, we get a strictly smaller class of functions. In fact, it's not hard to show that the function $f(n)=n^n$ grows faster than every function you can express using your system.

So how do we solve the problem with the correct definition? Suppose I have an r.e. set $X$. Since $X$ is r.e., we have $X=ran(f)$ for some recursive function $f$. Intuitively, I can find an infinite recursive subset $S\subseteq X$ as follows: each time I see $f$ enumerate some element of $X$ bigger than every element previously, I put it in $S$. The "bigger than every element previously" means that this set is in fact intuitively recursive: if I want to know whether $n\in S$, I wait until this process either puts $n$ into $S$ (in which case $n\in S$) or puts something bigger than $n$ into $S$ (in which case $n\not\in S$ since we can never "come back" to it).

Now we have to implement this strategy. We first define an auxiliary function $i$ which counts when $f$ "goes up":

  • $i(0)=0$,

  • $i(n+1)$ is the least $x$ such that $f(x)>f(i(n))$. (We could add the requirement that $x>i(n)$ but by induction we can show that this won't be necessary).

If we can show that $i$ is recursive, then we'll let $g(x)=f(i(x))$; it's clear that $g$ is increasing, and $ran(g)\subseteq X$, so we'll be done.

So how do we show that $i$ is recursive? This is where the primitive recursion scheme comes in handy. We have $i(n+1)=x$ iff $x$ is the least number such that $f(x)>i(n)$, that is, the least $x$ such that $i(n)+1-f(x)=0$ (I use "$-$" to denote natural subtraction here). So $i$ can be defined by primitive recursion as:

  • $i(0)=0$,

  • $i(n+1)=h(i(n))$, where $h(a)=\mu x (a+1-f(x)=0)$.

And now we're done.

Related Question