Prove the following claim, using either proof by contradiction or contrapositive:
For $x, y \in \mathbb Z$, if $x + y$ is odd then either $x$ or $y$ is odd.
Would it be easier to prove by contradiction or contrapositive? Do both these statements below look correct?
Contrapositive: (restate): If either x or y is even, then $x + y$ is even.
Contradiction: (restate): If $x + y$ is odd then either x or y is even.
Best Answer
For $x,y \in \mathbb{Z}$,
Required to proof: $$ (x+y)\text{ odd} \implies (x \text{ odd }) \vee (y \text{ odd}) $$ Contrapositive: Prove that the following statement is true. $$ \neg ((x \text{ odd }) \vee (y \text{ odd})) \implies \neg ((x+y)\text{ odd}) $$ $$ \equiv (x \text{ even }) \wedge (y \text{ even}) \implies (x+y)\text{ even} $$ Contradiction: Prove that the following statement is a contradiction. $$ (x+y)\text{ odd} \implies \neg((x \text{ odd }) \vee (y \text{ odd})) $$ $$ \equiv (x+y)\text{ odd} \implies (x \text{ even}) \wedge (y \text{ even}) $$ Contrapositive seems to be easier in this case.
Eg.
Since both $x$ and $y$ are even integers, let $x = 2n$ and $y = 2m$, where $n,m \in \mathbb{Z} $.
Therefore, $x+y= 2n + 2m = 2(n+m)$ is also even.
(*Please note that, when we push $\neg$ (negation) into the brackets, according to De Morgan's law, we negate the propositions and conjunction/disjunction operators.
From Wikiepia: