# 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?

• Stupid question: What is $e$, the Euler number, or some generic element? I think the latter. – mvw Jul 10 '15 at 22:13
• yes, it's just a generic element in H. – wanwuwi Jul 10 '15 at 22:19

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.

• I see. But if we put this specific theorem aside, and just consider whether I could define a set using notations that involves the set itself, would that be feasible then? – wanwuwi Jul 10 '15 at 22:24
• $W$ as defined above would still be ambiguously defined, even if it were OK that it's not necessarily a function. I'm reluctant to say you can never define a set using a predicate that mentions itself, because someone may come up with a clever counterexample; but it's hard to imagine why one would want to try to write such a definition. – David K Jul 10 '15 at 22:42
• Thank you for your explanation, it really helps me a lot, especially in the summer holiday when I won't be able to see any of my lecturers. – wanwuwi Jul 10 '15 at 22:44
• @wanwuwi: You can use recursive definitions to define things only if you allow it to be partial in a certain sense. To see why one just has to consider the Russell construction "Let $S=\{ x : x \notin x \}$.". It cannot refer to a set without being self-contradictory. However, if we think of the notation $x \in y$ as simply $1_y(x)$ (the indicator function for $y$ applied to $x$), then it clearly may not halt if $1_y$ is a partial function. So $S = \{ x : x \notin x \}$ would define a partial function that does not halt on itself as input. Indeed both $S \in S$ and $S \notin S$ would not halt. – user21820 Jul 11 '15 at 3:36
• @wanwuwi: Similarly, both "Let $S = \{ x : x = S \}$" and "Let $S = \{ x : x \ne S \}$" would define partial functions that never halt on any input. And I should say that in conventional set theory all sets are essentially total functions on the universe, so you cannot do any of these recursive constructions there. – user21820 Jul 11 '15 at 3:40

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:

1. Either this is not a well-formed definition, since it uses $W$ inside the definition of $W$; or
2. 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.

• Does it mean that if there is a way to rephrase the statement such that it does not involves $W$(which I know probably doesn't exist), then defining the set in this way would be possible? – wanwuwi Jul 10 '15 at 22:26
• @wanwuwi: The point is that you cannot define something in terms of itself. That is called circular and will get you nowhere. It's just like defining "the" as "the word that is used as the definite article in English". If you didn't already know what "the" means, can you understand what it means after reading my definition? – user21820 Jul 11 '15 at 4:00

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
• Why would you get that $W$ is a function? All this definition gives you is that $W$ supersets the wanted function. But $\Bbb N\times H$ satisfies the definition you present as well. – Asaf Karagila Jul 10 '15 at 21:44
• $(1,e)\in\Bbb N\times H$? Yes. If $(n,y)\in\Bbb N\times H$, is $(n+1,k(y))\in\Bbb N\times H$? Yes. Therefore $W=\Bbb N\times H$. Doesn't seem to work very well if $H$ has more than one element. – Asaf Karagila Jul 10 '15 at 21:46
• Yes, $W$ is a set. Functions are sets. I don't understand your comment... (Sorry for posting several comments at once!) – Asaf Karagila Jul 10 '15 at 21:46
• To make Asaf's comment clear, your so-called recursive definition does not specify what is not in $W$. In order to do so, you will end up having to do either of two things: (1) construct all sets that satisfy those conditions and then prove that there is at least one such set and then take their intersection (which is what the author of the textbook presumably did; I hope they didn't forget to prove that at least one such set exists otherwise the intersection won't). (2) ... [continued] – user21820 Jul 11 '15 at 4:11
• Define a function that extends any function $g$ with domain $[1..m]$ for some $m \in \mathbb{N}$ such that $g(1) = e$ and $g(n+1) = k(g(n))$ for any $n \in [1..m]$ to a function with domain $[1..m+1]$ such that $g(1) = e$ and $g(n+1) = k(g(n))$ for any $n \in [1..m+1]$. Then construct $S = \{ m : m \in \mathbb{N} \land \text{there is a function$g$on$[1..m]$such that$g(1) = e$and$g(n+1) = k(g(n))$for any$n \in [1..m]$} \}$ and prove by induction that $S = \mathbb{N}$. Then prove that the union of the functions that witness each element in $S$ is a function with the desired properties. – user21820 Jul 11 '15 at 4:24