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.

Let $P(n)$ be any property pertaining to a natural number $n$. We will look this example: $$P(n) := (n = 0) \vee (n \leq -1) $$

Now, I will prove this and I'm asking that can you please show me where I'm making mistake.

Proof: $P(0)$ is obviously correct. Let's assume $n \leq -1$ and try to prove $n+1 \leq -1$. Assume that we now $$\forall a,b \in \mathbb{N} ,\ a<b \to a+1 \leq b$$ Also, we know that $n \neq -1$. So, if $n \leq -1$, that means $n < -1$ and that means $n+1 \leq -1$ and we are done.

What is wrong? Thanks for any help.

share|improve this question
2  
You can't just assume $n \leqslant -1$, you must assume $(n \leqslant -1) \vee (n = 0)$. –  Daniel Fischer Aug 21 '13 at 16:23
    
@DanielFischer: I get it, thanks. Could you please write this as an answer so I can accept it? –  miskin Aug 21 '13 at 16:27
4  
The wrong step is rather when you assert that "we (k)now that $n\ne-1$". We do not. –  Did Aug 21 '13 at 16:35
    
@Did: Why don't we? –  miskin Aug 21 '13 at 17:09
    
Because we assumed at the beginning of the proof that $n\leqslant-1$, not that $n\lt-1$. –  Did Aug 21 '13 at 17:11
show 2 more comments

1 Answer

up vote 3 down vote accepted

When you start the induction, you prove (well, sort of) $(0 = 0) \vee (0 \leqslant -1)$.

But in the induction step, you assume something stronger than what was proved in the base case, namely $n \leqslant -1$. So the induction step (which is correct when the reason for $n \neq -1$ is given; that $n \in \mathbb{N}$, but $-1 \notin \mathbb{N}$) is not connected to the base case.

To connect the induction step to the base case, you must assume what you really have proved, namely that $(n = 0) \vee (n \leqslant -1)$. But from that assumption, you cannot infer that $(n+1 = 0) \vee (n+1 \leqslant -1)$, since if the first part of the conjunction is true - as it is for the base case - then you obtain $n+1 = 0+1 = 1 > 0 > -1$.

share|improve this answer
add comment

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.