10.1 Graphs and Graph Models May 07, 2018 Shawn Math 240 No comments yet 9.6 Partial Orderings May 07, 2018 Shawn Math 240 No comments yet 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 9.1 Relations and Their Properties Apr 18, 2018 Shawn Math 240 No comments yet 1 2 3 4 … 9
![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)
![Binary Relations • Definition ○ A binary relation R from a set A to a set B is a subset R⊆A×B. • Example ○ Let A={0,1,2} and B={a,b} ○ {(0, a), (0, b), (1, a), (2, b)} is a relation from A to B. ○ We can represent this relation graphically or using a table: • Note ○ Relations are more general than functions ○ A function is a relation where exactly one element of B is related to each element of A Binary Relation on a Set • Definition ○ A binary relation R on a set A is a subset of A×A or a relation from A to A. • Example 1 ○ Suppose that A={a,b,c} ○ Then R={(a,a),(a,b), (a,c)} is a relation on A • Example 2 ○ Let A={1, 2, 3, 4} ○ The ordered pairs in the relation R={(a,b)│a divides b} are ○ {(1,1), (1, 2), (1,3), (1, 4), (2, 2), (2, 4), (3, 3),(4,4)} • Question: How many relations are there on a set A? ○ Because a relation on A is the same thing as a subset of A×A ○ We count the subsets of A×A. ○ Since A×A has n^2 elements when A has n elements ○ And a set with m elements has 2^m subsets ○ There are 2^(|A|^2 ) subsets of A×A. ○ Therefore, there are 2^(|A|^2 ) relations on a set A. • Example 3 ○ Consider these relations on the set of integers: § R_1={(a,b)│a≤b} § R_2={(a,b)│a b} § R_3={(a,b)│a=b or a=−b} § R_4={(a,b)│a=b} § R_5={(a,b)│a=b+1} § R_6={(a,b)│a+b≤3} ○ Note § These relations are on an infinite set and each of these relations is an infinite set § R_5 can be viewed as a function § Our definition of a function f:A→B is a subset of A×B § Therefore every function is a relation ○ Which of these relations contain each of the pairs § (1,1), (1, 2), (2, 1), (1, −1), and (2, 2)? ○ Solution § (1,1) is in R_1, R_3, R_4, and R_6 § (1,2) is in R_1 and R_6 § (2,1) is in R_2, R_5, and R_6 § (1, −1) is in R_2, R_3, and R_6 § (2,2) is in R_1, R_3, and R_4 Reflexive Relations • Definition ○ R is reflexive if and only if (a,a)∈R for every element a∈A ○ Written symbolically, R is reflexive if and only if ○ ∀x[x∈U→(x,x)∈R] • Note ○ If A = ∅ then the empty relation is reflexive vacuously. ○ That is the empty relation on an empty set is reflexive! • Example ○ The following relations on the integers are reflexive: § R_1={(a,b)│a≤b} § R_3={(a,b)│a=b or a=−b} § R_4={(a,b)│a=b} ○ The following relations are not reflexive: § R_2={(a,b)│a b} (note that 3 ≯ 3) § R_5={(a,b)│a=b+1} (note that 3 ≠ 3 + 1) § R_6={(a,b)│a+b≤3} (note that 4+4≰3) Antireflexive Relations • Definition ○ R is antireflexive if and only if (a,a)∉R for every element a∈A ○ Written symbolically, R is antireflexive if and only if ○ ∀x[x∈U→(x,x)∉R] • Note ○ Antireflexive is different from not reflexive • Example ○ The following relations on the integers are antireflexive § R_2={(a,b)│a b} § R_5={(a,b)│a=b+1} ○ R_6={(a,b)│a+b≤3} is neither reflexive nor antireflexive Symmetric Relations • Definition ○ R is symmetric if and only if (b,a)∈R whenever (a,b)∈R,∀a,b∈A ○ Written symbolically, R is symmetric if and only if ○ ∀x∀y[(x,y)∈R→(y,x)∈R] • Example ○ The following relations on the integers are symmetric: § R_3={(a,b)│a=b or a=−b} § R_4={(a,b)│a=b} § R_6={(a,b)│a+b≤3} ○ The following are not symmetric: § R_1={(a,b)│a≤b} (note that 3 ≤ 4, but 4 ≰ 3) § R_2={(a,b)│a b} (note that 4 3, but 3 ≯ 4) § R_5={(a,b)│a=b+1} (note that 4 = 3 + 1, but 3 ≠ 4 + 1) Antisymmetric Relations • Definition ○ R is antisymmetric if and only if a=b whenever (a,b),(b,a)∈R,∀a,b∈A ○ Written symbolically, R is antisymmetric if and only if ○ ∀x∀y[(x,y)∈R∧(y,x)∈R→x=y] • Note ○ For any integer, if a≥b and a≤b, then a=b • Example ○ The following relations on the integers are antisymmetric: § R_1={(a,b)│a≤b} § R_2={(a,b)│a b} § R_4={(a,b)│a=b} § R_5={(a,b)│a=b+1} ○ The following relations are not antisymmetric: § R_3={(a,b)│a=b or a=−b} (note that (1,−1),(−1,1)∈R_3) § R_6={(a,b)│a+b≤3} (note that (1,2),(2,1)∈R_6) Transitive Relations • Definition ○ R is transitive if and only if (a,c)∈R whenever (a,b),(b,c)∈R, ∀a,b,c∈A ○ Written symbolically, R is transitive if and only if ○ ∀x∀y∀z[(x,y)∈R∧(y,z)∈R→(x,z)∈R] • Note ○ For every integer, a≤b and b≤c, then b≤c • Example ○ The following relations on the integers are transitive: § R_1={(a,b)│a≤b} § R_2={(a,b)│a b} § R_3={(a,b)│a=b or a=−b} § R_4={(a,b)│a=b} ○ The following are not transitive: § R_5={(a,b)│a=b+1} (note that (3,2),(4,3)∈R_5, but (3,3)∉R_5), § R_6={(a,b)│a+b≤3} (note that (2,1),(1,2)∈R_6, but (2,2)∉R_6). Combining Relations • Given two relations R_1 and R_2 • We can combine them using basic set operations to form new relations • Example ○ Let A={1,2,3} and B={1,2,3,4} ○ The relations R_1 = {(1,1),(2,2),(3,3)} and R_2 = {(1,1),(1,2),(1,3),(1,4)} can be combined using basic set operations to form new relations: ○ R_1 ∪ R_2 ={(1,1),(1,2),(1,3),(1,4),(2,2),(3,3)} ○ R_1 ∩ R_2 ={(1,1)} ○ R_1 − R_2 ={(2,2),(3,3)} ○ R_2 − R_1 ={(1,2),(1,3),(1,4)} Inverse • Definition ○ Let R be a relation from A to B ○ The inverse of R is the relation § R^(−1)={(a,b)│(b,a)∈R} • Proposition ○ R is symmetric if and only if R=R^(−1) Composition • Definition ○ Suppose § R_1 is a relation from a set A to a set B. § R_2 is a relation from B to a set C ○ Then the composition of R_2 with R_1 is a relation from A to C where § if (x,y) is a member of R_1 § and (y,z) is a member of R_2 § then (x,z) is a member of R_2∘R_1 • Example ○ R_2∘R_1={(b,x),(b,z)} Powers of a Relation • Definition ○ Let R be a binary relation on A ○ Then the powers R_n of the relation R can be defined inductively by: ○ Basis Step: R_1=R ○ Inductive Step: R_(n+1)=R_n∘R • The powers of a transitive relation are subsets of the relation • This is established by the following theorem: • Theorem 1 ○ The relation R on a set A is transitive iff R_n⊆R for n = 1,2,3… ○ (see the text for a proof via mathematical induction)](https://shawnzhong.com/wp-content/uploads/2018/04/img_5ad75495a5325.png)
