# The recursion principle.

In the book that I read there is a exercise where we need to prove the recursion principle that is written in the next fashion.

Proposition: Let $f: \mathbb{N} \times \mathbb{N}\rightarrow \mathbb{N}$ be a function and $c \in \mathbb{N}$. Then, there exist a unique function $a: \mathbb{N} \rightarrow \mathbb{N}$ such that: $a(0):=c\:$ and $\:a(n^{+}):=f(n,a(n))$; (where $n^{+}:=n \cup \left\{n \right\}$).

The book give us a hint: Show that for each natural number there exist a n-function $a_{n}: n^{+}\rightarrow \mathbb{N}$ such that $a_{n}(0):=c\:$ and for each $i \in n$, $\:a_{n}(i^{+}):=f(i,a(i))$.

And here is what I have at this moment:

Claim 1: For each natural number there exist a n-function.

Proof of Claim 1: Let "$\varphi (x)$" be the following:

$\forall x \forall y \forall y' ( \langle x,y\rangle \in a_{n} \wedge \langle x,y'\rangle \in a_{n} \rightarrow y=y' ) \wedge Dom(a_{n}) = n^{+} \wedge a_{n} (0)= c \,\wedge \, \forall i (i \in n \rightarrow a_{n} (i^{+}) = f(\,i,a_{n} (i))\,).$

Now we can apply the separation axiom and form a set which we define as: $S : = \left\{n \in \mathbb{N}: \exists a_{n} \varphi (x) \right\}$

For n=0, we require a function with domain $0^{+}$. And as the only element of the domain is $0$, we can form the ordered pair $a_0 = \left\{ \langle 0, c\rangle \right\}.$ Which is a function, its domain is in fact $n^{+}$ and the last statement of the formula is vacously true. Then $0 \in S$.

Suppose $n\in S$ that means $a_{n}$ exist. Then, we define $a_{n^{+}}$ as follows:

$a_{n^{+}}: = a_{n} \cup \left\{ \langle n^{+}, f(n,a_{n} (n)) \rangle \right\}$.

So, only we need to show that $a_{n^{+}}$ is a n+1- function.

i) $\langle x,y \rangle \in a_{n^{+}} \leftrightarrow \langle x,y \rangle \in a_{n} \vee \langle x,y \rangle \in \left\{ \langle n^{+}, f(n,a_{n} (n)) \rangle \right\}$

As $a_{n}$ is a function by our inductive hypothesis, only we need to show that $\left\{ \langle n^{+}, f(n,a_{n} (n)) \rangle \right\}$ is a functional relation:

$\langle x,y \rangle \in \left\{ \langle n^{+}, f(n,a_{n} (n)) \rangle \right\} \wedge \langle x,y' \rangle \in \left\{ \langle n^{+}, f(n,a_{n} (n)) \rangle \right\} \rightarrow y = f(n,a_{n} (n) = y'$. It follows because f is indeed a function.

ii) $Dom (a_{n^{+}}) = Dom(a_{n}) \cup \left\{ n^{+} \right\}$. By hypothesis we know that $Dom(a_{n}) = n^{+}$. Hence $n^{+} \cup \left\{ n^{+} \right\} = n^{++}$.

iii) As $a_{n}\subset a_{n ^ {+}}$, and by hypothesis we know that $\langle 0,c \rangle \in a_{n}$. Then $\langle 0,c \rangle \in a_{n ^ {+}}$.

iv) $\forall i \in n^{+}. \langle i^{+},c \rangle \in a_{n ^ {+}} \leftrightarrow \langle i^{+},c \rangle \in a_{n} \vee \langle i^{+},c \rangle \in \left\{ \langle n^{+}, f(n,a_{n} (n)) \rangle \right\}$.

If $\langle i^{+},c \rangle \in a_{n}$ by hypothesis we know that $c = f(i, a_{n}(i))$ as desired. On the other hand if $\langle i^{+},c \rangle \in \left\{ \langle n^{+}, f(n,a_{n} (n)) \rangle \right\}$ it follows by construction.

Then $n^{+} \in S$, and we conclude by induction that, there exist a n-function for every natural number.

Claim 2: For each natural number this function is unique.

Proof of claim 2: For n = 0, the only 0-function is $a_0 = \left\{ \langle 0, c\rangle \right\}$. If we assume that holds for n, we need to show that also holds for $n^{+}$.

Let $a_n = a'_n$, for construction of n-functions we know that:

$a_{n^{+}} = a_{n} \cup \left\{ \langle n^{+}, f(n,a_{n} (n)) \rangle \right\} =a'_{n} \cup \left\{ \langle n^{+}, f(n,a'_{n} (n)) \rangle \right\} =a'_{n^{+}}$. Therefore all the n-functions are uniques.

At this point I'm not sure how could I derive exactly the function a, I think that maybe using the union of all the families $a_{n}$. But I'm not really sure, somebody knows?

I'm not sure here, but if we use the replacement axiom for each n-function we have:

Let "$\varphi (x,y)$" be the formula:

$( x \in \mathbb{N} \wedge y = \,x-function ) \vee (\neg x \in \mathbb{N} \wedge y = 0 )$.

For the claim 2 there exist a unique n-function for each n, therefore "$\varphi (x,y)$" is functional. And we can apply replacement to derive: $\left\{a_{n}: n\in \mathbb{N} \right\}$.

And (maybe) define the function $a$ to be: $a: = \bigcup \left\{a_{n}: n\in \mathbb{N} \right\}$

Here is my attempt: By the union axiom and the replacement schema axiom $a$ defined as above is a set. So, only we need to show that indeed is a function and that all property that we wish really holds.

Claim 3: The relation a is a functional relation.

Proof of Claim 3: To $a$ be a functional relation we need to show $\langle x,y \rangle \in a \wedge \langle x,y' \rangle \in a \rightarrow y = y'.$

if $\langle x,y \rangle \in a \leftrightarrow \exists n \in \mathbb{N}. \langle x,y \rangle \in a_{n}$ at the same way $\langle x,y' \rangle \in a \leftrightarrow \exists m \in \mathbb{N}. \langle x,y' \rangle \in a_{m}.$ And as $m \in n \vee n\in m \vee n = m$.

(1) If $n = m$, by claim 2 we have that $a_{n} = a_{m}$ and as $a_{n}$ is functional. We're done, that means $y = y'$ because $\langle x,y \rangle \in a_{n} \wedge \langle x,y' \rangle \in a_{n} \rightarrow y = y'$.

(2) If $m \in n\, (m < n)$ by construction we know that $a_{m} \subset a_{n}$. Then $\langle x,y' \rangle \in a_{m} \rightarrow \langle x,y' \rangle \in a_{n}$. As $\langle x,y \rangle \in a_{n} \wedge \langle x,y' \rangle \in a_{n}$ and as $a_{n}$ is functional. Then $y = y'$ as desired.

(3) At the same way if $n \in m\, (n < m),\, a_{n} \subset a_{m}$. Then $\langle x,y \rangle \in a_{n} \rightarrow \langle x,y \rangle \in a_{m}$. As $\langle x,y \rangle \in a_{m} \wedge \langle x,y' \rangle \in a_{m}$ and as $a_{m}$ is functional. Then $y = y'$ as desired.

Then $a$ is a functional relation.

Claim 4: The functional relation a, is a function such that $a(0) = c \wedge a (i^{+}) = f(i, a(i))$.

Proof of claim 4:

(1) As definition all the n-function evaluated at 0 are c, therefore the union of all of them is c, $\langle 0,c \rangle \in a$ as desired.

(2) If $i^{+} \in \mathbb{N}. \langle i^{+},y \rangle \in a \leftrightarrow \exists n\in \mathbb{N}. \langle i^{+},y \rangle \in a_{n}.$ By construction of all the n-function that means $y = f(i, a_{n} (i))$. So, only we need to show that $a_{n} (i) = a (i)$. But since $a_{n}$ is the restriction of $a$ at n, that follows inmediately.

What do you think? Is it correct?

The other exercise the book says this:

Show using the last proposition there exist only one version of the natural numbers in set theory.

My attempt: Let $\mathbb{N'}$ be a set such that the Peano's axioms hold. Let f be a function, $f : \mathbb{N} \times \mathbb{N'} \rightarrow \mathbb{N'}$, such that $\langle n,n' \rangle \mapsto n'^{+}$. And, $a: \mathbb{N}\rightarrow \mathbb{N'}$ such that, $a(0) = 0'$ and $a(n^{+}) = f(n, a(n)) = n'^{+} =(a(n))^{+}$. By the last proposition the function exist and it is unique.

Injective part:

For $n = 0$ we have $a (0) = a(0^{*}) = 0'$, so we need to show that $0 = 0^{*}$. By the sake of the contradiction suppose $0 \neq 0^{*}$. Therefore $0^{*} = k^{+}$ for some $k \in \mathbb{N},\, a(0^{*})=a(k^{+}) = k'^{+}$. And as the Peano's Axiom hold in $\mathbb{N'}, k'^{+} \neq 0'$, a contradiction. Then, $0=0^{*}$.

Suppose that our assumption holds for n, we need to show that also holds for $n^{+}$. If $n'^{+}=a (n^{+}) = a (n^{*+})=n'^{*+}$. By the Peano's axioms we have $n'^{+} = n'^{*+} \rightarrow n'= n'^{*}$. As $a(n)=n' = a(n^{*})=n'^{*},\; a(n) = a(n^{*}) \rightarrow n = n^{*}$ (by the inductive hypothesis). Hence $n^{+} = n^{*+}$. That closed the induction.

Surjective part:

By definition we know that $0' = a (0)$, so there exist a $0 \in \mathbb{N}$. Suppose that our assumption holds for n', that means $n' = a(n)$ there exist a $n \in \mathbb{N}$. So, $n' ^{+}=(n')^{+} = (a(n))^{+} = a(n^{+})$. That closed the induction.

Hence exist a bijection between them.

Any suggestion about all of these exercises....

• I don't know what an $n$-function is but if you're allowed to use the usual principle of recursive definition then you should. – dfeuer Jul 15 '13 at 20:18
• @PeterTamaroff This is a specific application of that principle. I see that he's going through all the steps to prove the principle for this special case, which looks like overkill. – dfeuer Jul 15 '13 at 20:20
• @dfeuer Heh, true. I read all this too quickly. – Pedro Tamaroff Jul 15 '13 at 20:22
• @dfeuer An $n$ function seems to be a function with domain $n^{+}$ mapping to the naturals. – Pedro Tamaroff Jul 15 '13 at 20:23
• @PeterTamaroff Exactly that is what the book define them. Any function with domain $n^{+}$ such that $\varphi (x)$ is true. – Jose Antonio Jul 15 '13 at 20:29

## 1 Answer

Your proof of the recursion theorem for $\Bbb N$ looks spot-on. Good job, this proof is nontrivial to write correctly :).

In the second exercise, you take an overly long route, as well as glance over the proof that $a(n) = n'$.

If you first prove by induction on $\Bbb N$ that $a(n) = n'$, then injectivity is immediate.

Subsequently take $S = \{n' \in \Bbb N': \exists m: a(m) = n'\}$ and conclude surjectivity by induction on $\Bbb N'$. (This is actually more or less identical to what you wrote.)