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).
Answer
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.
No comments:
Post a Comment