0
$\begingroup$

Prove $a^2$ is even $\implies$ $a$ is even. It was proven via contradiction by my friend.

Here is the proof in question, which uses proof by contradiction

Assume towards a contradiction that $a$ is odd. Let $a = 2k+1$, then $a^2 = 4k^2 + 4k + 1 = 2(2k^2+2k)+1$ Therefore $a^2$ is odd. Contradiction.

To me, this proof in question seems incorrect because it shows that if $a$ is odd then $a^2$ is odd. We have shown that the converse of what we want to contradict is a contradiction. I feel like this proof by contradiction is not mathematically correct or vigorous enough, and for it to be correct we would have to start from $a^2$ being even, working our way down to $a$ being odd, and then finding a contradiction.

Am I correct? Or am I just confused about something?

$\endgroup$
  • $\begingroup$ He proved the contrapositive of the original statement (which is equivalent) but did not prove the statement by contradiction :) (the converse would be: if $a$ is even, then $a^2$ is even) $\endgroup$ – Scott H. Sep 15 '16 at 1:35
  • 1
    $\begingroup$ It's also important to note that $a$ is exactly one of odd or even. $\endgroup$ – Fimpellizieri Sep 15 '16 at 1:36
  • $\begingroup$ Logically, "$a^2$ is even implies $a$ is even" is equivalent to "$a^2$ is not even or $a$ is even" so a proof by contradiction would begin with "$a^2$ is even" and "$a$ is not even" as assumptions and arrive at a known false conclusion. $\endgroup$ – Guest Sep 15 '16 at 1:44
  • $\begingroup$ $(2k+1)^2 = 4k^2 + 4k + 1$ $\endgroup$ – Alex Ortiz Sep 15 '16 at 1:44
3
$\begingroup$

Your friend has done the contrapositive. He has not proved it by contradiction exactly. The contrapositive of a statement is: if the conclusion is false, then the premise is false. You friend assumed the conclusion did not apply, namely that $a^2$ is not even (which means it's odd), and went on to prove that $a$ is not even (which means it's odd).

Contradiction proceeds the following way: Assume that the conclusion is false but the premise is true. Then, come up with a false statement logically (a false statement could be like $0 = 1$ or $3$ divides $2$). Hence, we must assume both that $a^2$ is even and $a$ is odd, and come up with a false statement.

A proof by contradiction would say : Let $a^2$ be even and $a$ be odd. We will derive a contradiction.

Note that $a^2-a$ is an odd number, since it is an odd number subtracted from an even number. However, $a^2-a =a(a-1)$. Since $a$ and $a-1$ are consecutive numbers, one of them is an even number. Hence, since $a^2-a$ has an even number as a factor, it is also an even number. But then $a^2-a$ is both even and odd, which is not possible. Hence, the original statement "Let $a^2$ be even and $a$ be odd", must be false. Hence, if $a^2$ is even, $a$ too must be even.

$\endgroup$
  • $\begingroup$ "if A then B" So for contradiction we assume that A is true and B is false and try to find some logical contradiction. My question is this: Do we always have to start our logical sequence with A, and then work our way to B to find a contradiction? Or can we start with B being false, and then start working our way back to A to find a contradiction? But by starting with B being false, aren't we using the logic "if not B then A" instead of "if A then not B" ? $\endgroup$ – Jason Sep 15 '16 at 1:53
  • $\begingroup$ @Jason The statement of contradiction says that $if (A $ and $not B)$, then false. In our starting itself, we have that both $A$ and not $B$ are true. In $if not B then A$, you are starting with not B and proving A, but here, both are already given to be true, so you have to work with both being true. Note : I did not start my logical sequence with $A$. The first statement I made was "$a^2-a$ is odd". In this statement, I used both A and not B, where $A =$ "a^2 is even" and $B=$ "a is even", which means $not B = $ "a is odd". $\endgroup$ – астон вілла олоф мэллбэрг Sep 15 '16 at 2:29

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.