1
$\begingroup$

In this proof I am asked to use contradiction and have a few questions about it.

Example: Prove that for all integers m and n if mn is odd, then m is odd and n is odd. (Use contradiction.)

Here's my work:

Proof by Contradiction:

Suppose not. That is, suppose that there exists integers m and n such that mn is odd and m is not odd or n is not odd.

Since either m is not odd or n is not odd,

let m be an odd integer such that m = 2k+1 for some integer k (by def of odd integer)

and let n be an even integer such that n = 2g for some integer g (by def of even integer)

mn = (2k+1)(2k) (substitution)

= 4gk + 2g (distributive property of multiplication)

= 2(2gk + g) (factoring out a 2)

Let r = (2gk + g) where are is an integer by definition of integer because it is comprised of the sums and products of integers.

mn = 2r (substituting r for (2gk + g)

Thus mn is even by definition of even integer which contradicts our supposition that mn is odd.

Therefore, the given proposition "for all integers m and n if mn is odd, then m is odd and n is odd" is true.


My question is, is my work enough to show proof by contradiction or do I need to include division into cases? i.e., I proved contradiction for even m and odd n, do I also need to prove contradiction for odd m and even n?

Also, when I negated the statement and got: "suppose that there exists integers m and n such that mn is odd and m is not odd or n is not odd" which is of the form p and (~q or ~r), does this mean ~q or ~r OR does it mean ~q or ~r or both (~q and ~r). Basically in this negation, can both m and n be not odd? Or does it have to be one or the other and not both?

Going forward, will there EVER be a situation where I have to do a proof by contradiction and there will be division into cases, or can I just show one example where there is a contradiction and that is enough. That is what my textbook implies, just want to make sure...

Thank you!

$\endgroup$
2
  • $\begingroup$ You did not consider the case in which neither $m$ nor $n$ was odd. Easy to rule out, of course, but no easier than the cases you do consider. $\endgroup$
    – lulu
    Commented Nov 8, 2022 at 21:45
  • $\begingroup$ Here's a MathJax tutorial :) $\endgroup$
    – Shaun
    Commented Nov 8, 2022 at 22:28

1 Answer 1

1
$\begingroup$

Your statement you want to proof is from a formal point of view: $p \Rightarrow (a \land b)$. The stamenent you want to contradict is then: $p \Rightarrow \neg (a \land b) \iff p \Rightarrow (\neg a \lor \neg b)$.

Basically in this negation, can both m and n be not odd?

Yes, either a or b is wrong or both can be wrong (by definition of "$\lor$"). That also means you should prove your statement with even n and even m.

do I also need to prove contradiction for odd m and even n?

No, you can just say it's analogous for even n and odd m. But that just works here because its very easy.

Going forward, will there EVER be a situation where I have to do a proof by contradiction and there will be division into cases, or can I just show one example where there is a contradiction and that is enough.

For example with ORS you need consider at least 3 cases. In generel there can be (direct, induction, whatever) proofs where you need to consider multiple cases.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .