1
$\begingroup$

First of all, I should note that I'm working on Peano's axioms for constructing natural numbers.

For example, lets try to prove that "every natural number is the sum of four squares" by induction.The proof as follows;

i-) Show that $0$ satisfies the condition.

ii-) Assume that $n$ also satisfies the condition, and derive that $n+1$ also satisfies the condition.

The induction should work for proving this kind of a theorem because 0 will satisfies the condition and by applying $ii-)$ where $n=0$, $1$ will also satisfy, and repeating the same procedure, all the natural numbers will satisfy the condition.

However, lets consider the theorem;

"Every non-zero element of N has blah."

In the proof of this kind of a theorem, what it has been done is that they show that $0$ satisfies the theorem (since 0 makes the assumption false), and again apply the second condition of induction.

But why this is also work as it works in the first example ? What is the logic ?

I should also note that, induction is given as the fourth axiom of Peano, so I cannot talk about the proof of induction, but what I am asking is an intuition for the logic why it works.

|cite|improve this question
$\endgroup$
  • $\begingroup$ We may start from $1$ and prove $P(1)$ and $P(n) \to P(n+1)$. This amounts to proving (by induction): $\forall n (n \ge 1 \to P(n))$ which in turn is $\forall n (n > 0 \to P(n))$. $\endgroup$ – Mauro ALLEGRANZA Sep 18 '17 at 12:15
  • $\begingroup$ @MauroALLEGRANZA I'm asking for an intuition for why it works. $\endgroup$ – onurcanbektas Sep 18 '17 at 17:27
  • $\begingroup$ If the theorem is not true for 0, you can NOT use that as a base case. $\endgroup$ – user370967 Sep 18 '17 at 17:36
  • $\begingroup$ @Math_QED But the theorem is vacuously true for zero, so you can use it as a base case. $\endgroup$ – DanielV Sep 18 '17 at 17:47
  • 1
    $\begingroup$ You must be careful with that though. Make sure the proof for n -> n+1 works with n = 0, otherwise n=1 (or n = k with k>1) should be used as base case $\endgroup$ – user370967 Sep 18 '17 at 17:49
1
$\begingroup$

Alternatively, if you want to prove $P(n)$ for $n\in \{1, 2, 3, \cdots \}$, you could instead prove $P(n+1)$ for $n\in \{0, 1, 2, \cdots \}$ by induction. For the base case, prove $P((0)+1)$ or $P(1)$. For the inductive step, you would then, for any $k\in\{0, 1, 2, \cdots \}$, prove that $P(k+1)\implies P((k+1)+1)$ or $P(k+2)$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thank you for your answer.It is quite logically.However, my point is that the axiom does not say anything about those cases, so why do we need those extra steps if the axiom does not care those situations ? $\endgroup$ – onurcanbektas Sep 28 '17 at 14:17
  • 1
    $\begingroup$ Yes, it does. The "condition" your axiom refers to is given by $P(n+1)$. The base case (for $0$) would be to prove $P(0+1)$ or $P(1)$. $\endgroup$ – Dan Christensen Sep 28 '17 at 14:21
  • $\begingroup$ Ok, so if we look to the big picture, using the axioms in their pure form is equivalent to the method that you have described, so the transaction from $0$ to $1$ is actually embedded in the axioms, hence both methods (yours and mine) is the same thing.Am I right ? $\endgroup$ – onurcanbektas Sep 28 '17 at 17:30
  • $\begingroup$ I don't understand "the transaction from 0 to 1 is actually embedded in the axioms," but perhaps another example will clear things up for you. Suppose you want to prove $P(n)$ for $n\in \{5, 6, 7,\cdots \}$. We could use ordinary induction to prove that $P(n+5)$ or $n\in \{0, 1, 2, 3, \cdots \}$.The base case (for $0$) would be $P(0+5)$ or $P(5)$. The inductive step would be to prove that, for any $k \{0, 1, 2, \cdots \}$, we have $P(k+5) \implies P((k+5)+1)$ or $P(k+6).$ $\endgroup$ – Dan Christensen Sep 29 '17 at 3:30
  • $\begingroup$ @Got it, thanks a lot, this was troubling me for quite a time. $\endgroup$ – onurcanbektas Sep 29 '17 at 5:22
4
$\begingroup$

If you want to prove by induction that every natural number has blah, there are two ways to proceed. One, suggested in the comments, is to start the induction at $1$ (not at $0$), proving "$1$ has blah" and, for all $n\geq1$, "if $n$ has blah, then so does $n+1$."

The other approach, which you seem to intend, is to start at $0$ and prove, by induction on $n$, that if $n\neq0$ then $n$ has blah. This statement is, as you observed, vacuously true for $n=0$, so all that remains is to prove, for every natural number $n$, the implication: Assuming "if $n\neq0$ then $n$ has blah" it follows that "if $n+1\neq0$ then $n+1$ has blah."

That implication can be simplified, but the simplification depends on whether $n=0$. If $n=0$, the induction hypothesis "if $n\neq0$ then $n$ has blah" is vacuously true, so it gives you no real information, and you just have to prove "if $1\neq0$ then $1$ has blah" (because in this case $n+1=1$). Since in fact $1\neq0$, you need to prove $1$ has blah. On the other hand, for non-zero $n$, the implication you need to prove simplifies to "if $n$ has blah then so does $n+1$" (because the clauses $n\neq0$ and $n+1\neq0$ are both true in this case).

Collecting all this information, what the second approach requires you to do is to prove $1$ has blah (to cover the case $n=0$) and to prove, for all non-zero $n$, that if $n$ has blah then so does $n+1$. That's exactly what was required in the first approach, where the induction begins at $1$.

Conclusion: The two approaches look different at first, but, once you analyze and simplify the second approach, it's exactly equivalent to the first.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ but the axiom in PA does not says anything about this issue, so how can a mathematician who is introduced to PA know this ? $\endgroup$ – onurcanbektas Sep 20 '17 at 5:32
  • $\begingroup$ what I mean is that, the axiom is quite clear that if the theorem is true for $0$, and it satisfies the condition $ COND(n) \Rightarrow COND(n+1)$, then every natural numbers satisfies the given condition, so it does not "care" whether $0$ is in consideration of the theorem. $\endgroup$ – onurcanbektas Sep 20 '17 at 5:35
  • $\begingroup$ "How can a mathematician whois introduced to PA know this?" One way is by analyzing how the situation simplifies when the statement being proved has the special form "if $n\neq0$ then blah," in other words, essentially by seeing what I wrote in my answer. Another way (if one doen't need to formalize the proof in PA) is to realize that many variations of the induction principle (e.g., starting at $1$ instead of $0$) are just as obviously true as the version in PA's induction axiom. $\endgroup$ – Andreas Blass Sep 20 '17 at 14:24
  • $\begingroup$ Short introduction to this nice answer. Because your induction hypothesis is about non-zero natural numbers and you want to start at $0$, the argument going from $0$ to $0+1=1$ is pretty likely to need a special argument. It's that special argument that fails. $\endgroup$ – Ethan Bolker Sep 28 '17 at 14:13
  • 1
    $\begingroup$ The axiom talks about all $n$. Whether all those cases (for all $n$) can be handled by a single argument or whether some cases need a different argument than others is irrelevant to the axiom. It depends on the specific statement that you're trying to prove. The axiom gives you the general principle; the specific applications of the principle may or may not require treating some cases separately. $\endgroup$ – Andreas Blass Sep 28 '17 at 14:38

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.