2
$\begingroup$

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)$?

$\endgroup$
15
  • 1
    $\begingroup$ Why not just f() Sequences can have repeated terms. Consider for example the sequence $1,2,1,3,1,4,1,5,\ldots$. There is no $\,f\,$ such that $\,a_{n+1}=f(a_n)\,$ for that sequence. $\endgroup$
    – dxiv
    Mar 25 '18 at 1:46
  • $\begingroup$ Sometimes we might want to define a sequence $(a_0,a_1,\ldots)$ by saying something like, let $a_0=1$ and let $a_n = n \cdot a_{n-1}$ for all $n \geq 1$. But, somebody else might object: does such a sequence really exist? And if there does exist a sequence satisfying these properties, is the sequence unique? (This objection would probably only come from someone who is trying to prove everything very carefully from the axioms.) $\endgroup$
    – littleO
    Mar 25 '18 at 1:51
  • 1
    $\begingroup$ @dxiv So we're just taking one input through a function, taking that output and putting it into some different function, taking that output and putting it into yet another function, etc? $\endgroup$
    – user525966
    Mar 25 '18 at 1:51
  • $\begingroup$ That's pretty much it. $\endgroup$
    – Lee Mosher
    Mar 25 '18 at 1:53
  • $\begingroup$ But still, why? What is this meant to accomplish or show? $\endgroup$
    – user525966
    Mar 25 '18 at 1:53
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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)$
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.