Proof of the recursion theorem

Question

The present statement of the theorem is as follows:

Let $A$ be a set with an element $a \in A$, and let $\psi\colon A \to A$ be a map. There exists a unique map $f\colon \mathbb{N} \to A$ with $f(1) = a$ such that

$$ f(n+1) = \psi(f(n)) $$

for all $n \in \mathbb{N}$.

My definition of the natural numbers takes $1$ to be the initial element.

The proof in my textbook considers the set $\Gamma$ of all subsets $U \subseteq \mathbb{N} \times A$ that satisfy

1. $(1, a) \in U$,
2. $(n, b) \in U \Rightarrow (n+1, \psi(b)) \in U$.

Letting $F := \bigcap_{U \in \Gamma} U$, we show that $F$ is the graph of a function. It is easy to show by induction that for all $n \in \mathbb{N}$ there exists at least one $b \in A$ such that $(n, b) \in F$. However, proving that this $b$ is unique is left to the reader, and I haven't been successful in finding a proof for it.

Answer 1

It is easy to prove it by induction:

1. Suppose that $(1,a')\in F$ for some $a'\neq a$. Let $F'=F\setminus\{(1,a)\}$. Then $F'\in\Gamma$ and therefore $F'\supset F$. This is impossible, since $F'$ was obtained from $F$ removing one of its elements.
2. Let $n\in\mathbb N$ and suppose that there is only one $b\in A$ such that $(n,b)\in F$. This implies that $\bigl(n+1,\psi(b)\bigr)\in F$. Suppose that $F$ contains some element $(n+1,b')$ for some $b'\neq\psi(b)$. Then, as before, define $F'=F\setminus\bigl\{(n+1,b')\bigr\}$. Again, $F'\in\Gamma$ and therefore $F'\supset F$, which is impossible, since $F'$ was obtained from $F$ removing one of its elements.

Answer 2

I think I have figured out the details of the proof myself.

Let $n^+$ denote the successor of $n \in \mathbb{N}$.

Lemma 1

For all $n \in \mathbb{N}$ there exists at least one $b \in A$ such that $(n, b) \in F$.

-

Lemma 2

For all $n \in \mathbb{N}$ there exists a $U \in \Gamma$ such that, if $(n, b_1) \in U$ and $(n, b_2) \in U$, then $b_1 = b_2$.

Proof: By induction in $n$.

Let $n = 1$. Take any $U \in \Gamma$ and consider the set $E := \{(1, c) \in U \mid c \neq a\}$. We claim that $U \setminus E \in \Gamma$. We thus need to show that $U \setminus E$ satisfies conditions (1) and (2). (1) is clearly satisfied, since $(1, a) \in U$, but $(1, a) \not\in E$. As for (2), for any $k \in \mathbb{N}$, if $(k, b) \in U \setminus E \subseteq U$ then $(k^+, \psi(b)) \in U$. But $k^+ > 1$, so $(k^+, \psi(b)) \not\in E$, and so $(k^+, \psi(b)) \in U \setminus E$. That is, $U \setminus E$ satisfies (1) and (2), and thus $U \setminus E \in \Gamma$. Furthermore, it is clear that if $(1, b_1) \in U \setminus E$ and $(1, b_2) \in U \setminus E$, then $b_1 = a = b_2$.

Now assume that the theorem is true for $n$, and we need to show that it holds for $n^+$. By induction, there exists a set $U \in \Gamma$ such that, if $(n, b_1) \in U$ and $(n, b_2) \in U$, then $b_1 = b_2$. Let $b := b_1$, and let $E := \{(n^+, c) \in U \mid c \neq \psi(b) \}$. We claim that set $U \setminus E$ lies in $\Gamma$, and that it satisfies the above extra condition on $n^+$. We first show that it satisfies (1) and (2). It clearly satisfies (1), since $U \in \Gamma$, and no element on the form $(1, c)$ lies in $E$. Now (2): If $(k, b) \in U \setminus E \subseteq U$, then $(k^+, \psi(b)) \in U$. But $(k^+, \psi(b))$ is not in $E$, so $(k^+, \psi(b)) \in U \setminus E$, and (2) is satisfied. Finally, if $(n^+, c_1) \in U \setminus E$ and $(n^+, c_2) \in U \setminus E$, it follows by construction of $E$ that $c_1 = \psi(b) = c_2$.

Lemma 3

For all $n \in \mathbb{N}$, there exists a unique $b \in A$ such that $(n, b) \in F$.

Proof: By Lemma 1 there exists at least one $b \in A$ such that $(n, b) \in F$. Now consider $(n, b_1) \in F$ and $(n, b_2) \in F$. By construction, $(n, b_1) \in U$ and $(n, b_2) \in U$ for all $U \in \Gamma$. But by Lemma 2, there exists a $U' \in \Gamma$ such that if $(n, b_1) \in U'$ and $(n, b_2) \in U'$, then $b_1 = b_2$.