0
$\begingroup$

I started reading Terry Tao's Analysis I and am trying to do the second exercise in the text which is to prove

Lemma 2.2.10. Let $a$ be a positive number. Then there exists exactly one natural number $b$ such that $b++ = a$.

The exercise gives the hint to use induction. This seems easy: just prove the case for $a=1$, then use induction on $a$ to prove true for all positive numbers. But in the text the axiom of induction is presented such that induction on $0$ proves for all natural numbers.

Axiom 2.5 (Principle of mathematical induction). Let $P(n)$ be any property pertaining to a natural number $n$. Suppose that $P(0)$ is true, and suppose that whenever $P(n)$ is true, $P(n++)$ is also true. Then $P(n$) is true for every natural number $n$.

How do I know/prove I can do induction starting at $1$ to prove for all positive natural numbers?

$\endgroup$
7
  • 2
    $\begingroup$ Make the statement $P(n)$ be "either $n=0$ or else blah". You'll have to prove that $n=1$ case separately (that is, do two "bases"), but the $n=0$ case is trivial. $\endgroup$ Mar 29 at 16:03
  • 1
    $\begingroup$ Given a property $P$, consider the new property $Q(n)\equiv P(n+1)$. If you want $P$ to hold starting at $1$, that's the same as having $Q$ hold starting at $0$. (And this trick similarly lets you start at any integer.) $\endgroup$ Mar 29 at 16:05
  • 1
    $\begingroup$ Thanks. I just realized another way to put it would be "if $n$ is positive..." which will be automatically true for $0$ $\endgroup$
    – Tbw
    Mar 29 at 16:09
  • $\begingroup$ You can do induction starting anywhere. A base case is nothing more or less than the first case it is true. .... Math is thinking. Not doing magical incantations. Don't get hung up on magical ingredients.... I maybe I should say .. the ingredients aren't magic. The ingredients are a frame of reference-- they provide you with a method to filter vague idea to pure reason; but they don't lock you into religious dogma. $\endgroup$
    – fleablood
    Mar 29 at 17:56
  • $\begingroup$ @fleablood Yeah. I certainly knew that I could just start at 1, but Tao's book and his proofs seem to focus on great amounts of rigor, and the fact that starting at 1 reaches all positive numbers shouldn't be used without proving it, even if it seems obvious. $\endgroup$
    – Tbw
    Mar 29 at 21:38
0
$\begingroup$

You can do induction starting anywhere.

A base case is nothing more or less than the first case it is true. .... Math is thinking. Not doing magical incantations. Don't get hung up on magical ingredients.... I maybe I should say .. the ingredients aren't magic. The ingredients are a frame of reference-- they provide you with a method to filter vague idea to pure reason; but they don't lock you into religious dogma.

But .... if you want to figure out how to use religious dogma. If you want to do induction starting at a base case of say, $27$. That is $P(n)$ is true for all natural numbers $n \ge 27$ you can simple state: Let $Q(m)$ be the statement "$P(m+27)$ is true". Doing induction on $Q(m)$ starting at $0$ will be exactly the same thing as doing induction on $P(n)$ starting at $27$.

AND the induction needn't have a step of only the next number.

If I wanted to prove something is true for every third natural number after $25$ (that is it is true for $25, 28,31$ but not for $26,27, 29,30$ etc, I can do induction starting at $25$ and do an induction step that $P(n)\implies P(n+3)$.

ANd the magical incantation? "Let $Q(n)$ be the statement 'P(25 + 3n) is true'". Then doing induction on $P$ starting at $25$ and only on every third number is the exact same thing as doing induction on $Q$ starting at $0$ and proving for each successor.

You can even do induction going in a negative direction.

=========

Okay.... I'm doing a complete 180 and when comes to basic defining you systems from the very beginning. Those steps need to be rigourous. And here we are defining the natural numbers so it must be rigorous.

I think we need to be careful in our basic statement.

$P(n)$ be the statement if $n \ne 0$ then there is a unique $a$ so that $a++ =n$.

Basic case: $P(0)$ is vacuously true.

But now our induction step is going to be strange and nearly pure bootstrap.

Suppose $P(n)$. Consider $n++$. Let $a = n$. Then $n++ = a++$ so there does exist a natural $a$ so that $a++ = n++$. Now we just have to show there is no other. But if $b \ne a$ is a natural number then axiom 2.4 says $b++ \ne a++ = n++$. So $a$ is unique.

....

Now, I'll admit that barely seems to be induction. Can't we just use 2.4 on $n$ directly? Well..... How do we know that there exists any $a$ so that $a++ = n$?

Well, here's a weird and subtle thing about induction. We know we can start an numbers system with $0$ and for every $n$ we have $n++$ exists. And $1 =0++$. But how do we know that there isn't any $n: 0 < n < 1$ (assuming we have defined $"<"$) or that there is no $m: n < m < n++$

We'll induction say if something is true for if something is true for $n$ implies it is true for $n++$ (and it is true for $0$) then it is true for all natural numbers. This doesn't just mean we can bootstrap all the natural numbers by taking successors. It means that if we do do that we create all the natural number by doing so and there aren't any natural numbers that aren't created this way.

Okay... when I type it out it doesn't sound all that astonishing but think of it. How do we prove that all the numbers we create by doing $0,0++=1; 1++=2$, etc are all and we can't sneek in a number between $2$ and $3$. $0$ is created that way. And if $n$ is so is $n++$. So all natural numbers, by axiom, are and by axiom we can't sneek any in.

$\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.