Tao Analysis I - 3.5.12 (i)

Exercise 3.5.12 (i)

This exercise will establish a rigorous version of Proposition 2.1.16 that avoids circularity (in particular, avoiding the use of any object that required Proposition 2.1.16 to construct).

(i) Let $X$ be a set, let $f : \mathbb{N} \times X \to X$ be a function, and let $c$ be an element of $X$. Show that there exists a function $a : X \to X$ such that

$$a(0) = c$$

and

$$a(n++) = f(n, a(n)) \text{ for all } n \in \mathbb{N}$$

and furthermore that this function is unique. (Hint: first show inductively, by a modification of the proof of Lemma 3.5.11, that for every natural number $N \in \mathbb{N}$, there exists a unique function $a_N:\{n \in \mathbb{N}:n \leq N\} \to X$ such that $a_N(0)=c$ and $a_N(n++)= f(n,a_N(n))$ for all $n \in \mathbb{N}$ such that $n < N$.)

Discussion

I found this exercise tricky because it needs clarity on what we need to do and show. This answer on math stack exchange is helpful on proof strategy (link).

It is also worth pondering on the point of the exercise. It shows that some recursively defined functions can be valid functions. Without proof we can't assume a function defined in terms of itself is a valid function. 

Exploration

To clarify the objects we're dealing with let's write out some examples.

For $N=0$, we have $a_N$ as

$$a_0 : \{0\} \to X \quad \text{ where } \quad a_0(0) = c$$

Note that $a_0$ is a function, defined over the domain $\{0\}$, the subscript zero is not a parameter or input to that function.

Our definition of $a_N$ must conform to the two conditions:

• $a_N(0)=c$
• $a_N(n++)= f(n,a_N(n))$ for all $n \in \mathbb{N}$ such that $n < N$

Our $a_0$ meets the first condition by its own definition.

What about the second condition? The second condition is vacuously true because there are no $n \in \mathbb{N}$ such that $n < N=0$.

For $N=1$, we have $a_N$ as

$$a_1 : \{0, 1\} \to X \quad \text{ where } \quad \begin{cases}a_1(0) &= c \\ \\ a_1(1) &= f(0, a_1(0)) \\ & = f(0, a_0(0)) \end{cases}$$

Here $a_1(0)$ is trivially defined to be $c$, and $a_1(1)$ maps to a unique element of $X$ because $f$ is given as a well-defined function. Thus $a_1$ is also a well-defined function.

For $N=2$, we have $a_N$ as

$$a_2 : \{0, 1,2\} \to X \quad \text{ where } \quad \begin{cases}a_2(0) &= c \\ \\ a_2(1) &= f(0, a_2(0)) \\ & = f(0, a_1(0))  \\ \\ a_2(2) &= f(1, a_2(1)) \\ & = f(1, a_1(1)) \end{cases}$$

Note how we choose to define $a_1(0)=a_0(0)=c$, and $a_2(1)=a_1(1)$ , and in general

$$a_N(n)=a_{N-1}(n)$$

because we want each $a_N$ to be equal to all previous $a_M$ over their shared domain $\{0, \ldots, M\}$, where $M < N, n \leq N$.

So in general we have $a_N$ as

$$a_N : \{0, \ldots, N\} \to X \quad \text{ where } \quad \begin{cases}a_N(0) &= c \\ \\ a_N(n++) &= f(n, a_N(n)) \\ & = f(n, a_{N-1}(n)) \end{cases}$$

where $n < N$.

On the question of uniqueness, each $a_N$ is unique if $f$ is unique, which it is because we are told it is a well-defined function.

Solution

To show that for every natural number $N \in \mathbb{N}$ there exists a unique function $a_N$ as defined in the question, we will use induction on $N$. 

Consider the statement $P(N):$ there is a unique function $a_N:\{n \in \mathbb{N}:n \leq N\} \to X$ which meets the two conditions:

• $a_N(0)=c$
• $a_N(n++)= f(n,a_N(n))$ for all $n \in \mathbb{N}$ such that $n < N$

Base case P(0): We can define a function $a_0 : \{0\} \to X$ where $a_0(0) = c$.

This meets the first condition by definition, and the second condition is vacuously true because there is no $n \in \mathbb{N}$ such that $n<N=0$.

This $a_0:\{0\}\to X$ is also unique. If there were another function $b_0:\{0\}\to X$ which met the same conditions, it would mean $b_0(0)=c$. Since they map every element of the domain, in this case $\{0\}$, to the same $c \in X$, the two functions are equal.

Inductive Hypothesis P(N): We will assume the function $a_N:\{0, \ldots, N\} \to X$ exists, meets the two conditions, and is unique.

Inductive Step P(N++): We need to show $a_{N+1}$ exists, meets the two conditions, and is unique. Let's define it as follows:

$$a_{N+1} : \{0, \ldots, N+1\} \to X \quad \text{ where } \quad \begin{cases}a_{N+1}(0) &= c \\ \\ a_{N+1}(n++) &= f(n, a_{N++}(n)) \\ & = f(n, a_{N}(n)) \end{cases}$$

where $n < N+1$.

By its definition it meets the first condition, $a_{N+1}(0)=c$. The second condition is met because we chose to define $a_{N}$ to equal $a_{N-1}$ over their shared domain $\{0, \ldots, N-1\}$, which gives us $f(n, a_{N++}(n)) = f(n, a_{N}(n))$, which in turn means $a_{N+1}$ exists.

The inductive hypothesis tells us $a_N$ exists and is unique. This means $f(n, a_{N}(n))$ is unique because $f$ is a well-defined function. So if $f(n, a_{N}(n))$  exists and is unique, we have shown $a_{N+1}$ exists and is unique.

Thus, by induction, a unique $a_N$ exists for all $N \in \mathbb{N}$. 

This means there exists a function $a : X \to X$ such that

$$a(0) = c$$

and

$$a(n++) = f(n, a(n)) \text{ for all } n \in \mathbb{N}$$

and furthermore that this function is unique. $\square$