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!
 A: 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_{n++} = f_n(a_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.
