9.5 Equivalence Relations Apr 23, 2018 Shawn Math 240 No comments yet 9.3 Representing Relations Apr 23, 2018 Shawn Math 240 No comments yet
![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.](https://shawnzhong.com/wp-content/uploads/2018/04/img_5addedc1250d8.png)
![Representing Relations Using Matrices • A relation between finite sets can be represented using a zero-one matrix. • Suppose R is a relation from A={a_1,a_2,…,a_m } to B={b_1,b_2,…,b_n } ○ The elements of the two sets can be listed in any arbitrary order ○ When A=B, we use the same ordering. • The relation R is represented by the matrix ○ M_R = [m_ij], where ○ m_ij={■8(1&if (a_i,b_j )∈R@0&if (a_i,b_j )∉R)┤ • The matrix representing R has ○ a 1 as its (i,j) entry when a_i is related to b_j ○ a 0 if a_i is not related to b_j. Examples of Representing Relations Using Matrices • Example 1 ○ Suppose that A = {1,2,3} and B = {1,2} ○ Let R be the relation from A to B containing (a,b) if a b. ○ What is the matrix representing R (with increasing numerical order) • Solution ○ Because R={(2,1), (3,1),(3,2)}, the matrix is ○ M_R=[■8(0&0@1&0@1&1)] • Example 2 ○ Let A={a_1,a_2, a_3} and B={b_1,b_2, b_3,b_4, b_5}. ○ Which ordered pairs are in the relation R represented by the matrix ○ M_R=[■8(0&1&0&0&0@1&0&1&1&0@1&0&1&0&1)] • Solution ○ Because R consists of those ordered pairs (a_i,b_j) with m_ij = 1 ○ R={(a_1, b_2), (a_2, b_1),(a_2, b_3), (a_2, b_4),(a_3, b_1), {(a_3, b_3 ), (a_3, b_5 )} Matrices of Relations on Sets • If R is a reflexive relation, all the elements on the main diagonal of M_R are equal to 1 • R is a symmetric relation, if and only if m_ij = 1 whenever m_ji = 1 • R is an antisymmetric relation, if and only if m_ij = 0 or m_ji = 0 when i≠j Example of a Relation on a Set • Example 3: Suppose that the relation R on a set is represented by the matrix ○ M_R=[■8(1&1&0@1&1&1@0&1&1)] • Is R reflexive, symmetric, and/or antisymmetric? • Because all the diagonal elements are equal to 1, R is reflexive • Because M_R is symmetric, R is symmetric • R not antisymmetric because both m_1,2 and m_2,1 are 1 Representing Relations Using Digraphs Definition ○ A directed graph, or digraph, consists of a set V of vertices (or nodes) together with a set E of ordered pairs of elements of V called edges (or arcs). ○ The vertex a is called the initial vertex of the edge (a,b) ○ The vertex b is called the terminal vertex of this edge. ○ An edge of the form (a,a) is called a loop. Example 1 ○ A drawing of the directed graph with vertices a, b, c, and d ○ and edges (a, b), (a, d), (b, b), (b, d), (c, a), (c, b), and (d, b) is shown here. Example 2 ○ What are the ordered pairs in the relation represented by this directed graph? § ○ The ordered pairs in the relation are ○ (1, 3), (1, 4), (2, 1), (2, 2), (2, 3), (3, 1), (3, 3), (4, 1), (4, 3) Determining which Properties a Relation has from its Digraph • Reflexivity: A loop must be present at all vertices in the graph. • Symmetry: If (x,y) is an edge, then so is (y,x). • Antisymmetry: If (x,y) with x≠y is an edge, then (y,x) is not an edge. • Transitivity: If (x,y) and (y,z) are edges, then so is (x,z) Determining which Properties a Relation has from its Digraph • Example 1 ○ Reflexive? No, not every vertex has a loop ○ Symmetric? Yes (trivially), there is no edge from one vertex to another ○ Antisymmetric? Yes (trivially), there is no edge from one vertex to another ○ Transitive? Yes, (trivially) since there is no edge from one vertex to another • Example 2 ○ Reflexive? No, there are no loops ○ Symmetric? No, there is an edge from a to b, but not from b to a ○ Antisymmetric? No, there is an edge from d to b and b to d ○ Transitive? No, there are edges from a to c and from c to b, but there is no edge from a to d • Example 3 ○ Reflexive? No, there are no loops ○ Symmetric? No, for example, there is no edge from c to a ○ Antisymmetric? Yes, whenever there is an edge from one vertex to another, there is not one going back ○ Transitive? No, there is no edge from a to b • Example 4 ○ Reflexive? No, there are no loops ○ Symmetric? No, for example, there is no edge from d to a ○ Antisymmetric? Yes, whenever there is an edge from one vertex to another, there is not one going back ○ Transitive? Yes (trivially), there are no two edges where the first edge ends at the vertex where the second edge begins Closures • Definition ○ The closure of a relation R on A with respect to property P ○ is the least relation on A that contains R and has property P • Note ○ Least relation R^′ on A s.t. ○ R⊆R′ ○ R′ has property P ○ If S is a relation that safisfies the condition above, then R^′⊆S • Example ○ The reflexive closure of R is just R∪{(a,a)│a,∈A} ○ The symmetric closure of R is R∪R^(−1) ○ The transitive closure of R is R∪R^2∪R^3∪… Path in Directed Graphs • Definition ○ A path from a to b is a directed graph G is a sequence of edges ○ (a=x_0,x_1 ),(x_1,x_2 ),…,(x_(n−1),x_n=b) where n 0 ○ We denote the path by x_0,x_1,…,x_n say that the path has length n • Theorem ○ Let R be a relation on a set A ○ There is a path of length n from a to b if and only if (a,b) is an element of R^n The Connectivity Relation • Definition ○ Let R be a relation on A ○ The connectivity relation R^∗ cibsusts if all elements (a,b) s.t. ○ There is a path from a to b in R ○ In other words, R^∗ is the union of R,R^2,R^3,… ○ R^∗=⋃24_(i=1)^∞▒R^((i) ) • Example 1 ○ Let R be the relation between US state such that (a,b) is in R if a and b share a border. What is R^∗? ○ All pairs of states except Alaska and Hawaii • Example 2 ○ Let R be the relation between integers s.t. (a,b) is in R if b=a+1 ○ What is R^2, R^n, R^∗ ○ R^2={(a,b)│b=a+2} ○ R^n={(a,b)│b=a+n} ○ R^∗={(a,b)│a b} • Transitive closure ○ The connectivity relation R^∗ is exactly the transitive closure of R ○ We need to show that R is a subset of R^∗, R^∗ is transitive and least with that property. ○ The first two are easy ○ Let S be a transitive relation containing R ○ By induction we show that S contains R^n for every n Computing The Connectivity Relation • Theorem ○ Let R be a relation on A and let n be the number of elements in A. ○ The connectivity relation R^∗ is the union of R,R^2,…,R^n • Proof ○ Let (a,b) be the element of R^∗ ○ Let a_0=x_0,x_1,…,x_m=b be the shortest path witnessing this. ○ If m n, then two of the vertices among x_1,…,x_m must be the same, say x_i=x_j ○ But then we can find a shorter path x_0,x_1,…,x_i=x_j,x_(j+1),x_n • Corollary ○ M_(R^∗ )=M_R∨M_R^[2] ∨…∨M_R^[n] • Example ○ Compute M_(R^∗ ) for the relation R={(a,b),(b,c),(c,d),(d,b)} ○ M_R=[■8(0&1&0&0@0&0&1&0@0&0&0&1@0&1&0&0)] ○ M_R^[2] =[■8(0&1&0&0@0&0&1&0@0&0&0&1@0&1&0&0)]⨀[■8(0&1&0&0@0&0&1&0@0&0&0&1@0&1&0&0)]=[■8(0&0&1&0@0&0&0&1@0&1&0&0@0&0&1&0)] ○ Similarly, compute M_R^[3] ,M_R^[4] ○ Then M_(R^∗ )=M_R∨M_R^[2] ∨M_R^[3] ∨M_R^[4]](https://shawnzhong.com/wp-content/uploads/2018/04/img_5added4674c91.png)
