Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The way I understand complete induction, as applied to the naturals at least, the inductive step consists of assuming that a given proposition $p_i$ is true for $1 \le i \le n$, and from this deduce the truth of of $p_{n+1}$. However, I had thought that one always needed to check the base case ($i=1$). But reading the articles on vacuous truth and transfinite induction, I am now left wandering if this is really the case, considering that the truth of $p_1$ might follow (vacuously) from the fact that there is no smaller element. So my two questions are:

  • When proving some statement with complete induction, is it correct to assume the truth of $p_1$ as a vacuous truth? Could anyone provide an example? (somewhat to my astonishment I was unable to find one...)

  • If $p_1$ is vacuously true for complete induction, then is that also the case for (simple) induction? I am inclined to believe so, because the truth of $p_1$ would follow vacuously from the truth of (the set containing) the previous smaller element, which is the empty set. However in all I've read of simple induction, this never comes up; instead one is always told to check the base case.

Thank you in advance for your help in clarifying this!

share|improve this question
1  
See my answer in math.stackexchange.com/questions/663264/… –  Tom Collinge Jun 28 at 12:59
    
@TomCollinge Yep, that answers precisely my doubt. Thanks! (too bad I can't mark a comment as the accepted answer...). –  wmnorth Jun 28 at 21:55

2 Answers 2

"Theorem": for every positive integer $n$, we have $n<n-1$.

"Proof": By "induction". Suppose that $k<k-1$. Adding one to both sides, we get $$k+1 <(k-1)+1=(k+1)-1.$$ By the Induction Principle, $n<n-1$ for all $n$. QED.

So there you have a "proof" that $1 <2$.

"Vacuosly True" refers to a property of the empty set. The base case you want to omit is never about the empty set.

share|improve this answer

See the answer to this post.

Mathematical induction consists into applying the following "method of proof", based on axiom schema of induction :

if $P(0)$ and $\forall k [P(k) \implies P(k+1)]$, then $\forall n P(n)$.

In words, I have to prove that : property $P$ hold for number $0$ and that : if property $P$ holds for a number $k$ whatever, then it holds also for its successor $k+1$, in order to be able to conclude that : $P$ holds for all natural numbers.

Strong induction is the equivalent form :

if $\forall i [(i < k \implies P(i)) \implies P(k)]$, then $\forall n P(n)$.

In words, I've to prove that : if $P(i)$ holds for all $i < k$, then $P(k)$ holds, in order to be able to conclude that : $P$ holds for all natural numbers.


Comment

I'm starting from $0$ but we can start from $1$; it depends on the definition of natural number.

We can start from a number $k > 0$, if we want to prove a statement not for all natural numbers but only for all numbers greater than or equal to $k$. In this case we have :

  • to prove that the statement holds when $n = k$;

  • to prove that if the statement holds for $n = m > k$ then the same statement also holds for $n = m$.

In every case, the proof will not work if $P$ does not hold for the basis case : $P(0)$ (or $P(k)$).

For math induction, we have to prove it as first step (the basis case), while for strong induction it is included into the proof of $\forall i [(i < k \implies P(i)) \implies P(k)]$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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