Equivalence Relations

  1. I am not exactly clear on what an equivalence relation. If A is a set, then a relation on A is a subset R. The relation R is an equivalence relation on A if it satisfies the reflexive property, symmetric property, and transitive property. What types of relations are we talking about. And when could these relations ever not have these 3 properties. And what are equivalence classes? I need some simple examples to demonstrate this since none are really provided in this textbook.
     
  2. jcsd
  3. What are you asking? If there are equivalence relations not satisfying those properties? Obviously not, since then the relations wouldn't be equivalence relations.

    Maybe you want an example of a relation that's not an equivalence relation. Cconsider the relation "less than" (<) on the real numbers. It is not symmetric, since for example, 3 < 4 doesn't imply 4 < 3.
     
    Last edited: Feb 29, 2004
  4. What about reflexive
     
  5. matt grime

    matt grime 9,395
    Science Advisor
    Homework Helper

    it's not relflexive either, 3<3? Don't think so! But [tex]\leq[/tex] is reflexive (and transitive) but not symmetirc again.

    Equivalence relations are the generalization of the relation of being equal - whilst two elements are not the same, they may in share all the properties that you care about.

    an equivalence realation on a set A is not a subset of A. It is just a relation, a rule for saying how/when two elements are related in some manner.

    the equivalence class [x] of x in A is the subset of A of all elements that are 'related' to x. The rules for an equivalnce relation imply that if xRy, they [x]=[y] - ie equivalence classes are equal or disjoint.

    Important examples are modulo arithmetic, conjugacy classes of groups, cosets of subgroups, defining quotient structures such as in the isomorphism theorems of algebra


    here are several relations on Z

    say xRy iff x=y+1

    this not symmetric transitive or refelxive

    xRy iff x<y this is only transitive


    xRy iff x<=y is transitive and relfexive but not symmetric

    xRy iff x is not equal to y is symmetric but neither reflexive nor transitive.
     
  6. I think I have a really good way of explaining this so I would like comments.

    My example of an equivalence relation is x and y have the same parity
    in other words xRy is true when both x and y are odd. xRy is also true
    when both x and y are even. If one of the variables x,y is odd or even then xRy false.

    So xRy is true when x and y are the "same"(equivalent) in some respect. if xRy is true x and y have a specific common property.
    Exactly what the common property is depends on the problem.
    This explains all your rules.

    symmetric
    xRy => yRx
    If x has a common property with y then y must have a common property with x.

    reflexive
    xRx
    x and x must have a common propery!

    transitive

    xRy and xRz => yRz.
    If x and y have a common property and x and z have a common property then y and z share a common property.

    Now cleary an equivalence relation divides the set into distint subset where everything each subset has the same common property.

    if you remember my original example where the equivalence relation is " both odd or both even" then two subsets are the even numbers and the odd numbers and xRy => x and y are in the same subset.
     
  7. Janitor

    Janitor 1,189
    Science Advisor

    Hope this helps

    In general, an n-ary relation (n a positive integer) R on a set A is a subset of the Cartesian product A x A x ... A (n times). Since the most commonly used relations are binary, we are usually dealing with relations that are a subset of A x A.

    I just thought of a binary relation that is symmetric but not reflexive and not transitive: the relation "is perpendicular to" on the set of vectors in a real three-dimensional vector space.
     
  8. Janitor

    Janitor 1,189
    Science Advisor

    Examples of binary relations

    The binary relation "divides," on the set of positive integers (as in "5 divides 15, 5 does not divide 12") is reflexive and transitive, but not symmetric.

    There are 8 possible "truth tables" (if I can use that terminology for this purpose) for a binary relation to fall into:

    1) Reflexive, Symmetric, Transitive
    2) Reflexive, Symmetric, not Transitive
    ...
    8) not Reflexive, not Symmetric, not Transitive

    We now have examples of some of those eight in this thread. Can anybody come up with examples of the others? I don't just mean ad hoc examples, such as: "A Bush-Kerry binary relation on the set (a, b, c) is given by the subset (<a,c>, <b,c>) (or in other terminology, aRc and bRc)" which is not reflexive, not symmetric, and not transitive. Here I am using < , > to mean ordered pair.
     
    Last edited: Mar 7, 2004
  9. Janitor

    Janitor 1,189
    Science Advisor

    Another binary relation

    The binary relation "is parallel to" on the set of vectors in a real three-dimensional vector space is reflexive, symmetric, and transitive.
     
    Last edited: Mar 12, 2004
  10. matt grime

    matt grime 9,395
    Science Advisor
    Homework Helper

    Let's do it on N. let R, S T be reflexive etc, and nR be the negations

    (R)(S)(T):

    x~y iff x=y


    one negation:

    (nR)(S)(T)
    ???


    (R)(nS)(T)
    x~y iff x<=y


    (R)(S)(nT)
    x~y iff x=y+1 or x=y-1 or x=y



    two negations:

    (nR)(nS)(T)
    x~y iff x<y

    (nR)(S)(nT)
    x~y iff x is not equal to y.

    (R)(nS)(nT)
    x~y iff x=y or x=y+1

    three negations:
    (nR)(nS)(nT)
    x~y iff x=y+1
     
  11. Janitor

    Janitor 1,189
    Science Advisor

    Thanks Matt.

    Now you've got me trying to come up with a relation (nR)(S)(T) on N.

    By the way, if by N you mean the naturals, should we broaden it to the integers, to avoid lack-of-closure problems with x=y-1?
     
    Last edited: Mar 7, 2004
  12. matt grime

    matt grime 9,395
    Science Advisor
    Homework Helper

    fine, Z, N, whichever seems most appropriate to you it isn't important I don't beleive (I am not saying every possible relator of every number must exist)
     
  13. Hurkyl

    Hurkyl 16,089
    Staff Emeritus
    Science Advisor
    Gold Member

    Well, if your relation is symmetric and transitive and you have x~y, then:

    x~y
    therefore y~x
    therefore x~x

    !

    So in order for a relation to be symmetric, transitive, and not reflexive, you must have some element x that is not related to anything.

    BTW, there are three classes for reflexivity and symmetry;

    You have reflexive ([itex]\forall x:x\sim x[/itex]), irreflexive ([itex]\forall x: \neg (x \sim x)[/itex]), and neither.

    You have symmetric ([itex]\forall x \forall y: x \sim y \Leftrightarrow y \sim x[/itex]), antisymmetric ([itex]\forall x \forall y: x \sim y \wedge y \sim x \Rightarrow x = y[/itex]), and neither.
     
    Last edited: Mar 7, 2004
  14. Janitor

    Janitor 1,189
    Science Advisor

    "I am not saying every possible relator of every number must exist."

    Fair enough! I avoided zero in my "divides" example, but given your proviso, maybe I didn't need to. Thanks.
     
    Last edited: Mar 7, 2004
  15. Janitor

    Janitor 1,189
    Science Advisor

    Thanks Hurkyl for pointing out that "So in order for a relation to be symmetric, transitive, and not reflexive, you must have some element x that is not related to anything." I guess that is why it is hard to come up with an example that doesn't look ad hoc, for that particular case. And thanks for pointing out that one can usefully further subdivide some of my eight cases.
     
  16. Janitor

    Janitor 1,189
    Science Advisor

    Amplifying on something Matt said-

    As chance would have it, I came upon a definition today: A relation is total if for all x there exists a y such that xRy.

    So my "divides" relation is a total relation on Z+ but not on Z.
     
  17. matt grime

    matt grime 9,395
    Science Advisor
    Homework Helper

    Is y allowed to be x? For then every reflexive relation is total.
     
  18. Elements of the partition on A are subsets of A, and the Union of the partition is A and the intersection of the partition is NULL.
     
  19. I have a question. For something like x=ymodn, how would you prove something which is intuitively obvious like for this relation, n distinct equivalence classes exist ([0],[1],...[n-1]).
     
  20. you just need to show that if you have some Natural number x , that you infact have a partition.

    so x can be in some set A and in some set B iff A = B.

    how it is partitioned is not as important as showing that it is an equivilence relation because once you establish the EQ Relation on the set, you have no need to proove that a partition exists.
     
  21. Janitor

    Janitor 1,189
    Science Advisor

    "Is y allowed to be x? For then every reflexive relation is total." - Matt

    Yes, I didn't see any restriction saying y had to be distinct from x. So you make a good point: every reflexive relation has to be a total relation.
     
Know someone interested in this topic? Share this thead via email, Google+, Twitter, or Facebook

Have something to add?