1
$\begingroup$

I got Proof of a proposition regarding recursive definitions (from Terence Tao's Analysis I) Here i understood that what tao done in the proof. But still i have some confusion.

Question: Why Terence Tao didn't use inductive hypothesis in the proof of proposition 2.1.16?

Also there are some other proofs too where inductive hypothesis is not used and still these are done by induction. How is this possible.

Proposition:2.1.16 (Recursive definition). Suppose for each natural number n, we have some function $f_n: \mathbb N → \mathbb N$ . Let c be a natural number. Then we can assign a unique natural number $a_n$ to each natural number n, s.t $a_0=c$ and $a_{S(n)}=f_n(a_n)$ for each natural number n.

Notice : I used $S(n)$ instead of $n++$.

$\endgroup$
7
  • 1
    $\begingroup$ I don't understand your question. In that link you provided, the first line of the proof is "We use induction". $\endgroup$
    – Lee Mosher
    Commented Jun 30, 2023 at 16:33
  • $\begingroup$ @LeeMosher Yes. Proof is done by induction. But didn't use inductive hypothesis. $\endgroup$
    – Afzal
    Commented Jun 30, 2023 at 16:48
  • 1
    $\begingroup$ It does use the inductive hypothesis, in the phrase "Now suppose inductively..." $\endgroup$
    – Lee Mosher
    Commented Jun 30, 2023 at 16:52
  • $\begingroup$ @LeeMosher Oh. But author didn't use it. He supposed inductively that $a_n$ assigns a unique natural number. Then he didn't use above assumption to show $a_{S(n)}$ has unique value that is $f_n(a_n)$. $\endgroup$
    – Afzal
    Commented Jun 30, 2023 at 17:03
  • $\begingroup$ I mean author proved base case that is P(0) is true. Now he has to show that for all n ( P(n) $\implies$ P(S(n)) is true. So he assumed P(n) is true and later didn't use P(n) to show P(S(n)) is true. $\endgroup$
    – Afzal
    Commented Jun 30, 2023 at 17:05

1 Answer 1

0
$\begingroup$

Quoting from the proof in the link provided, the inductive hypothesis is used starting in the sentence

Now suppose inductively that the procedure gives a single value to $a_n$.

The next sentence completes the induction:

Then the procedure give a single value to $a_{n++}$, namely $f_n(a_n)$.

Here is a more detailed explanation of that sentence. Knowing from the induction hypothesis that $a_n$ has a single value, and knowing from the hypothesis of the proposition that $f_n$ is a function, it follows from the definition of a function that $f_n(a_n)$ is a single value. That value is then assigned to $a_{n++}$, using the assignment statement $a_{n++} := f_n(a_n)$. This gives a single value to $a_{n++}$ which completes the induction step.

Almost.

In the sentence in parentheses that follows, the author raises an issue: Could one of the later assignment steps $a_{m++} = f_m(a_m)$ cause $a_{n++}$ to be re-assigned a different value? But this could only happen if $m\!+\!+=n\!+\!+$, which by Axiom 2.4 only happens when $m=n$. The issue is therefore irrelevant.

$\endgroup$
1
  • $\begingroup$ I understood that : if $a_n$ is not unique then $a_{S(n)}$ can't be unique. This is how inductive hypothesis used. $\endgroup$
    – Afzal
    Commented Jul 3, 2023 at 6:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .