# Proof by Contrapositive

• May 13th 2009, 03:15 PM
utopiaNow
Proof by Contrapositive
Let $\displaystyle S = \{a, b, c, d,\}$ be a set of four distinct integers. Prove that if either (1) for each $\displaystyle x \in S$, the integer $\displaystyle x$ and the sum of any 2 of the remaining 3 integers of S are of the same parity, or (2) for each $\displaystyle x \in S$, the integer $\displaystyle x$ and the sum of any 2 of the remaining 3 integers of S are of different parity, then every pair of integers S are of the same parity.

Here is my attempt at proof by Contrapositive:
Let P: for each $\displaystyle x \in S$, the integer $\displaystyle x$ and the sum of any 2 of the remaining 3 integers of S are of the same parity.

Q: for each $\displaystyle x \in S$, the integer $\displaystyle x$ and the sum of any 2 of the remaining 3 integers of S are of different parity.

R: every pair of integers S are of the same parity.

In logic symbols: $\displaystyle P \vee Q \Rightarrow R$

Contrapositive: $\displaystyle \sim R \Rightarrow\ \sim P\ \wedge \sim Q$

So assume $\displaystyle \sim R$: there exists a pair of integers of S of different parity. And show that $\displaystyle \sim P\ \wedge \sim Q$ follows.

$\displaystyle \sim P$: there exists $\displaystyle x \in S$, such that the integer $\displaystyle x$ and the sum of any 2 of the remaining 3 integers of S are of the different parity.

$\displaystyle \sim Q$: there exists $\displaystyle x \in S$, such that the integer $\displaystyle x$ and the sum of any 2 of the remaining 3 integers of S are of the same parity.

Without loss of generality, let a and b be the pair of integers with different parity and without loss of generality let a be even and b be odd. Then $\displaystyle a = 2k$ for some $\displaystyle k \in \mathbb{Z}$ and $\displaystyle b = 2m + 1$ for some $\displaystyle m \in \mathbb{Z}$.

Case 1: Both remaining c and d are even. Then $\displaystyle c = 2l$ for some $\displaystyle l \in \mathbb{Z}$ and $\displaystyle d = 2z$ for some $\displaystyle z \in \mathbb{Z}$.
For $\displaystyle b = 2m + 1$, the sum of any 2 other integers will be of opposite parity because they are all even. So $\displaystyle \sim P$ is satisfied.

Here is where I'm stuck, to show $\displaystyle \sim Q$, I need an integer such that, the sum of any 2 of the remaining 3 integers have the same parity. But I can't have that because if I choose one of the even numbers, then I eventually have to select an odd number to be in the sum of the 2 of the remaining 3.

Case 2: Both remaining c and d are odd.Then $\displaystyle c = 2l + 1$ for some $\displaystyle l \in \mathbb{Z}$ and $\displaystyle d = 2z + 1$ for some $\displaystyle z \in \mathbb{Z}$.

Same problem as case 1 except reversed. I can show $\displaystyle \sim Q$ because for $\displaystyle a = 2k$, the 3 remaining are all odd numbers, so adding any 2 of those 3 will give an even number. So they have the same parity.

But how do I show $\displaystyle \sim P$ because if I choose an odd number, adding an odd number with an even number will still give an odd number, so the sum of those 2 will end up having the same parity again.

Case 3: c and d are of different parity. Without loss of generality let c be even and d be odd. Then $\displaystyle c = 2l$ for some $\displaystyle l \in \mathbb{Z}$ and $\displaystyle d = 2z + 1$ for some $\displaystyle z \in \mathbb{Z}$.
Case 3 I can't show either.

I don't understand what I'm doing wrong. Any suggestions would be appreciated.
• May 13th 2009, 10:31 PM
Hello utopiaNow

It's your proposition $\displaystyle \sim Q$ that's wrong. You said:
Quote:

Q: for each $\displaystyle x \in S$, the integer $\displaystyle x$ and the sum of any 2 of the remaining 3 integers of S are of different parity.
and
Quote:

$\displaystyle \sim Q$: there exists $\displaystyle x \in S$, such that the integer $\displaystyle x$ and the sum of any 2 of the remaining 3 integers of S are of the same parity.
But you don't need the word
any. You need simply show that $\displaystyle \exists x, y, z \in S$, such that $\displaystyle x$ and $\displaystyle y+z$ are the same parity.