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!

Equivalence relations

  1. Feb 4, 2006 #1
    ok i don't know why i can't grasp this and i feel so stupid...

    here's an example in the book which i do get...
    Let S denote the set of all nonempty subsets of {1, 2, 3, 4, 5}, and define a R b to mean that a [tex]\cap[/tex] b not equal to [tex]\emptyset[/tex]. The R is clearly reflexive and symmetric. Howerver, R is not transitive since {1, 2} R {2, 3} and {2, 3} R {3, 4} are true, but {1, 2] R {3, 4} is false

    but here's two problems that i don't get where i have to state what the special propert(y/ies) are and state whether R is an equivalence relation on S

    S = {1,2,3,4,5,6,7,8} and x R y means that x - y is odd
    S = {1,2,3,4,5,6,7,8} and x R y means that |4 - x| = |4 - y|
     
  2. jcsd
  3. Feb 4, 2006 #2

    EnumaElish

    User Avatar
    Science Advisor
    Homework Helper

    You have to figure whether each of the properties you described in the "nonempty intersection" example holds for the new examples.

    How do you/your textbook define an equivalence rel.?
     
  4. Feb 4, 2006 #3
    for the two problems i don't have to determine if it's a nonempty intersction, i have to...

    Determine which of the reflexive, symmetric, and transitive properties are satisfied by the given relation R defined on set S, and state whether R is an equivalence relation on S

    S = {1,2,3,4,5,6,7,8} and x R y means that x - y is odd
    S = {1,2,3,4,5,6,7,8} and x R y means that |4 - x| = |4 - y|
     
  5. Feb 4, 2006 #4

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Reflexive: is x R x ? What is x- x?
    Symmetric: if x R y is y R x? If x- y is odd, what is y- x?
    Transitive: if x R y and y R z is x R z? If x- y and y- z are both odd, what can you say about x- z?

    x R x?
    if x R y is y R x? In other words, if you swap x and y in the formula above, is it still true?
    if x R y and y R z, is x R z?
     
  6. Feb 4, 2006 #5

    ok i think i understand that better. it would be symmetric because i can get an odd number, but reflexive and transitive don't always yield an odd number
     
  7. Feb 7, 2006 #6
    ok i'm still having problems with this and i know i'm making it way harder then it needs to be

    for instance here is a problem that's in the book and the solutions manual with the answer


    S is the set of all real numbers and xRy means that [tex]x^2=y^2[/tex]

    The solution manual says that it's reflexive, symmetric and transitive,
    but what makes it that and how do you find it?


    i don't know why i can't grasp this, please help!
    :cry:
     
  8. Feb 7, 2006 #7

    VietDao29

    User Avatar
    Homework Helper

    First, I suggest you should go back to your book, and look up the definitions for reflexive, symmetric and transitive, try to remember it, and try to understand some examples the book provides.
    S is the set of all real numbers, and x R y means that : x2 = y2
    ---------------
    1. Is it reflexive? Is x R x? Or in other word, is x2 = x2
    2. Is it symmetric?
    If x R y, then is y R x? Or in other word, if x2 = y2, is y2 = x2?
    3. Is it transitive?
    If x R y, and y R z, then is x R z? Or in other word, if x2 = y2, and y2 = z2, is x2 = z2?
    ------------
    Can you get it now? :) Or are you still have some problem with it?
     
    Last edited: Feb 7, 2006
  9. Feb 7, 2006 #8
    ok let me ask this, i'm completely making this up so that i can get this... i mean what you posted helps, anyway...

    if i have something like the following and i think this is where my misunderstanding of this is, because i've read the definitions of reflexive, symmetric, and transitive over and over, but i think the following is what i'm not grasping

    if i have the following...
    S={1, 2, 3, 4, 5, 6}

    whate would be the x, y, and for transitive the z
    1=x
    2=y
    3=z
    ????
     
  10. Feb 7, 2006 #9

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Same thing as before:
    Reflexive: xRx. Is x2= x2? Of course, it is! The relation is reflexive.

    Symmetric: if xRy then yRx: If x2= y2 is y2= x2? Of course, it is!

    Transitive: if xRy and yRz then xRz: If x2= y2 and y2= z2, is x2= z2? Of course, it is.

    In fact, this just say "xRy if and only if some function of x equals some function of y" so it is really based on the fact that "= " (the prototypical "equivalence relation") is reflexive, symmetric and transitive.
     
  11. Feb 7, 2006 #10

    VietDao29

    User Avatar
    Homework Helper

    You forgot the relation, what's your relation?
    Okay, lets have another example: let R be a relation on the real number set.
    x R y means that: x > y.
    Now:
    Reflexive: Is x R x? Is x > x? (No, right?, 3 > 3 is false)
    Symmetric: If x R y, then is y R x? Say x = 3, y = 2 (3 > 2 => 2 > 3, again wrong)
    Transitive: If x R y, and y R z, then is x R z?
    x > y, and y > z, we have:
    x > y > z, so it implies that: x > z.
    You can test it with x = 3, y = 2, z = -1.5
    So it's transitive, right?
    Overall, The relation ">" between real numbers is not an equivalence relation. Because it's transitive, but not symmetric, and reflexive.
    Can you understand this?
     
    Last edited: Feb 7, 2006
  12. Feb 7, 2006 #11
    ok i see how that work, now if i use what i stated before
    S={1, 2, 3, 4, 5, 6}

    in what order would i plug in the values to x, y, and z?

    would i just go from one to the other meaning
    1 would be x
    2 would be y
    3 would be z

    this is where i'm running into the confusion for some reason.

    i understand what you posted with no problem it just in what order i guess that i'm having the problem with.

    also thank you so much for helping me
     
  13. Feb 7, 2006 #12

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    What relation are you talking about? "Transitive", "symmetric", and "reflexive" are possible properties of a relation, not a set or members of that set.

    A relation must say "xRy if and only if" some formula or other property involving x and y.
    The relation is "reflexive" if and only if xRx for all x in the set: replace both x and y in the formula with x (or some other single letter representing any member of the set)- is the formula true?

    The relation is "symmetric" if whenever xRy, also yRx: Assume the formula is true with x and y, swap x and y in the formula. Is it still true?

    The relation is "transitive" if whenever xRy and yRz, also xRz. Assume that the formula is true with x and y and also true if y and z in place of x and y. Can you use those to prove that the formula is still true with x and z in place of x and y?
     
  14. Feb 7, 2006 #13

    i'm talking about any relation. i understand what you are saying about the definitions to the 3 properties, but for instance the one problem i had posted a few posts ago

    S = {1,2,3,4,5,6,7,8} and x R y means that x - y is odd

    i realize that xRx isn't going to get me an odd number so i know it's not going to be reflexive

    here's where i'm confused if i do xRy and the yRx if i'm only doing something like 2-3 or 3-2 i will get an odd number, but if i were to do 2-4 or 4-2 of course i'm not going to have an odd number. this is what i'm asking about with pluging in the values into x, y, and z, is there a specific order in which i plug in a value? i hope i'm making better sense
     
  15. Feb 7, 2006 #14

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Okay since deciding if this relation is reflexive, symmetric, and transitive is still your homework problem, not mine, lets look at a slightly different example: xRy if and only if x- y is an even number.

    Reflexive: xRx for all numbers.
    Proof: x- x= 0 which is an even number. Yes, this relation is reflexive.

    Symmetric: if xRy, then yRx
    Proof: IF xRy, then x-y is even. yRx becomes y- x (since y and x have swapped places in yRx, they swap places in the definition of the relation).
    Of course, y- x= -(x- y) and the negative of an even number is even. Yes, that's a symmetric relation.

    Transitive: if xRy and yRz then xRz
    Proof: If xRy, then x- y is even. If yRz, then y- z is even. To decide if xRz, we need to look at x-z. x- z= (x- y)+ (y- z) and so is the sum of two even numbers. Yes, the sum of two even numbers is even. The relation is transitive.
     
  16. Feb 7, 2006 #15
    OMG thank you the light bulb finally went on...:biggrin: i'm soooo sorry for being a complete idiot, but thank you so much for helping... i understand it now:surprised
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Equivalence relations
  1. Equivalence relations (Replies: 1)

  2. Equivalence Relations (Replies: 11)

  3. Equivalence Relations (Replies: 17)

  4. Equivalence relation (Replies: 7)

Loading...