Using disjunction prove that for all integers $m$ and $n$ if $mn$ is even then $m$ is even or $n$ is even

Question

As the title says:

Using disjunction prove that for all integers $m$ and $n$ if $mn$ is even then $m$ is even or $n$ is even.

From my understanding I can either choose not $P$ and prove $Q$ or not $Q$ and prove $P$.

So choosing either $m$ or $n$ as my $P$ or $Q$, I could prove using the definition of even and odd:

$mn$ = $(2k+1)(2i)$ where $m$ is not $P$?

Is this the correct approach?

Answer 1

"If $mn$ is even, then $m$ is even or $n$ is even" is equivalent to the contrapositive:

"if not ($m$ is even or $n$ is even), then not ($mn$ is even)."

This is logically equivalent to the following:

"if $m$ is not even and $n$ is not even, then $mn$ is not even,"

i.e., the product of two odd numbers is odd, which is true because

$(2 \times u+1)(2 \times v+1) = 2 \times (2\times u\times v+u+v) + 1$ for integers $u$ and $v$.

Answer 2

You seem to be confusing yourself as to what $P$ and $Q$ might represent in this case.

Let $m$ and $n$ be integers. Let $P$ be the statement "$mn$ is even". Let $Q$ be the statement "$m$ is even or $n$ is even."

Proving $Q\implies P$ is trivial. Suppose without loss of generality that $m$ is even. Then we have some integer $k$ such that $m=2k$ and therefore $mn = (2k)n = 2(kn)$ is even as well. The problem doesn't actually ask us to prove this, but since it is true anyways it might as well be done so you can see more examples.

Now, proving that $P\implies Q$ is easiest to do by contraposition rather than directly. That is to say, we instead prove that $\neg Q\implies \neg P$. So, suppose that neither $m$ nor $n$ is even. That is to say, both $m$ and $n$ are odd. Then there exist some integers $k$ and $\ell$ such that $m=2k+1$ and $n=2\ell + 1$. It follows then that $mn = \dots$

$mn = (2k+1)(2\ell+1) = 4k\ell + 2k + 2\ell + 1 = 2(2k\ell + k + \ell) + 1$ is odd.

Of course, it could also have been done directly if you know enough about prime numbers and Euclid's lemma. Suppose that $mn$ is even. Then $2\mid mn$. It follows by Euclid's lemma that $2\mid m$ or $2\mid n$. Hence $m$ is even or $n$ is even. Given the nature of your question however, I expect that these properties have not yet been proven for you yet and so likely are not yet valid for you to use.

Answer 3

I am not sure what you mean by 'using disjunction prove' ... I see that there is a disjunction involved here, yes, but 'disjunction' is not a proof technique.

More importantly, you cannot treat $m$ and $n$, which are numbers as $P$ and $Q$, which are claims

What you can do, is to define $P$ as the claim that "$m$ is even", and $Q$ as "$n$ is even"

Now, since you have to prove that $P \lor Q$, which is equivalent to both $\neg P \rightarrow Q$ and $\neg Q \rightarrow P$, you do indeed have a choice to either show that $Q$ is true if you assume that $P$ is false, or vice versa.

Now, I see that you are going for the assume $\neg P$ route, i.e. assume that $m$ is not even, and thus odd. Ok, that's fine, but you now have to prove that $n$ is even ... rather than just assuming that, which is what you do. That is, you can assume that $m=2k+1$ for some whole number $k$, but you need to show that $n=2i$. And for that, you will need the fact that $mn$ is even, i.e. that $mn=2j$.

To sum up: you have that $m=2k+1$, and that $mn=2j$. Now you need to show that $n=2i$ for some whole number $i$. To do this, I would show that if $n$ is not even, you obtain a contradiction.