Where is the mistake in this proof that "If the square of a number is even, then the number is even"?

Question

The proof given in This question is incorrect (the proof will be posted at the end for convenience). However, the question seem to address the fact that the statement to be proven is not stated correctly, and not the fact the the proof is incorrect.

Stated different, what I am asking is...

What step in the following (see below) proof of "If a number $n^2$ is even, then $n$ is even" is incorrect?

(Some step must be incorrect since If I change $n^2$ to $x$ and $n$ to $\sqrt{x}$, we would have a proof saying "if you give me any even number $x$, its square root is even")

---

The proof (by contrapositive) given is as follows:

If a number $n^2$ is even, then $n$ is even. The contrapositive is that is that if $n$ is not even (odd), then $n^2$ must also be not be even (be odd).

We represent n as $n=2p+1$. $n^2=4p^2 + 4p + 1 = 2(p^2+2) + 1$. We see that $n^2$ is odd. Therefore, the original statement must be true.

---

Is the problem that, in general, the negation of "$n$ is even", but rather "$n$ is odd OR $n$ is not an integer$?

Answer 1

We need to be clear about what values $n$ is allowed to take. For example; $n^2 = 2$ is even, but $n$ is not, because $n$ is not an integer.

If $n$ is an integer and $n^2$ is even, then $n$ is even. This is a correct statement.

If $n$ is a real number, and $n^2$ is even, then $n$ is not necessarily even; $n = \sqrt{2}$ is a counterexample as mentioned above.

The flaw in the proof when $n$ is not assumed to be an integer is that if $n$ is not even, it does not necessarily follow that $n$ is odd, because $n$ may not be an integer. When $n$ is an integer, then either $n$ is divisible by $2$ (we call these 'even') or $n$ is not divisible by $2$ (we call these 'odd'). Therefore, when $n$ is not restricted to integers, the negation of the statement "$n$ is even" is not "$n$ is odd," but rather, "$n$ is not an even integer."

Answer 2

The proof you've cited is correct. It is a good proof by contrapositive. In fact, it is often the "role model" proof by contrapositive that I first introduce in a proofs course. (And let's say "integer" instead of "number" for clarity.)

Your mistake is in thinking that you can "change... $n$ to $\sqrt{x}$" and get something meaningful. After all, $\sqrt{x}$ is rarely an integer when $x$ is a natural number, so "even" and "odd" wouldn't even make sense. For example, if $x=3$, what would it mean for $\sqrt{3}$ to be "even"? It doesn't make any sense at all.

Answer 3

This is a classic example of proof by contrapositive. It is completely correct, and I'll use truth tables to show you why:

$$\begin{array}{c|c|c} P & \to & Q \\ \hline T & T & T \\ \hline T & F & F \\ \hline F & T & T \\ \hline F & T & F \end{array}$$

and, where $P'$ means not $P$:

$$\begin{array}{c|c|c} P' & \leftarrow & Q' \\ \hline F & T & F \\ \hline F & F & T \\ \hline T & T & F \\ \hline T & T & T\end{array}$$

The two middle rows match, so the tables' meanings are the same, or have the same truth value. That is to say:

"If P then Q" is the same as "If not Q, then not P".

This is what is used in the proof method.