Exercise 3.5.12. Let $ f: \mathbb N \times \mathbb N \to \mathbb N$ be a function, and let c be a natural number. Show that there exists a function $a:\mathbb N\to \mathbb N$ such that $$a(0)=c$$ and $$a(n++)=f(n,a(n))\;for\;all\;n\in \mathbb N,$$ and furthermore that this function is unique. Tao gives the hint: first show inductively, by a modification of the proof of Lemma 3.5.12, that for every natural number $N\in \mathbb N$, there exists a unique function $a_N:\{ n\in \mathbb N:n\lt N\}\to \mathbb N $ such that $a_N(0)=c$ and $ a_N(n++)=f(n,a(n))$ for all $n\in \mathbb N$ such that $n\lt N$.
In my opinion, we could solve it by proving that $\forall n\in \mathbb N,a(n)\in \mathbb N$ according to mathematcial induction. The property P(n) is:$$\forall n\in \mathbb N, a(n)\;is\;unique$$ P(0) is true. And if P(n) holds, P(n++) is true because different natural numbers must have different successors. $$a(n++)=f(n,a(n))$$ $$a(m++)=f(m,a(m))$$ $$n++=m++\Rightarrow n=m\Rightarrow a(n++)=a(m++)$$ It's similar to the proof of 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$.
This proof indicates both the existence and uniqueness of the function $a$. I don't know why Tao says it's informal.
But regarding the hint, how do we get the function f even if we've got the conclusion from the hint. Also it seems like the function a(n) can be diffentent considering different N. I don't know if the hint is correct.
One has to be careful while forming infinite sets. Simply because $\alpha(n)$ is defined for each $n \in \mathbb{N}$ you cannot form the set $\{(n,\alpha(n)): n \in \mathbb{N}$}.
Existence: Let $\mathcal{C} = \{A \subseteq \mathbb{N} \times \mathbb{N}: (0, c) \in A, (n++, f(n, a(n))) \in A \text{ for all } n \in \mathbb{N}\}$ and order $\mathcal{C}$ by inclusion $\subseteq$. $\mathbb{N} \times \mathbb{N} \in \mathcal{C}$ and therefore the collection $\mathcal{C}$ is not empty. It is easy to see that $C = \bigcap_{A \in \mathcal{C}} A \in \mathcal{C}$ and is the smallest such element in $\mathcal{C}$ with this property.
We claim that $C$ is a graph. ($(x,y) \in C$ and $(x,z) \in C \implies y = z$). If $(0,c),(0,d) \in C$, with $c \not = d$. Then $C- \{(0,d)\} \in \mathcal{C}$ - a contradiction. Similarly if $(n++, f(n,a(n)))$ and $(n++, d) \in C$ with $d \not = f(n, a(n))$ for some $n \in \mathbb{N}$, then $C - \{(n++, d)\} \in \mathcal{C}$ which contradicts the minimality of $C$. Hence $C$ is a graph and therefore defines a function.
Uniqueness can be proved using induction.