Recursion questions

Question

Let $M$ be a set, $e\in M$, and $F:M\rightarrow M$. Define $r$ on $\mathbb{N}$ by $r(0)=e$, and, for all $k$, $k\in \mathbb{N}$, $r(s(k))=F(r(k))$.

Assume that $F$ maps $M$ $1\text{-}1$ and onto $M$. Define a function $F$ for which $r$ does not map onto $M$. Also, define a function $F$ for which $r$ is not $1\text{-}1$ on $\mathbb{N}$.

Answer 1

HINT: You didn’t say, but I’m assuming that $Nat$ is $\Bbb N$, the set of natural numbers (including $0$), and that $s$ is the successor function. If $M=\{e\}$, $r$ will always map $\Bbb N$ onto $M$, so we must assume that $M$ contains at least one other element.

• If $F:M\to M$ is the identity function, what does $r$ turn out to be?