Course: Foundations of Higher Mathematics
Let x and y be integers. Prove that if x*y is odd, then x and y are odd.
I assume that x and y are odd, i.e. and .
Then,
=
=
= , for some integer c
There's only one case for x and y to be odd, so is another case needed?
Yes. The negation of the conclusion "x is odd and y are odd" is "x is even or y is even". This negation is assumed in a proof by contradiction. When you assume a disjunction (A or B) and use it to prove some C, you do it by cases, i.e., you prove that A implies C and B implies C.
The answer in post #1 is not correct. You are not trying to prove that if and are odd, then their product is odd. You are trying to prove that if is odd, then both and are odd. So, if you assume that and are odd, you will always get that and are odd because that was your assumption in the first place. Instead, assume only that the product is odd. A logically equivalent statement to the one you are trying to prove would be "If x is even or y is even, then x*y is even." This is called the contrapositive, and a conditional statement is logically equivalent with its contrapositive. So, if you prove that statement, you also prove the original statement. Assume (without loss of generality) that is even. Then for some integer . Hence is even. This proves the contrapositive, and in so doing, also proves the initial statement.
That's weird, because we've been doing things in class that way for a while. But I could be wrong. Take a look at this proof. The professor did it in class.
Let a, b, and c be integers. Prove: (a|b) ^ (b|c) => (a|c)
Assume that ^ , i.e. and , for any integer x,y
Then,
=
=
= , for some integer z
Therefore, , for some integer z, so
I am not great with logic, so please forgive me if my comment is obvious. I am not sure that the contrapositive is fully constructed here. My thought is that, yes, you can show that if the product of two numbers is even then at least one of the original numbers also must be even. But I don't feel that the possibility of one of the numbers being even and one odd (from the original problem statement) is addressed here? Or am I mistaken?
-Dan
The question about your OP is that you are proving the converse of what you are asked to prove.
If is odd, then both are odd. Not the other way around.
Personally, I would do this by contradiction. Suppose is odd.
Then is any even number times any integer is even. SO?
As for your instructor's proof, I hope he/she said and , for some integers x & y.
Otherwise, it is the way to do it.
is the equivalent of saying, "If a divides b and b divides c, then a divides c."
Your professor assumed what came after the "if" and proved what came after the "then". In post #1, you assume what comes after the "then" and prove what comes after the "if". As Plato said, you proved the converse statement which is not logically equivalent to the original statement.
You are correct, I did not explain how the statement I wrote is logically equivalent to the contrapositive. The contrapositive would be, "If not (x and y are odd), then not (x*y is odd)." By DeMorgan's Laws, the negation of a conjunction of two expressions is logically equivalent to the disjunction of the negation of each expression . So, the statement is logically equivalent to "If (x is not odd) or (y is not odd), then x*y is not odd." Since not odd is equivalent to even, "If x is even or y is even, then x*y is even."
However, the statement you mention, "If the product of two numbers is even, then at least one of the original numbers also must be even," is actually an inverse statement, not a contrapositive one. In general, the truth value of the inverse statement does not in any way depend on the truth value of the original statement.
This is great. Thank you emakarov, SlipEternal, topsquark, and Plato!
I think what you all are saying is that I should prove that the consequent is true. Then, no matter what the truth value of the antecedent is, the implication will be true. I think I see it now. Don't assume the consequent is true, but prove that it is. I can't think of a way to prove that x and y are odd, so by finding the contrapositive I can prove that x*y is odd and would give me 2-3 cases. Case 1 being x and y are odd. Case 2 being that x is odd and y is even (and vice-versa for case 3, if it's needed).
Proof by contradiction was mentioned twice, but I don't know how to prove it that way. I can't find anything about the process in my textbook.
For proof by contradiction: When is a conditional statement false? It is when the antecedent is true, but the consequent is false. Assume that the antecedent is true and the consequent is false and arrive at a logical contradiction. Proof by contradiction is not necessary in this case because proof by exhaustion is just as easy.
Case 1: x is odd and y is odd (you already showed that x*y is odd)
Case 2: x is even and y is odd (show that x*y is even)
Case 3: x is odd and y is even (show that x*y is even)
Case 4: x is even and y is even (show that x*y is even)
Assume that x*y is odd. Case 1 is the only possible conclusion because you showed that cases 2, 3, and 4 cannot be true if x*y is odd.
It's taking a little time, but I'm getting this. I really appreciate the help.
Original statement: If x*y is odd, then x and y is odd.
I didn't understand how Plato got "If x is even OR y is even, then x*y is even" as the contrapositive, but now I see it. You also negate the "and" to get "or".