Equivalence Classes and Partitions

We recall that a binary relation R on a set A is an equivalence relation if and only if the following 3 conditions are all true.
Reflexivity: x A, xRx
Symmetry: x,y A, xRy yRx
Transitivity: x,y,z A, xRy yRz xRz

Example

  1. Let set A={ 2, 4, 6, 8, 10 } and R be a binary relation on A defined by

    (m,n) R   iff   m n (mod 4)   m,n A .

    Recall that m n (mod 4) is equivalent to saying 4 divides (m-n) or (m-n) is an integer multiple of 4. Thus it is easy to see
    (m,n) m-n conclusion is multiple of 4?
    (2,2) 2-2=0 (2,2) R yes, 0 is a multiple of 4
    (2,4) 2-4=-2 (2,4) R no, -2 is not a multiple of 4
    (2,6) 2-6=-4 (2,6) R -4: yes
    (2,8) 2-8=-6 (2,8) R -6: no
    (2,10) 2-10=-8 (2,10) R -8: yes
    (4,2) 4-2=2 (4,2) R 2: no
    (4,4) 4-4=0 (4,4) R 0: yes
    (4,6) 4-6=-2 (4,6) R -2: no

    which gives explicitly

    R = { (2,2), (2,6), (2,10), (4,4), (4,8), (6,6), (6,10), (8,8), (10,10), (6,2), (10,2), (8,4), (10,6) } .

    This relation R can be drawn as

    and is obviously an equivalence relation (cf. examples in the previous lecture). Notice that there are 2 ''connnected'' components, one containing elements 4 and 8 and the other, elements 2, 6 and 10. Here the ''connection'' is made through certain walks along the directions of the arrows. These 2 components are just the 2 distinct equivalence classes under the equivalence relation R. Naturally we may use any element in an equivalence class to represent that particular class which basically contains all elements that are connected to the arbitrarily chosen representative element. Hence, in this case, we may choose 2 to represent the class {2,6,10}, written simply [2]={2,6,10}, and choose for instance 8 to represent the other class {4,8}, that is, [8]={4,8}. Since any member of an equivalence class can be used to represent that class, [6] and [10] will be representing exactly the same equivalence class as [2]. Hence

    [2] [6] [10] = { 2, 6, 10 }, [4] [8] = { 4, 8 } .

    are the 2 distinct equivalnce classes.

The definition of equivalence classes and the related properties as those exemplified above can be described more precisely in terms of the following lemma.

Lemma Let A be a set and R an equivalence relation on A. For any a A we define the equivalence class of a, written [a], by [a] = { x A : x R a}. Then

(i)
For any a A, a [a].
(ii)
For any a,b A , a R b iff [a]=[b].
(iii)
For any a, b A, either [a] [b] = , or [a] =[b].
(iv)
For an equivalence class S, any element a S can be used as a representative of S, guaranteeing [a] =S.

Proof First, R is an equivalence relation means R is reflexive, symmetric and transitive.

(i)
Since R is reflexive implies aRa for any a A, hence a [a].
(ii)
(a)
Necessity. Let aRb. For any x [a] we have xRa. From xRa and aRb, we derive from R's transitivity that xRb, i.e. x [b]. Hence [a] [b]. Likewise [b] [a] because bRa is implied by aRb and R is symmetric. Hence [a]=[b].
(b)
Sufficiency. Let [a] =[b]. Since (i) implies a [a] and thus a [b], we have by definition of [b] that aRb.
(iii)
If [a] [b] , then there exists an x A such that x [a] and x [b]. This means xRa and xRb, i.e. aRx and xRb due to the symmetry of R, implying aRb due to the transitivity. (ii) thus implies [a] =[b].
(iv)
S is an equivalence class means S=[b] for some b A. Thus for any a S=[b], we have aRb and hence from (ii) [a]=[b]=S.

Examples

  1. For the binary relation R defined in example 1, let us verify the results of the above lemma.

    Solution Actually this is more like explanations.

    (a)
    (i) of the lemma in this case implies 2 [2]={2,6,10}, 6 [6], 10 [10], 4 [4] and 8 [8]={4,8} which is obviously true due to the explicit formula at the end of example 1.
    (b)
    (ii) in this case is the same as saying [2]=[6]=[10] and [4]=[8], which are already shown in example 1.
    (c)
    (iii) is consistent with the fact that any 2 of the equivalence classes [2], [4], [6], [8] and [10] are either disjoint (e.g. [2] and [4] have no elements in common) or exactly the same (e.g. [2]=[6]).
    (d)
    (iv) for the equivalence class {2,6,10} implies we can use either 2 or 6 or 10 to represent that same class, which is consistent with [2]=[6]=[10] observed in example 1. Similar observations can be made to the equivalence class {4,8}.
  2. Show that the distinct equivalence classes in example 1 form a partition of the set A there.

    Solution In example 1 we have shown that [2]={2,6,10} and [4]={4,8} are the only distinct equivalence classes. Since A in example 1 is given by A={2,4,6,8,10}, we can easily verify

    (a):   A = [2] [4] ;     (b):   [2] [4] = .

    From the definition of the set partition (see the earlier lecture for sets) we conclude that { [2], [4] } is a partition of set A.

The above example is in fact a special case of the more universal properties to be summarised in the following theorem.

Theorem Let A be a nonempty set.

(i)
If R is an equivalence relation on A, then the distinct equivalence classes of R form a partition of A. This partition is said to be induced by the equivalence relation R.
(ii)
Suppose A has a partition { A1, , An}, i.e. A= Ai and Ai Aj= for any i j. If a relation R on A is defined by
x, y A:     x R y iff Ai of the partition such that x Ai and y Ai , (*)
then R is an equivalence relation, and the distinct equivalence classes of R form the original partition {A1, ,An}.

Proof

(i)
Let Ai for i=1, , m be all the distinct equivalence classes of R. For any x A, since [x] is an equivalence class and hence must be one of the Ai's, we have from Lemma (i) x [x] Ai. Hence A Ai, implying A = Ai because Ai A for any i= 1,..,m. Notice that Ai Aj= for any i j is obvious from Lemma (iii).
(ii)
(a)
Reflexive: x A= Ai, i0 such that x Ai0. Hence xRx from the definition (*) of R.
(b)
Symmetric: x,y R such that xRy, io such that x,y Ai0, i.e. y,x Aio, implying yRx from (*).
(c)
Transitive: x,y,z R such that xRy and yRz, i0 and j0 such that x,y Ai0 and y,z Aj0. Since y Ai0, y Aj0 and Ai's are disjoint for different i, we must have i0=j0, hence x,z Ai0, implying xRz.
From (a), (b), (c) we conclude R is an equivalence relation.
Since by definition of x Ai means [x] ={ y A: yRx} = { y A: i0 such that x,y Ai0 }, if x Ai for some i then i0 must be equal to i because Aj Ak= for any j k. We thus conclude that all Ai's are just the distinct equivalence classes, and [x] for any x A is just one of Ai's. Therefore we see that R will induce the original partitions { A1, , An}.

Example

  1. Let R be the equivalence relation defined on by R={(m,n): m,n , m n (mod 3)}, see examples in the previous lecture. Give the partition of in terms of the equivalence classes of R.

    Solution

    (a)
    Pick any element in , say 0, we have

    [0] ={ x :   x R 0} = { ... , -6, -3, 0, 3, 6, ... } .

    (b)
    Pick any element in \ [0], say 1, we have

    [1] ={x :   x R 1} = { ... , -5, -2, 1, 4, 7, ... } .

    (c)
    Pick any element in \ ([0] [1]), say 5, we have

    [5] ={ x :   x R 5} = { ... , -4, -1, 2, 5, 8, ... } .

    (d)
    Since \ ([0] [1] [5]) = , all distinct equivalence classes are now exhausted. Hence the partition of under R is { [0], [1], [5] }.