"Recursive definitions" in Tao's Analysis Vol I

Question

I am totally confused when Tao gets into recursive definitions (page 26).

Paraphrasing, the axioms of natural numbers let us define sequences recursively. Suppose we want to build a sequence $a_0, a_1, a_2, ...$ by first defining $a_0 := c$ and then letting $a_1 := f_0(a_0)$, then $a_2 := f_1(a_1)$, etc. In general $a_{n++} := f_n(a_n)$. Now he claims that this procedure gives a single value to the sequence element $a_n$, i.e. there is a unique function $a(n)$ from $N$ to $N$ such that $a(0) = c$ and $a(n\text{++}) = f_n(a(n))$ for each natural number $n$.

Proof: Induction. $a_0 := c$ as a base case (which does not get redefined by anything else since $n\text{++}$ cannot be $0$ by Peano's third axiom). Then suppose inductively the procedure gives a single value to $a_n$. Then it gives a single value to $a_{n++} := f_n(a_n)$, which does not get redefined anywhere due to the successor function being injective. This completes the induction and so $a_n$ is defined for each natural number $n$ with a single value assigned to each $a_n$.

Now, I have no idea what's going on here. I've read this at least ten times and I'm just not seeing it.

I don't understand what he's doing here, what he's proving, what he's using this for, etc. He explains this definition right before we move forward into the definitions and derivations for things like addition: $0+m=m$ and $(n\text{++}) + m = (n+m)\text{++}$.

I don't understand why we have basically $n$ different functions denoted $f_n()$. Why not just $f()$? What is this function supposed to do? What does this have to do with recursion? What is this allowing us to do?

Tao sort of pulls this recursive paragraph out of nowhere and I don't understand what he's connecting this to or how it works or why we need it.

For example, if we let $S$ represent the successor function, then addition is defined as $m+0 = m$ with $m+S(n) = S(m+n)$. How would this functional, recursive relationship map between this and what Tao is talking about? What is $a_{n\text{++}}$? What is $f_n(a_n)$? And why not $f(a_n)$?

Answer 1

See footnote 3 (3rd ed., page 23):

"Proposition 2.1.16 (Recursive definitions) can be formalized more rigorously in the language of set theory."

Thus, we have to use the Recursion Theorem.

Tao defines by recursion the function $n+m$ (i.e. $+(n,m)$). It is a binary function, abd thus we can rewrite it as $F_m(n)$.

For $n=0$, we have : $F_m(0)=0+m=m$ where $m$ is used as the $a$ (or $c$) of the theorem.

Then, assuming defined the case $n+m$, he uses it to define the next case: $F_m(s(n))=s(n)+m=s(n+m)$, where we use the previously defined $(n+m)$ and we use the successor function $s(x)$ [denoted with $x++$ by Tao] as the function $f$ of the Recursion theorem.

Answer 2

Recursions aren't always via function constant. For example, you can define the triangular numbers recursively by

• $t_0 = 0$
• $t_n = n + t_{n-1}$

The formula we use to compute $t_n$ depends on $n$ in addition to the previous value $t_{n-1}$.

So, we can't express this recursion with a single univariate function $f$. The requisite $f_n$ are given by $f_n(x) = x + (n+1)$.

Another common example is the factorial:

• $0! = 1$
• $n! = n \cdot (n-1)!$

This time the functions are $f_n(x) = (n+1) x$.

---

It may help not to think of infinitely many functions, but instead a single two-variable function. That we have a two-variable function $g$ and the recursion is that $a_{n++} = g(n, a_n)$.

This is basically the same thing:

• Given a sequence $f_n$, we define $g$ by $g(n,x) = f_n(x)$
• Given $g$, we define a sequence $f_n$ by $f_n(x) = g(n,x)$