2

I need to prove the following by contrapositive:

"$x$ and $y$ are integers, and $xy$ is even, then $x$ is even or $y$ is even"

I'm sure this question isn't very hard to solve, however my understanding of contraposition is very weak. I have only learned it recently and I do not feel like I am totally grasping the concept.

From my understanding I am almost trying to prove this by saying the opposite statement. But I feel like this is oversimplifying it.

I know that based on previous proofs an even number is in a form like $z = 2a$ an odd is the same as the even except plus 1: $x = 2a + 1$. Based on knowing this I assume I am able to use contraposition. But where do I start to use this?

Ian Murphy
  • 196
  • 13
ComputerLocus
  • 273
  • Well, I don't know what contraposition is. But it appears to me that you are doing correct. Assume both x,y to be $2a+1,2b+1$. Multiply and you must be able to see that the product is odd. The result follows. –  Feb 06 '15 at 15:57
  • I see I have an edit changing contraposition to contrapositive. Do these terms mean the same thing? I have only learned it as being called contraposition. – ComputerLocus Feb 06 '15 at 16:07

3 Answers3

5

What your are starting with is

Let $x, y$ be integers.

($xy$ is even) $\implies (x$ is even or y is even)

The contrapositive is then $\lnot(x$ is even or $y$ is even)$\implies \lnot(xy$ is even).

This means we want to prove that if $x$ is odd AND $y$ is odd, then $xy$ is odd.

Start in the standard way: Let $x = 2a +1$ and let $y = 2b +1$ where $a, b \in \mathbb Z$.

Then calculate $xy$, and represent the product as an odd integer.

amWhy
  • 209,954
  • Okay, so I would get 4ab+2a+2b+1. And the 4ab+2a+2b part is even, and plus the 1 would make it odd. So to properly conclude this prove would saying the following be sufficient: "Therefore if both x and y is odd, xy is odd. This proves by contraposition that if xy is even, that either x or y will be even as well". Is this sufficient? – ComputerLocus Feb 06 '15 at 16:05
  • 2
    Yes it is sufficient. – amWhy Feb 06 '15 at 16:08
1

To prove this, you must rewrite the statement as:

If $x$ is odd AND $y$ is odd, then xy is odd.

You can do this by letting $x = 2a + 1$ and $y = 2b + 1$, for all integers, $a,b$.

Then, try multiplying them and see what you can say about $xy$

Ian Murphy
  • 196
  • 13
  • Okay, so I would get $4ab + 2a + 2b + 1$. And the $4ab + 2a + 2b$ part is even, and plus the $1$ would make it odd. So to properly conclude this prove would saying the following be sufficient: "Therefore if both x and y is odd, xy is odd. This proves by contraposition that if xy is even, that either x or y will be even as well". Is this sufficient? – ComputerLocus Feb 06 '15 at 16:01
  • Yes it is sufficient. To prove $p\rightarrow q$ we prove its contrapositive $\lnot q \rightarrow \lnot p$. Anything that holds for an implication holds for its contrapositive, and vice-versa, as they are logically equivalent. – amWhy Feb 06 '15 at 16:07
1

There is a very important different between the converse of a statement and the contrapositive of a statement. If you have a statement $S$ that says "if $A$, then $B$" the converse/opposite of $S$ would be "if not $A$, then not $B$". As a general rule, $S$ and the converse of $S$ are not logically equivalent. The exception is that $A$ and $B$ are logically equivalent. You'll encounter this periodically in math and proofs of this nature are commonly called "if and only if" proofs. Anyway, what is equivalent to $S$ is the contrapositive of $S$. The contrapositive of $S$ is "if not $B$, then not $A$". Using logic notation, the following two statements are identical.

$$(A \implies B) \equiv (\neg B \implies \neg A)$$

In the context of what you need to prove, it might help to rephrase the sentence slightly. We can say "Let $x,y$ be integers. If $xy$ is even, then $x$ is even or $y$ is even". Pattern matching that to what is above, then $A \equiv $ "$xy$ is even" and $B \equiv $ " $x$ is even or $y$ is even." Hence the contrapositive would be:

If $\neg(x$ is even or $y$ is even$)$ then $\neg (xy$ is even$)$

$\equiv$ If $x$ is not even and $y$ is not even, then $xy$ is not even.

$\equiv$ If $x$ is odd and $y$ is odd then $xy$ is odd.

At this point you can proceed as you correctly guessed, letting $x = 2a+1$ and $y = 2b+1$ for some $a,b \in \Bbb{Z}$. You'll find that $xy = 2c+1$ for some $c \in \Bbb{Z}$.

Community
  • 1
graydad
  • 14,077
  • Hi, quick one : is it possible to say that if not A then Not B is equivalent to if A then B ? I think no but I need to ask. – Andy K Apr 19 '15 at 16:26
  • @AndyK your suspicion is correct, it is generally untrue. It is only true if $A$ and $B$ are equivalent statements. For example, "if $x$ is divisible by two then $x$ is even" is the same as saying "if $x$ is not divisible by two then $x$ is not even." – graydad Apr 19 '15 at 16:29
  • thanks @graydad. Indeed , I found this one http://www.regentsprep.org/regents/math/geometry/gp2/lcontrap.htm – Andy K Apr 19 '15 at 16:38