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.
On
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:
In this case both proofs would look almost the same, so they are equally easy.
Contraposition: prove that if both $x$ and $y$ are even, then so is $x+y$ (your restatement is incorrect: the negation of A or B is not A and not B).
Contradiction: [assuming that $x+y$ is odd] prove that if both $x$ and $y$ are even, then so is $x+y$ (and therefore get a contradiction with your standing assumption).
In other cases there is a bigger difference between those methods of proof, because the contradiction that you get may not be directly the negation of your standing hypothesis. For example, you could get something like $1<0$, etc.