I came across this problem and I was not able to solve it:
Show that every infinite recursive set is the range of a nondecreasing unbounded recursive function of one variable.
Also, what would be the case if the function is bounded?
Thanks :)
Asked
Active
Viewed 147 times
0
Salma
- 97
-
What can you say about a nondecreasing bounded (integer) function of one variable? – Steven Stadnicki May 18 '16 at 20:57
-
@StevenStadnicki it's a recursive function ? – Salma May 18 '16 at 22:01
-
Salma: if it's bounded there's some $N$ such that it can never be greater than $N$. What can you say about the set of (natural numbers) $\leq N$? – Steven Stadnicki May 18 '16 at 22:37
-
@StevenStadnicki it is infinite ? So $N$ is infinite ? – Salma May 19 '16 at 02:44