Relations, Equivalence relations

MiNI PW | Strona główna | Course contents

A relation R between elements of a set X and elements of a set Y is a subset of the Cartesian product of X and Y, X⨯Y (the set of all ordered pairs (p,q) such that p comes from X and q from Y). X and Y may be different or equal. If X=Y we say that R is a relation on X (or on Y, when X=Y it makes no difference).
If R=∅ we call R the empty relation. It is not particularly exciting, nobody in X is related to anybody in Y. On the other end of the spectrum we have the full relation R=X⨯Y, where everybody in X is related to everybody in Y.
  1. For each of the given relations on {1,2,3,6} list all its elements and sketch its graph.
    1. xRy Û x divides y (in symbols: x|y),
    2. xRy Û x<y
    3. xRy Û x=y
    4. xRy Û x¹y
    5. xRy Û x2 £ y
    6. xRy Û x+y is odd
     
  2. Determine which of the following relations on N\{1} are equivalence relations. Find equivalence classes for those who are.
    1. xRy Û gcd(x,y) = 1
    2. xRy Û gcd(x,y) > 1
    3. xRy Û x divides y
    4. xRy Û x+y is even
    5. xRy Û x+y is odd
    6. xRy Û xy is odd
     
  3. R1 and R2 are equivalence relations on a set X. In each of the following questions, if the answer is YES, describe equivalence classes of the relation in terms of equivalence classes of R1 and R2.
    1. Is R1ÇR2 an equivalence relation on X?
    2. Is R1ÈR2 an equivalence relation on X?
    3. Is R1\R2 an equivalence relation on X?
    4. Is R1´R2 an equivalence relation on X´X?
     
  4. Show that for every partition p of a set X there exists an equivalence relation on X whose equivalence classes are exactly elements of p. A partition of X is a set (a family) of pairwise disjoint subsets of X whose union is X. Pairwise disjoint means that each two sets from the family are disjoint.
  5.  
  6. Let X denote the set of all 0-1 sequences of length 100. We define the following relation R on X:
    aRb Û |{i : a(i)=b(i)}| is even
    Is R an equivalence on X? If it is, describe its equivalence classes.