Proof of recursion theorem I was going through a real analysis textbook The Real Numbers and Real Analysis this morning, and I encountered a theorem stating that:
Let $H$ be a set, let $e\in H$ and $k:H\rightarrow H$ be a function. Then there always exists a unique function $f:\mathbb{N}\rightarrow H$ such that $f(1)=e$, and that $f(n+1)=k(f(n))$ for all $n\in\mathbb{N}$.
As a 1st year undergrad in maths, I have little knowledge in set theory except for the basics, but I simply couldn't help but wonder why does one have to consider the set $$C=\lbrace W\subseteq \mathbb{N}\times H\mid (1,e) \in W,\,\text{and if}\,(n,y)\in W,\,(n+1,k(y))\in W\rbrace$$ and let $f=\bigcap W\in C$ to prove $f$ does have the desired property and it is indeed a function.
Instead, could I not just define the relation to be $$W=\lbrace (a,b)\in \mathbb{N}\times H\mid (1,e) \in W,\,\text{and if}\,(n,y)\in W,\,(n+1,k(y))\in W\rbrace?$$
I know this sounds rather silly, but is there a reason why I can't define a set in this way? Is it because that the set builder notation actually involves the set itself, so I have to justify the existence of such a set beforehand? Or is it because of some other reason?
 A: You want to prove the existence of a function. This means that you have to come up with the set of ordered pairs which is that function.
In the proof given in the book, we define a collection of relations, whose intersection is the wanted function.
What you suggest suffers from one of two possible problems:


*

*Either this is not a well-formed definition, since it uses $W$ inside the definition of $W$; or

*you actually claim that $W$ is a set which is equal to the set defined on the right hand side, but this gives you only the information that $W$ is closed under a certain operation. It, in fact, assumes that $W$ already exists, when you try to prove its existence to begin with.


Instead, the book opts for a different method. First define a collection of relations, then show that they define the wanted function.
A: Suppose we just say that 
$$W=\{(a,b)\in \mathbb{N}\times H \mid (1,e) \in W,\ \text{and if}\ (n,y)\in W,\ (n+1,k(y))\in W\}.$$
As an example, assuming $k$ is not the identity function,
$W$ could contain the following distinct elements:
$$(1,e)$$
$$(2,k(e))$$
$$(2,e)$$
Then $W$ must also contain the elements
$$(3,k(k(e)))$$
$$(3,k(e))$$
and indeed many more elements. But there is nothing that prevents $W$
from containing all the elements already mentioned.
This creates problems. First, there are a lot of different ways to
construct a set $W$ that meets this requirement
($W$ might contain $(2,e)$, or it might not), 
so really $W$ is not a well defined set at all.
Second, a lot of the sets we could construct along the lines of
this "definition" (for example any such set containing the elements
listed above) are not functions. (They have more than one right-hand
element associated with the same left-hand element.)
But when you consider all possible sets $W$ satisfying the given conditions,
you see that $(2,e)$ is not an element of every such set.
Therefore the intersection of all such sets
will not contain $(2,e)$ or any of the other elements that prevent
many of the sets $W$ from being functions.
The intersection contains only the desired elements
$(1,e)$, $(2,k(e))$, $(3,k(k(e)))$, and so forth.
A: 
Instead, could I not just define the relation to be $$W=\lbrace
 (a,b)\in \mathbb{N}\times H\mid (1,e) \in W,\,\text{and if}\,(n,y)\in
 W,\,(n+1,k(y))\in W\rbrace?$$
I know this sounds rather silly, but is there a reason why I can't
  define a set in this way? Is it because that the set builder notation
  actually involves the set itself, so I have to justify the existence
  of such a set beforehand?

My opinion is that this is not a definition by itself. What we have here is the bootstrap process used by the Peano axioms for characterisation of the natural numbers. (See below)
You can write it more suggestive as
$$
\begin{matrix}
(1,e) \in W \\
(n,y) \in W \Rightarrow (n+1,k(y)) \in W
\end{matrix}
\quad (*)
$$
this seems a legitimate recursive definition of a set $W$ to me. Note that the inductive clause requires $(n,y) \in W$ and does not permit any choice from $\mathbb{N} \times H$.
Further it seems evident to me that
$$
W = \{ (n, k^{n-1}(e)) \mid n \in \mathbb{N} \} \quad (**)
$$
where $k^m$ means the $m$-fold application of the function $k$,e.g. $k^3 = k \circ k \circ k$, with the special case $k^0 = \mbox{id}$ and that this can be seen as graph of a function $f$:
$$
G_f = \{ (n, f(n)) \mid n \in \mathbb{N} \}  = W
$$
or in other words
$$
f(n) = k^{n-1} (e) \quad (n \in \mathbb{N})
$$
We have $W \subseteq \mathbb{N}\times H$ because for the first component $1 \in \mathbb{N}$ and $n \in \mathbb{N} \Rightarrow n+1 \in \mathbb{N}$ (see Peano axioms). For the second component we have $e \in H$ and due to $k : H \to H$ we have $k^{n-1}(e) \in H$ for any $n \in \mathbb{N}$.
It is my believe that $(*)$ leads to just $(**)$, there are no more elements in $W$. And here I am unsure, if I can get away with just that or not. 
The problem I have with your excerpt of that proof is 


*

*I lack the imagination for more than one possible set $W$ within $C$. If I am correct that would make the intersection trivial and unnecessary

*if there are different $W$ I would really need to be able to imagine them at least to that detail that I am able to perform the intersection

