# What is wrong with this induction?

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.

• 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? – user87853 Aug 21 '13 at 16:27
• 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? – user87853 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

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