# Proof of a proposition regarding recursive definitions (from Terence Tao's Analysis I)

I'm currently reading Terence Tao's book Analysis I, and I got stuck on his proposition 2.1.16 about recursive definitions ; actually, I don't understand his (informal) proof of it.

First, here are the five Peano axioms he's using :

Axiom 2.1. $$0$$ is a natural number.

Axiom 2.2. If $$n$$ is a natural number, then $$n{++}$$ is also a natural number.

Axiom 2.3. $$0$$ is not the successor of any natural number ; i.e., we have $$n{++} \ne 0$$ for every natural number $$n$$.

Axiom 2.4. Different natural numbers must have different successors ; i.e., if $$n, m$$ are natural numbers and $$n \ne m$$, then $$n{++} \ne m{++}$$. Equivalently, if $$n{++} = m{++}$$, then we must have $$n=m$$.

Axiom 2.5. (Principle of mathematical induction). Let $$P(n)$$ be any property pertaining to a natural number $$n$$. Suppose that $$P(0)$$ is true, and suppose that whenever $$P(n)$$ is true, $$P(n{++})$$ is also true. Then $$P(n)$$ is true for every natural number $$n$$.

And here is the proposition, and the proof I'm stuck on :

Proposition 2.1.16 (Recursive definitions). Suppose for each natural number $$n$$, we have some function $$f_{n} : \mathbb{N} \rightarrow \mathbb{N}$$ from the natural numbers to the natural numbers. Let $$c$$ be a natural number. Then we can assign a unique natural number $$a_{n}$$ to each natural number $$n$$, such that $$a_{0} = c$$ and $$a_{n{++}} = f_{n} (a_{n})$$ for each natural number $$n$$.

Proof. (Informal) We use induction. We first observe that this procedure gives a single value to $$a_0$$, namely $$c$$. (None of the other definitions $$a_{n{++}}:= f_{n} (a_n)$$ will redefine the value of $$a_0$$, because of Axiom 2.3.) Now suppose inductively that the procedure gives a single value to $$a_n$$. Then it gives a single value to $$a_{n{++}}$$, namely $$a_{n{++}}:= f_{n} (a_n)$$. (None of the other definitions $$a_{m{++}}:= f_{m} (a_{m})$$ will redefine the value of $$a_{n{++}}$$, because of Axiome 2.4.) This completes the induction, and so $$a_n$$ is defined for each natural number $$n$$, with a single value assigned to each $$a_n$$.

I don't understand how does that prove anything. I feel like all he's saying is that « all natural numbers are different from each others » ; I don't understand why we couldn't have, for example, $$a_0 = a_1 = c$$ (for instance, if we consider the Fibonacci sequence : $$0, 1, 1, 2, ...$$, we have $$a_1 = a_2 = 1$$).

I actually found another proof of uniqueness on Wikipedia (regarding the Recursion theorem) and I think I understood it, but I really would like to understand Tao's point of view as well.

Finally, shouldn't we prove that such a function exists as well, instead of just supposing it exists ? I found this document which gives a proof for the existence of such a function (at pages 2-3), but I'm a little bit confused about the way they do it: can we really "imagine" or "create" such sets as $$S$$ and $$g$$, like they do, and draw conclusions from them? Another thing that disturbs me regarding their approach is that Tao doesn't talk about sets before chapter 3, and the proposition above comes from chapter 2... so the question here is: how could we prove the existence of such functions as the ones described in the recursion theorem without knowing anything about sets and set theory?

So, as you can see... I'm pretty confused about a lot of things. Any help would be greatly appreciated!

• We could have $a_0 = a_1 = c$ just as long as $a_1=f_0(a_0)=f_0(c)=c$. Nothing in his definition prevents that.
– Arby
Apr 13 '17 at 6:43
• He is manufacturing the sequence $\{ a_n \}$. He does not say that all $a_n$ are distinct; what he is saying is that the "procedure" never loops. i.e. that it never assign two different values to $a_n$ ensuring that the result is a function $F : \mathbb N \to \mathbb N$ such that $F(n)=a_n$. Apr 13 '17 at 8:36
• NO; consider the "tricky" case of the inductive step: we have that $a_{n++} := f_n(a_n)$. This is a definition, and thus we have nothing to say "against" it; the issue is: "it may happens that for a "later" $m$ the corresponding def $a_{m++} := f_m(a_m)$ makes a loop ?" i.e. that $m++=n++$ (and not that $a_{m++} = a_{n++}$ that is perfectly acceptable...) ? The answer is NO, because if $m++=n++$, then - by Ax.2.4 - $m=n$ and thus $f_m(a_m)=f_n(a_n)$ and we have no risk of "multiple values". Apr 13 '17 at 9:20
• You can apply it to the recursive def of sum: $+$. Basis : $x+0 :=0$ here we have $c=0$ and Ind.step: $x+(n++)=(x+n)++$ here we have $a_{n++}=x+(n++)$ and $a_n=(x+n)$ and $f_n=s$ (the successor function). The Th about recursive defs licenses us to assert that we have a "single" function $+$ such that $+(x,n)$ is a well-defined value for every $n$. Apr 13 '17 at 9:25
• Last try :-) assume that $m++=n++$ but $m \ne n$. When we arrive at $m++$ after having alteady defined $a_{n++}$ we define $a_{m++}$; but by assumption we are looping on the "index" and thus we get a new value $a^*_{n++}$ for the "index" that we have already used. But under our assumption $m\ne n$ and thus $f_m(a_m)$ can be different from $f_n(a_n)$ and thus we have that $a^*_{n++} \ne a_{n++}$, getting the undesired multi-value. Apr 13 '17 at 10:26

The proposition states that if we have a countably family of functions

$$\{ f_n \mid f_n : \mathbb{N} \rightarrow \mathbb{N}, n \in \mathbb{N}\}$$

then we can always, by choosing a seed $c \in \mathbb{N}$, use the family to define a unique sequence of natural numbers $\{ a_k \}_{k \in \mathbb{N}}$ given by

• $a_0 = c$
• Otherwise, $a_{n++} = f_n(a_n)$

For an example of such a sequence, consider the family where $f_n(x) = x^2 + n$. Let $c = 2$; then we get the sequence

$$\{ 2, 2^1+1, (2^1+1)^2+2, \ldots \} = \{ 2, 3, 11, 124, \ldots \}$$

The proof of uniqueness relies on Axiom 2.5; the property $P(n)$ is

$P(n)$: For all $n \in \mathbb{N}$, $a_n$ is uniquely defined.

$P(0)$ holds, since there is precisely one clause defining $a_0$.

Now we show that if $P(n)$ is true, then so is $P(n{++})$.

So we must show that $a_{n++}$ is uniquely defined. Axiom 2.3 tells us that we cannot have used the first clause, $a_0 = c$, to define $a_{n++}$, so we must have used the second clause, $a_{++} = f_n(n{++})$, to define $a_{n++}$. But since $a_n$ is uniquely defined and $f_n$ is a function, the value $a_{n++}$ is also unique. This completes the proof.