Equivalence Relations • Definition 1 ○ A relation on a set A is called an equivalence relation if ○ it is reflexive, symmetric, and transitive • Definition 2 ○ Two elements a,b that are related by an equivalence relation are called equivalent ○ The notation a ∼ b is often used to denote that a and b are equivalent elements with respect to a particular equivalence relation. Strings • Example ○ Suppose that R is the relation on the set of strings of English letters such that ○ aRb if and only if l(a) = l(b), where l(x) is the length of the string x. ○ Is R an equivalence relation? • Solution ○ Show that all of the properties of an equivalence relation hold ○ Reflexivity § Because l(a)=l(a), it follows that aRa for all strings a. ○ Symmetry § Suppose that aRb. Since l(a)=l(b), l(b)=l(a) also holds and bRa. ○ Transitivity § Suppose that aRb and bRc § Since l(a)=l(b),and l(b)=l(c), l(a)=l(a) also holds and aRc. Congruence Modulo m • Example ○ Let m be an integer with m 1 ○ Show that the relation ○ R={(a,b)│a≡b (mod m) } ○ is an equivalence relation on the set of integers. • Solution ○ Recall that a≡b (mod m) if and only if m divides a−b ○ Reflexivity § a≡a (mod m) since a−a=0 is divisible by m since 0 = 0 ∙ m. ○ Symmetry § Suppose that a≡b (mod m) § Then a−b is divisible by m, and so a−b=km, where k is an integer § It follows that b−a=(−k)m, so b≡a (mod m). ○ Transitivity § Suppose that a≡b (mod m) and b≡c (mod m). § Then m divides both a−b and b−c. § Hence, there are integers k and l with a−b=km and b−c=lm § We obtain by adding the equations: § a−c=(a−b)+(b−c)=km+lm=(k+l)m § Therefore, a≡c (mod m) Divides • Example ○ Show that the “divides” relation on the set of positive integers is not an equivalence relation. • Solution ○ The properties of reflexivity, and transitivity do hold, but there relation is not transitive. ○ Hence, “divides” is not an equivalence relation. ○ Reflexivity § a ∣ a for all a. ○ Not Symmetric § For example, 2 ∣ 4, but 4 ∤ 2 § Hence, the relation is not symmetric. ○ Transitivity § Suppose that a divides b and b divides c. § Then there are positive integers k and l such that b=ak and c=bl. § Hence, c=a(kl), so a divides c. § Therefore, the relation is transitive. Equivalence Classes • Let R be an equivalence relation on a set A. • The set of all elements that are related to an element a of A is called the equivalence class of a • The equivalence class of a with respect to R is denoted by [a]_R. • When only one relation is under consideration, we can write [a], without the subscript R • Note that [a]_R={s|(a,s)∈R} • If b∈[a]_R, then b is called a representative of this equivalence class. • Any element of a class can be used as a representative of the class. • The equivalence classes of the relation congruence modulo m are called the congruence classes modulo m. • The congruence class of an integer a modulo m is denoted by [a]_m • So [a]_m={…,a−2m,a−m,a+2m,a+2m,…} • For example, ○ [0]_4 = {…, −8, −4 , 0, 4 , 8 , …} ○ [1]_4 = {…, −7, −3 , 1, 5 , 9 , …} ○ [2]_4 = {…, −6, −2 , 2, 6 , 10 , …} ○ [3]_4 = {…, −5, −1 , 3, 7 , 11 , …} Equivalence Classes and Partitions • Theorem 1 ○ Let R be an equivalence relation on a set A. ○ These statements for elements a and b of A are equivalent: i) aRb ii) [a]=[b] iii) [a]∩[b]=∅ • Proof ○ We show that (i) implies (ii). ○ Assume that aRb. ○ Now suppose that c ∈ [a].Then aRc. Because aRb and R is symmetric, bRa. ○ Because R is transitive and bRa and aRc, it follows that bRc. ○ Hence, c ∈ [b]. Therefore, [a]⊆ [b]. ○ A similar argument (omitted here) shows that [b]⊆ [a]. ○ Since [a]⊆ [b] and [b]⊆ [a], we have shown that [a] = [b]. Partition of a Set • A partition of a set S is a collection of disjoint nonempty subsets of S that have S as their union. • In other words, the collection of subsets A_i, where i∈I, forms a partition of S if and only if ○ A_i≠∅ for i∈I, ○ A_i∩A_j=∅ when i≠j, ○ ⋃8_(i∈I)▒A_i =S An Equivalence Relation Partitions a Set • Let R be an equivalence relation on a set A. • The union of all the equivalence classes of R is all of A • Since an element a of A is in its own equivalence class [a]_R. In other words, ○ ⋃8_(a∈A)▒[a]_R =A • From Theorem 1, it follows that these equivalence classes are either equal or disjoint • So [a]_R∩[b]_R=∅ when [a]_R≠[b]_R. • Therefore, the equivalence classes form a partition of A • Because they split A into disjoint subsets. Equivalence Relation and Partition • Theorem 2 ○ Let R be an equivalence relation on a set S. ○ Then the equivalence classes of R form a partition of S. ○ Conversely, given a partition {A_i│i∈I} of the set S ○ There is an equivalence relation R that has the sets A_i, i∈I, as its equivalence classes. • Proof ○ We have already shown the first part of the theorem. ○ For the second part, assume that {A_i│i∈I} is a partition of S. ○ Let R be the relation on S consisting of the pairs (x, y) ○ where x and y belong to the same subset A_i in the partition. ○ We must show that R satisfies the properties of an equivalence relation. ○ Reflexivity § For every a∈S, (a,a)∈R, because a is in the same subset as itself. ○ Symmetry § If (a,b)∈R, then b and a are in the same subset of the partition, so (b,a)∈R ○ Transitivity § If (a,b)∈R and (b,c)∈R, then a and b are in the same subset of the partition, as are b and c. § Since the subsets are disjoint and b belongs to both, the two subsets of the partition must be identical. § Therefore, (a,c)∈R since a and c belong to the same subset of the partition.
