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

    HallsofIvy

    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