# Proof by Contrapositive

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

Q: for each $x \in S$, the integer $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: $P \vee Q \Rightarrow R$

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

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

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

$\sim Q$: there exists $x \in S$, such that the integer $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 $a = 2k$ for some $k \in \mathbb{Z}$ and $b = 2m + 1$ for some $m \in \mathbb{Z}$.

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

Here is where I'm stuck, to show $\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 $c = 2l + 1$ for some $l \in \mathbb{Z}$ and $d = 2z + 1$ for some $z \in \mathbb{Z}$.

Same problem as case 1 except reversed. I can show $\sim Q$ because for $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 $\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 $c = 2l$ for some $l \in \mathbb{Z}$ and $d = 2z + 1$ for some $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 $\sim Q$ that's wrong. You said:
Quote:

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

$\sim Q$: there exists $x \in S$, such that the integer $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 $\exists x, y, z \in S$, such that $x$ and $y+z$ are the same parity.