4
$\begingroup$

I am confused by the following exercise in Velleman's How To Prove It:

'Suppose $m$ and $n$ are integers. If $mn$ is even, then either $m$ is even or $n$ is even.

Proof: Suppose $mn$ is even. Then we can choose an integer $k$ such that $mn=2k$. If $m$ is even then there is nothing more to prove, so suppose $m$ is odd. Then $m=2j+1$ for some integer $j$. Substituting this into the equation $mn=2k$, we get $(2j+1)n=2k$, so $2jn+n=2k$, and therefore $n=2k-2jn=2(k-jn)$. To prove $n$ is even it suffices to find an integer $c$ such that $n=2c$, from the above $c=k-jn$ works. Since $k-jn$ is an integer, it follows that $n$ is even.'

There are two things I don't understand:

1) How could $n=2(k-jn)$ be legitimate? Isn't that circular? Surely if he is to solve for n all n must be on one side of the equation?

2) I am not quite sure what he did. It seems that he split them into two cases to exhaust the possibilities of m. If one can prove exhaustively that the conclusion necessarily happens, the proof is correct. But in terms of the entire equation that doesn't seem exhaustive to me, i.e. what about $n$?

Also, I understand that by existential instantiation the definition of an even number $$\exists x(m=2x) $$ leads to m=2k, and the same goes with m=2j+1.But why is it suffice to find an integer c such that n=2c? Is he going to use existential generalization to make n=2c into $$ \exists x(n=2x) $$ i.e. the definition of even number, to complete a direct proof? But this is not explicit in the proof.

I am trying to self-study this and my maths is, needless to say, dire. So I really appreciate any help on this, thank you so much!

$\endgroup$
  • 2
    $\begingroup$ We are not trying to "solve for n".That is we are not trying to find the value of n.We are trying to PROVE that n is even.Once we have found that 2jn+n=2k , we know that n=2(k-nj). And therefore we know that n is twice an integer. $\endgroup$ – DanielWainfleet Jan 20 '16 at 16:10
5
$\begingroup$

The assumption of the exercise is that $m,n$ are given to us as integers, and that $mn$ is an even integer and therefore $mn=2k$ where $k$ is an integer.

The proof goes by cases. The case that $m$ is even has been handled, and now we are in the opposite case where $m$ is odd, so $m=2j+1$ where $j$ is given to us as an integer. (Note: proofs in different cases are independent of each other; the proof in one of the cases does not have to be "exhaustive", i.e. it does not have to apply to the other case).

The equation $n=2(k-jn)$ has been derived from those assumptions using the laws of algebra, it is perfectly valid, and $j,k,n$ are all integers, by assumption.

Perhaps you are confused because it looks like this equation is being used to "solve for $n$", but that's not what is happening in this proof. The quantity $n$ is not being defined by this equation $n=2(k-jn)$. Instead, $n$ has already been given to us as an integer, at the very beginning of the proof.

All that's happening with the equation $n=2(k-jn)$ is that $n$ is being expressed as a product of $2$ times another integer, that integer being $k-jn$. Since $2$ times any integer is an even integer, we may conclude (in the case that $m$ is odd) that $n$ is an even integer.

Let me attempt to emphasize the point by an extreme example. If you did not already believe that $4$ is an even integer, I could perhaps convince you by writing the equation $$4 = 2(34 - 8 \cdot 4) $$ which expresses $4$ as a product of $2$ times another integer, that integer being $34 - 8 \cdot 4$. I do not ask that you do the arithmetic to discover exactly which integer $34 - 8 \cdot 4$ happens to equal, instead I ask you to understand that the result of multiplying two integers and subtracting them from another integer is always an integer.

$\endgroup$
  • $\begingroup$ Thank you so much! I now understand what's happening to n. But I am still not sure about the approach, namely why he firstly assumed m is even, and then m is odd. To me the conclusion seems to have the logical form of 'If P, then Q or R', so either proving Q (m is even) or R (n is even) would suffice. He certainly did prove R, but why did he assume m is odd (more importantly, is this justified?)? Also, if his goal was R all along, why go to the trouble of assuming Q is true? If you have assumed the conclusion then the conclusion necessarily entails. But this move doesn't seem to do anything? $\endgroup$ – Daniel Mak Jan 21 '16 at 16:09
  • 2
    $\begingroup$ You need to know about Proof By Cases. For this proof, it is known that "$m$ is even or $m$ is odd". Knowing that one may break the proof into two cases: "Case 1: Assume $m$ is even (give a proof of the desired conclusion using the Case 1 assumption). Case 2: Assume $m$ is odd (give a different proof of the desired conclusion using the Case 2 assumption)" $\endgroup$ – Lee Mosher Jan 22 '16 at 14:19
1
$\begingroup$

If $n=2c$, then $mn$ is even because of $2|mn$ , which follows from $2|n$

Easier formulated : If a product contains an even number, it is itself even.

$\endgroup$
1
$\begingroup$
  1. I admit that the proof is a bit difficult to understand, especially seeing it the first time. Basically, you've fixed an $n$ integer. So you can express $n$ as a multiple of $2$. Of course for different $n$, you'd expect different multiples. So thinking about it this way, it's actually quite expected that $n = 2 f(n)$, some function of $n$.
  2. Yes, when proving disjunction statements directly, you must split into cases, either explicitly or implicitly. The definition for an integer $n \in \mathbf{Z}$ to be even is that $\exists c \in \mathbf{Z}$ such that $n = 2c$.

It's probably easier to prove the contrapositive: if $m$ and $n$ are both odd, then $mn$ is also odd.

$m = 2k+1$, $n = 2l+1$, so $$mn = (2k+1)(2l+1) = 4kl + 2k+2l + 1 = 2(2kl+k+l)+1 $$

$\endgroup$
-1
$\begingroup$

Part of your confusion is due to the fact that Velleman is glossing over the '$m$ is even' case. The explicit proof for even '$m$' - which he is expecting you to see for yourself directly - is this:

If $m$ is even, then $m$=2$j$ for some $j$. Then $mn$ is (2$j$)$n$. By associativity, this is equal to 2($jn$). So to show $mn$ = 2$k$ for some $k$, take $k$=$jn$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.