Proof of a proposition about recursion definition (Terence Tao's Analysis I)

Solution 1:

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.