Thursday, November 15, 2018

induction - Find the fundamental error in the proof




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

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...