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 .
= , for some integer c
There's only one case for x and y to be odd, so is another case needed?
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.
Let a, b, and c be integers. Prove: (a|b) ^ (b|c) => (a|c)
Assume that ^ , i.e. and , for any integer x,y
= , for some integer z
Therefore, , for some integer z, so
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.
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.
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".