1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: [Discrete Math] Relations, symmetric and transitive

  1. Feb 19, 2006 #1
    Ok so here's one of the questions we've been assigned...

    So I can graphically see what this relation looks like, and from that I've shown it's reflexive. Now I'm working on proving it as being symmetric, but I can't put it into words.

    b) ~ is symmetric. Well we want to show that aRb -> bRa, so [tex]5 | a^2+4b^2[/tex] -> [tex]5 | b^2+4a^2[/tex]. Well I can see graphically once again that [tex]b^2+4a^2[/tex] will always give me a multiple of 5 - this is what I can't put into words... I can't really figure out how to express aRb -> bRa... From another help source I was told this;

    [tex]5 | a^2+4b^2[/tex] iff [tex]5 | a^2-b^2[/tex], so then I was told to [tex]a^2+4b^2 - a^2-b^2 = 5b^2[/tex], which is a multiple of 5. But I don't see how the hell that works... But it's based on some equivalance class, modulous 5 (maybe?) that's 4 = -1...

    c) ~ is transitive. Graphically this looks true. We need to show that aRb and bRc -> aRc. But I'm not sure where to start on this... I don't see where c fits in.
  2. jcsd
  3. Feb 19, 2006 #2


    User Avatar
    Science Advisor

    That 5 divides a2+ 4b2 if and only if 5 divides a2- b2 is a very good hint! Of course, it's clear that it is true: if 5 divides a2- b2 then it certainly divides ab- b2+ 5b2 and vice versa.

    The point is that if a2+ 4b2 is not obviously "symmetric" but a2- b2 certainly is: if a2- b2 is divisible by 5 then b2- a2= -(a2- b2) certainly is!

    Once again, that lovely "5 divides a2+ 4b2 if and only if 5 divides a2- b2" is key. If 5 divides a2- b2 and 5 divides b2- c2 then what can you say about a2- c2= (a2- b2)- (b2- c2)?
  4. Feb 19, 2006 #3
    a^2 - b^2 is obviously symmetric? I don't see it =\ can you explain this further?

    [edit] Ohh... So it's like aRb -> bRa (for all a,b in some set). I see it now. But I don't see why we are using a^2-b^2, where did it come from? What made you say, oh well 5|a^2+4b^2 iff 5|a^2-b^2.
    Last edited: Feb 19, 2006
  5. Feb 19, 2006 #4
    That 5 must also divide a2- c2= (a2- b2)- (b2- c2) since aRb^bRc -> aRc
  6. Feb 19, 2006 #5

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Adding (or subtracting) a multiple of 5 doesn't alter the divisibilty or indivisibilty by 5 of a number. That's just basic modulo arithmetic.

    a^2-b^2 = a^2+4b^2 -5b^2

    hence one side is divisible 5 if and only if the other side is.

    and since a^2-b^2=-(b^2-a^2)

    it is obviously a symmetric relation.
  7. Feb 19, 2006 #6
    I can follow this really well; but never in a million years would I have used the idea that I could just subtract a mulitple of 5... But yes, this now makes sense.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook