0

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?

JMP
  • 21,771
Jason
  • 3,563
  • 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) – Scott H. Sep 15 '16 at 01:35
  • 1
    It's also important to note that $a$ is exactly one of odd or even. – Fimpellizzeri Sep 15 '16 at 01:36
  • 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. – Guest Sep 15 '16 at 01:44
  • $(2k+1)^2 = 4k^2 + 4k + 1$ – Alex Ortiz Sep 15 '16 at 01:44

1 Answers1

4

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.

Sarvesh Ravichandran Iyer
  • 76,105
  • "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" ? – Jason Sep 15 '16 at 01:53
  • @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". – Sarvesh Ravichandran Iyer Sep 15 '16 at 02:29