0
$\begingroup$

The proof provided has a "fundamental error" in it, but I can't figure out what the error is.

Statement: For all non-negative integers $n$, $n$ is even.

Proof: Let $P(n)$ be the open sentence: $n$ is even.

Base Case: We show that $P(0)$ is true. Since $0=2(0)$, then 0 is even and the statement is true for $n=0$

Inductive Hypothesis: We assume the $P(i)$ is true for $0\leq i\leq k$. That is, $i$ is even for all $i$ in the range $0 \leq i \leq k$ for some $k \in \mathbb Z$ for $k \geq 0$.

Inductive Conclusion: We show that $P(k+1)$ is true. Conside $k+1$. Since $k+1 = k-1+2$ and since $0 \leq k-1 \leq k$, the by the inductive hypothesis, $k-1$ is even and 2 is even. The sum of two even numbers is even, and thus $k+1$ is even as required.

Obviously this is not true, and I have an idea as to the error, but I'm not 100% sure. I think it has something to do with the fact that they are using the strong induction method in the hypothesis, but have only provided 1 base case. Other than that, I can't see anything wrong with the actual proof method (but the proof is obviously wrong).

$\endgroup$
  • $\begingroup$ The error here is that you are assuming that $P(i)$ is true for all $0 \leq i \leq k$, and by the inductive step $k+1$ you are using that it is true not 'only' for $k$, which is the previous one, but for $k-1$, which is $2$ steps below. Hence, if you actually wanted to prove that this is true for all $k$, you should include in your base case $k=1$, which is obviously not true. $\endgroup$ – Klaramun Oct 11 '17 at 7:03
  • $\begingroup$ To show $P(1)=P(0+1)$ we write $1=-1+2.$ But we have not shown that $-1$ is even. Indeed, it isn't. Here is where the proof fails. $\endgroup$ – mfl Oct 11 '17 at 7:03
  • $\begingroup$ The Induction Step proof is wrong: we have that $P(0)$ holds but clearly $P(1)$ does not. Thus, it is not true that $P(k) \to P(k+1)$ holds for every $k$. $\endgroup$ – Mauro ALLEGRANZA Oct 11 '17 at 7:03
  • $\begingroup$ For $k=0$ the "calculation" based on $k-1$ will fail, because $k-1=-1$. $\endgroup$ – Mauro ALLEGRANZA Oct 11 '17 at 7:05
1
$\begingroup$

Let us rewrite the inductive step instantiated for $k=0$:

Inductive Conclusion: We show that $P(1)$ is true. Conside $1$. Since $1 = -1+2$ and since $0 \leq -1 \leq 0$, the by the inductive hypothesis, $-1$ is even and 2 is even. The sum of two even numbers is even, and thus $1$ is even as required.

$\endgroup$
  • $\begingroup$ What do you mean by $0\le -1\le 0?$ $\endgroup$ – mfl Oct 11 '17 at 11:08
  • $\begingroup$ @mfl: I don't mean anything, I just made a formal substitution. Are you aware of the goal ? $\endgroup$ – Yves Daoust Oct 11 '17 at 11:58
1
$\begingroup$

The problem is going from 0 to 1. See if you can figure out why.

$\endgroup$

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.