1. Not finding help here? Sign up for a free 30min 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!

Prove that a relation is an equivalence relation

  1. Oct 14, 2008 #1
    Please be nice to me, I'm new here. Anyway, help to solve this maths problem would be much appreciated:
    1. The problem statement, all variables and given/known data
    Work out a detailed proof (below) that the relation on the integers defined by p~q if and only if 7|p-q is an equivalence relation:
    a) the relation is reflexive
    b) the relation is symmetric
    c) the relation is transitive


    2. Relevant equations
    p~q if and only if 7|p-q


    3. The attempt at a solution
    a) (I'm pretty sure this is done right)
    If relation is reflexive then:
    x[tex]\in[/tex]S[tex]\rightarrow[/tex] (x,x) [tex]\in[/tex]R
    Therefore x~x
    7|x-x since x-x=0 and 7|0
    Therefore relation is reflexive.

    That's the easy bit. Now:
    b)If relation is symmetric then:
    x~y [tex]\leftrightarrow[/tex] y~x

    And I don't know how to go on from there. Please help me!!
     
    Last edited: Oct 14, 2008
  2. jcsd
  3. Oct 14, 2008 #2

    statdad

    User Avatar
    Homework Helper

    Suppose

    [tex] x \sim y [/tex]

    so that

    [tex]
    7 \mid x - y
    [/tex]

    To show that

    [tex] y \sim x [/tex]

    you need to show that

    [tex]
    7 \mid y - x
    [/tex]

    How can you do that?


    For the transitive part, begin by assuming

    [tex]
    \begin{align*}
    x \sim y & \text{ so } 7 \mid x - y \\
    y \sim z & \text{ so } 7 \mid y - z
    \end{align*}
    [/tex]

    Write out what these two statements mean, and you should see why it follows that

    [tex]
    x \sim z
    [/tex]
     
  4. Oct 14, 2008 #3

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    You mean "reflexive".

    'quote]That's the easy bit. Now:
    b)If relation is symmetric then:
    x~y [tex]\leftrightarrow[/tex] y~x

    And I don't know how to go on from there. Please help me!![/QUOTE]
    x~y means 7 divides x-y which means x-y= 7n for some integer n.

    y~ x means 7 divides y- x which means y- x= 7m for some m. Knowing that x- y= 7n, y- x= 7 times what?

    "Transitive": if x~y and y~z then x~z.

    Okay, you know x~y so x- y= 7n for some integer n.
    You know y~ z so y- z= 7m for some integer m.
    Therefore x- z= 7*what?
    (hint: what is (x- y)+ (y- z)?)
     
  5. Oct 14, 2008 #4
    Ok, focusing on the symmetric bit for now (sorry about that major typo, HallsofIvy):

    x-y=7n
    y-x=-7n
    m=-7n

    I can see that this is leading to some sort of a proof, but I don't really know what to write. Is something like the following enough for proof?:
    m and n have a common factor of 7, so x-y and y-x are always divisible by 7. Therefore x~y[tex]\leftrightarrow[/tex]y~x.
     
  6. Oct 14, 2008 #5
    I've proved the transitivity now, thanks for the help you two. Unfortunately,I've just realised that there's more:
    Fill in the blanks:
    "The equivalence class containing 5 is given by
    [5] = {n[tex]\in Z[/tex]|n has remainder _ when divided by _}"
    Am I supposed to put in 0 and 7? If it is, that seems like a bit of a random question. If it isn't, then I have no idea what's going on!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Prove that a relation is an equivalence relation
  1. Equivalence relation (Replies: 4)

  2. Equivalence relations (Replies: 1)

  3. Equivalence Relations (Replies: 11)

  4. Equivalence Relations (Replies: 17)

Loading...