2
$\begingroup$

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.

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

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy