Proof about parity of a set of four integers

Printable View

December 5th 2010, 07:11 AM
zg12

Proof about parity of a set of four integers

Statement to prove:

Let S={a,b,c,d} be a set of four distinct integers. Prove that if either (1) for each xES, the integer x and the sum of any two of the remaining three integers of S are of the same parity or (2) for each xES, the integer x and the sum of any two of the remaining three integers of S are of opposite parity, then every pair of integers of S are of the same parity.

I have two proofs of this statement and I want to make sure they are correct. In the first one I assume that some pair of integers of S are of different parity, and in four different cases show that neither condition (1) or condition (2) is satisfied. So proof by contrapositive.

In the second I assume that every pair of integers in S are of opposite parity. Since this is always false (right?) the contrapositive is a true statement and I'm done. So a vacuous proof of the contrapositive. I'm unsure of this one because so far I haven't seen a two proof methods combined.
December 5th 2010, 08:07 AM
tonio

Quote:

Originally Posted by zg12

Statement to prove:

Let S={a,b,c,d} be a set of four distinct integers. Prove that if either (1) for each xES, the integer x and the sum of any two of the remaining three integers of S are of the same parity or (2) for each xES, the integer x and the sum of any two of the remaining three integers of S are of opposite parity, then every pair of integers of S are of the same parity.

The last words above are a little odd for me (pun intended): to say, in this case, that "every pair of integers of

S are of the same parity" is exactly the same as saying that all the integers in S have

the same parity...unless I missed something.

Tonio

I have two proofs of this statement and I want to make sure they are correct. In the first one I assume that some pair of integers of S are of different parity, and in four different cases show that neither condition (1) or condition (2) is satisfied. So proof by contrapositive.

In the second I assume that every pair of integers in S are of opposite parity. Since this is always false (right?) the contrapositive is a true statement and I'm done. So a vacuous proof of the contrapositive. I'm unsure of this one because so far I haven't seen a two proof methods combined.

.
December 5th 2010, 08:17 AM
zg12

That's how I read it too. And I found the question and answer elsewhere and my first proof is indeed correct. And if we're reading it correctly I think that the second proof is ok too, since assuming some pair of integers are of opposite parity and all pairs of integers are of opposite parity are both negations of the statement "all pairs of integers are of the same parity."
December 5th 2010, 12:07 PM
emakarov

Quote:

some pair of integers are of opposite parity and all pairs of integers are of opposite parity are both negations of the statement "all pairs of integers are of the same parity."

No way.

Let p(x) denote the parity of x. "All pairs of integers are of the same parity" is $\forall x,y\in S.\,x\ne y\to p(x)=p(y)$ . Its negation is $\exists x,y\in S.\,x\ne y\land p(x)\ne p(y)$ , i.e., "some pair of integers are of opposite parity". The statement "all pairs of integers are of opposite parity" is $\forall x,y\in S.\,x\ne y\to p(x)\ne p(y)$ . It implies the previous statement, but then falsehood implies everything.

The following should have given you a warning bell. The conclusion of the claim you need to prove — "all the integers in S have the same parity" — is not true for all S, so it essentially uses the premise (that (1) or (2) holds). However, in your second proof you ignore this premise.
December 5th 2010, 05:26 PM
zg12

Quite right emakarow, thank you.