Results 1 to 14 of 14
Like Tree11Thanks
  • 1 Post By emakarov
  • 1 Post By emakarov
  • 3 Post By SlipEternal
  • 1 Post By emakarov
  • 1 Post By Plato
  • 2 Post By SlipEternal
  • 2 Post By SlipEternal

Math Help - Prove that if xy is odd, then x and y are odd. Proof by cases

  1. #1
    Junior Member
    Joined
    Sep 2013
    From
    United States
    Posts
    67
    Thanks
    3

    Prove that if xy is odd, then x and y are odd. Proof by cases

    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. x=2a + 1 and y=2b + 1.

    Then, xy = (2a + 1)(2b + 1)

    = 4ab + 2a + 2b + 1

    = 2(2ab + a + b) +1

    = 2c + 1, for some integer c

    There's only one case for x and y to be odd, so is another case needed?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773

    Re: Prove that if xy is odd, then x and y are odd. Proof by cases

    Quote Originally Posted by MadSoulz View Post
    There's only one case for x and y to be odd, so is another case needed?
    No, this is fine. I would add that at this level of detail, you should note that a and b are integer.

    You could also prove this by contradiction. Then you need to consider two cases: a is even and b is even (each case includes the possibility that both are even).
    Thanks from MadSoulz
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Sep 2013
    From
    United States
    Posts
    67
    Thanks
    3

    Re: Prove that if xy is odd, then x and y are odd. Proof by cases

    Quote Originally Posted by emakarov View Post
    You could also prove this by contradiction. Then you need to consider two cases: a is even and b is even (each case includes the possibility that both are even).
    I want to give that a try. I'm assuming that you mean that case 1 would be that a is even and case 2 would be that b is even, right?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773

    Re: Prove that if xy is odd, then x and y are odd. Proof by cases

    Quote Originally Posted by MadSoulz View Post
    I'm assuming that you mean that case 1 would be that a is even and case 2 would be that b is even, right?
    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.
    Thanks from MadSoulz
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,845
    Thanks
    715

    Re: Prove that if xy is odd, then x and y are odd. Proof by cases

    The answer in post #1 is not correct. You are not trying to prove that if x and y are odd, then their product is odd. You are trying to prove that if x\cdot y is odd, then both x and y are odd. So, if you assume that x and y are odd, you will always get that x and y are odd because that was your assumption in the first place. Instead, assume only that the product x\cdot y 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 x is even. Then x=2k for some integer k. Hence x\cdot y = 2ky = 2(ky) is even. This proves the contrapositive, and in so doing, also proves the initial statement.
    Thanks from topsquark, MadSoulz and emakarov
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773

    Re: Prove that if xy is odd, then x and y are odd. Proof by cases

    Quote Originally Posted by SlipEternal View Post
    The answer in post #1 is not correct. You are not trying to prove that if x and y are odd, then their product is odd. You are trying to prove that if x\cdot y is odd, then both x and y are odd.
    Thanks. I retire for the night.
    Thanks from MadSoulz
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Sep 2013
    From
    United States
    Posts
    67
    Thanks
    3

    Re: Prove that if xy is odd, then x and y are odd. Proof by cases

    Quote Originally Posted by SlipEternal View Post
    The answer in post #1 is not correct. You are not trying to prove that if x and y are odd, then their product is odd. You are trying to prove that if x\cdot y is odd, then both x and y are odd.
    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 (a|b) ^ (b|c), i.e. b=ax and c=by, for any integer x,y

    Then, c=by
    = (ax)y
    = a(xy)
    = az, for some integer z

    Therefore, c=az, for some integer z, so a|c
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,889
    Thanks
    326
    Awards
    1

    Re: Prove that if xy is odd, then x and y are odd. Proof by cases

    Quote Originally Posted by SlipEternal View Post
    The answer in post #1 is not correct. You are not trying to prove that if x and y are odd, then their product is odd. You are trying to prove that if x\cdot y is odd, then both x and y are odd. So, if you assume that x and y are odd, you will always get that x and y are odd because that was your assumption in the first place. Instead, assume only that the product x\cdot y 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 x is even. Then x=2k for some integer k. Hence x\cdot y = 2ky = 2(ky) is even. This proves the contrapositive, and in so doing, also proves the initial statement.
    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
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,610
    Thanks
    1576
    Awards
    1

    Re: Prove that if xy is odd, then x and y are odd. Proof by cases

    Quote Originally Posted by MadSoulz View Post
    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. x=2a + 1 and y=2b + 1.
    Quote Originally Posted by MadSoulz View Post
    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 (a|b) ^ (b|c), i.e. b=ax and c=by, for any integer x,y
    Then, c=by
    = (ax)y
    = a(xy)
    = az, for some integer z
    Therefore, c=az, for some integer z, so a|c
    The question about your OP is that you are proving the converse of what you are asked to prove.
    If xy is odd, then both x~\&~y are odd. Not the other way around.
    Personally, I would do this by contradiction. Suppose xy is odd.
    Then is any even number times any integer is even. SO?

    As for your instructor's proof, I hope he/she said b=ax and c=by, for some integers x & y.
    Otherwise, it is the way to do it.
    Thanks from MadSoulz
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,845
    Thanks
    715

    Re: Prove that if xy is odd, then x and y are odd. Proof by cases

    Quote Originally Posted by MadSoulz View Post
    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 (a|b) ^ (b|c), i.e. b=ax and c=by, for any integer x,y

    Then, c=by
    = (ax)y
    = a(xy)
    = az, for some integer z

    Therefore, c=az, for some integer z, so a|c
    (a|b) \wedge (b|c) \Longrightarrow (a|c) 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.


    Quote Originally Posted by topsquark View Post
    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
    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 \left( \neg(P\wedge Q) \equiv \neg P \vee \neg Q \right). 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.
    Thanks from MadSoulz and topsquark
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Junior Member
    Joined
    Sep 2013
    From
    United States
    Posts
    67
    Thanks
    3

    Re: Prove that if xy is odd, then x and y are odd. Proof by cases

    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.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,845
    Thanks
    715

    Re: Prove that if xy is odd, then x and y are odd. Proof by cases

    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.
    Thanks from MadSoulz and topsquark
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Junior Member
    Joined
    Sep 2013
    From
    United States
    Posts
    67
    Thanks
    3

    Re: Prove that if xy is odd, then x and y are odd. Proof by cases

    Oops, I've made another mistake.

    Find the contrapositive, and prove that x*y is even, with 2-3 cases
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Junior Member
    Joined
    Sep 2013
    From
    United States
    Posts
    67
    Thanks
    3

    Re: Prove that if xy is odd, then x and y are odd. Proof by cases

    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".
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Can someone check a proof involving cases, please?
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 11th 2012, 12:32 AM
  2. Replies: 2
    Last Post: November 18th 2011, 09:49 PM
  3. Proof by Cases
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 18th 2009, 09:36 AM
  4. Proof by cases
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 15th 2007, 02:06 AM
  5. Is this a proof by cases?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 9th 2007, 05:24 AM

Search Tags


/mathhelpforum @mathhelpforum