L14-Relations_2

Relations (cont.) CSE 215, Computer Science 1, Fall 2011 Stony Brook UniversityStony Brook University http://www.cs.stonybrook.edu/~cse215 Equivalence Relations  The Relation Induced by a Partition: given a partition of a set A, the relation induced by the partition, R, is defined on A as A, the relation induced by the partition, R, is defined on A as follows: for all x, y A, x R y there is a subset Ai of the partition such that both x and y are in Ai.  Example: Let A = {0, 1, 2, 3, 4} and consider the following partition of A: {0, 3, 4}, {1}, {2}. 0 R 3 because both 0 and 3 are in {0, 3, 4} 1 R 1 because both 1 and 1 are in {1}{ } { } 3 R 0 because both 3 and 0 are in {0, 3, 4} 2 R 2 because both 2 and 2 are in {2} 0 R 4 because both 0 and 4 are in {0, 3, 4} R = {(0, 0), (0, 3), (0, 4), (1, 1), (2, 2), 4 R 0 because both 4 and 0 are in {0, 3, 4} (3, 0), (3, 3), (3, 4), (4, 0), 3 R 4 because both 3 and 4 are in {0, 3, 4} (4, 3), (4, 4)}. 4 R 3 because both 4 and 3 are in {0, 3, 4} 0 R 0 because both 0 and 0 are in {0, 3, 4} 3 R 3 because both 3 and 3 are in {0 3 4} (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 3 R 3 because both 3 and 3 are in {0, 3, 4} 4 R 4 because both 4 and 4 are in {0, 3, 4} 2 The Relation Induced by a Partition  Let A be a set with a partition and let R be the relation induced by the partition. Then R is reflexive, symmetric, and induced by the partition. Then R is reflexive, symmetric, and transitive. Proof: Suppose A is a set with a partition (finite): A1,A2,...,An Ai∩Aj= whenever i = j and A1 A2 ··· An = A. For all x, y A, x R y there is a set Ai of the partition such that x Ai and y Ai. Proof that R is reflexive: Suppose x A. Since A1,A2,...,An i i i f A A A A A i f ll h Ais a partition of A, A1 A2 ··· An = A, it follows that x Ai for some i. There is a set A of the partition such that x A (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) There is a set Ai of the partition such that x Ai. By definition of R, x R x. 3 The Relation Induced by a Partition Proof that R is symmetric: Suppose x and y are elements of A such that x R y. Then there is a subset Ai of the partition A such that x R y. Then there is a subset Ai of the partition such that x Ai and y Ai by definition of R. It follows that the statement there is a subset Ai of the partition such that y Ai and x Ai is also true. By definition of R, y R x. (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 4 The Relation Induced by a Partition Proof that R is transitive: Suppose x, y, and z are in A and xRy and yRz. By definition of R, there are subsets Ai and Aj of xRy and yRz. By definition of R, there are subsets Ai and Aj of the partition such that x and y are in Ai and y and z are in Aj. Suppose Ai = Aj . [We will deduce a contradiction.] Then j Ai∩Aj= since {A1, A2, A3,..., An} is a partition of A. But y is in Ai and y is in Aj also. Hence Ai∩Aj= . [This contradicts the fact that A∩A = ] Thus A =A It follows that x y and z the fact that Ai∩Aj= .] Thus Ai=Aj. It follows that x, y, and z are all in Ai, and so in particular, x and z are in Ai. Thus, by definition of R, x R z., y , . (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 5 Equivalence Relation  Let A be a set and R a relation on A. R is an equivalence relation R is reflexive, symmetric, and transitive  Example: X = {{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}} A relation R on X: A R B ֞ the least element of A equals the least element of Bq R is an equivalence relation on X: R is reflexive: Suppose A is a nonempty subset of {1, 2, 3}[We must show that A R A] By definition of R A R A : the least element of A equals the least element of ABy definition of R, A R A : the least element of A equals the least element of A. R is symmetric: Suppose A and B are nonempty subsets of {1, 2, 3} and A R B. [We must show that B R A] By A R B, the least element of A equals the least element of B. Thus, by symmetry of equality, B R A.by symmetry of equality, B R A. R is transitive: Suppose A, B, and C are nonempty subsets of {1, 2, 3}, A R B, and B R C. [We must show that A R C.] By A R B, the least element of A equals the least element of B B B R C th l t l t f B l th l t l t f C (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) By B R C, the least element of B equals the least element of C. By transitivity of equality, the least element of A equals the least element of C: A R C. 6 Equivalence Classes  Let A be a set and R an equivalence relation on A. For each element a in A, the equivalence class of a (the class of a) is the set element a in A, the equivalence class of a (the class of a) is the set of all elements x in A such that x is related to a by R. [a] = {x A |x R a}  Example: Let A = {0, 1, 2, 3, 4} and R be a relation on A: R = {(0, 0),(0, 4),(1, 1),(1, 3),(2, 2),(3, 1),(3, 3),(4,0),(4,4)} R is an equivalence relation [0] = {x A |x R 0} = {0, 4}=[4] [1] = {x A |x R 1} = {1, 3}=[3] [2] = {x A |x R 2} = {2} (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) {0, 4}, {1, 3} and {2} are distinct equivalence classes 7 Equivalence Classes of a Relation on a Set of Subsets  X = {{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}} A R B th l t l t f A l th l t l t f BA R B the least element of A equals the least element of B [{1}] = {{1},{1,2},{1,3},{1,2,3}}=[{1,2}]=[{1,3}]=... [{2}] = {{2} {2 3}} =[{2 3}][{2}] = {{2}, {2, 3}} =[{2, 3}] [{3}] = {{3}} (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 8 Equivalence Classes of the Identity Relation  Let A be any set and R a relation on A: For all x and y in A, x R y x = yx R y x = y Given any a in A, the class of a is: [a] = {x A |x R a} = {a} since the only element of A that equals a is a.y q (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 9 Equivalence Relations  Let A be a set and R an equivalence relation on A. For any a and b elements of A if a R b then [a] = [b]For any a and b elements of A, if a R b, then [a] = [b]. Proof: [a] = [b]  [a] [b] and [b] [a]. 1 [a] [b] 1. [a] [b] Let x [a] iff then x R a. a R b by hypothesis  by transitivity of R x R b  x [b]a R b by hypothesis  by transitivity of R, x R b  x [b] 2. [b] [a] Let x [b] iff then x R b.[ ] b R a by hypothesis and symmetry  by transitivity of R, xRa x [a] (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 10 Equivalence Relations  If A is a set, R is an equivalence relation on A, and a and b are elements of A, then either [a] ∩ [b] = or [a] = [b].elements of A, then either [a] ∩ [b] or [a] [b]. Proof: Suppose A is a set, R is an equivalence relation on A, a and b are pp , q , elements of A, and [a] ∩ [b] = . [We must show [a] = [b]] Since[a]∩[b]= ,there exists an element x in A s.t. x [a]∩[b]  x [a] and x [b]  so x R a and x R b By symmetry and transitivity, a R b  [a] = [b].  If A is a set and R is an equivalence relation on A, then the distinct equivalence classes of R form a partition of A: the union of the equivalence classes is all of A and the (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) union of the equivalence classes is all of A, and the intersection of any two distinct classes is empty. 11 Congruence Modulo 3  Let R be the relation of congruence modulo 3 on the set Z of all integers: for all integers m and n, m R n 3 | (m − n) m ≡ n (mod 3). Solution For each integer a, [ ] { אZ| 3|( )} { אZ| 3k f i k}[a] ={xאZ| 3|(x−a)} ={xאZ|x−a=3k, for some integer k} = {x א Z | x = 3k + a, for some integer k}. [0] = {x א Z| x = 3k + 0 for some int k}= {x א Z| x=3k}[0] {x א Z| x 3k + 0, for some int k} {x א Z| x 3k} ={...− 9,−6,−3, 0, 3, 6, 9,...}=[3]=[−3]=[6]=[−6]=... [1] = {x א Z| x = 3k + 1, for some integer k}[ ] { | , g } ={...− 8,−5,−2, 1, 4, 7, 10,...}=[4] = [−2] = [7] =[−5]=... [2] = {x א Z| x = 3k + 2, for some integer k} (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) ={...−4,−1, 2,...}= [5] = −1 = [8] = [−4] = ... 12 Congruence Modulo  Let m and n be integers and let d be a positive integer. m is congruent to n modulo d: m ≡ n (mod d) ֞ d | (m − n) Example: 12 ≡ 7 ( d 5) b 12 7 = 5 = 5 1  5 | (12 7)12 ≡ 7 (mod 5) because 12 − 7 = 5 = 5 · 1  5 | (12 − 7). (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 13 Rational Numbers Are Equivalence Classes  Let A be the set of all ordered pairs of integers for which the second element of the pair is nonzero: A = Z × (Z − {0})second element of the pair is nonzero: A Z (Z {0}) R is a relation on A: for all (a, b), (c, d) A, (a, b) R (c, d) ad = bc (a/b=c/d)( , ) ( , ) ( ) R is an equivalence relation Example equivalence class:p q (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 14 Antisymmetry  Let R be a relation on a set A. R is antisymmetricfor all a b A if aRb and bRa then a=bR is antisymmetricfor all a,b A, if aRb and bRa then a=b R i t ti t ith i t b A t Rb bR b t =bR is not antisymmetricthere exist a,b A s.t. aRb, bRa,but a=b 0 R 2 and 2 R 0 but 0=2 (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 0 R 2 and 2 R 0 but 0 2 15 Antisymmetry of “Divides” Relations  For all a, b Z+, a R1 b a | b. R i i i S b א Z+ h h R b d bR [W R1 is antisymmetric: Suppose a, b א Z+ such that aR1b and bR1a. [We must show that a = b] By definition of R1, a|b and b|ab=k1a and a=k2b, k1,k2א Z y 1, | | 1 2 , 1, 2 b=k1k2b Dividing both sides by b gives k1k2=1 k1=k2=1 a=b  For all a, b Z, a R2 b a | b. R2 is not antisymmetric: Counterexample: a = 2 and b = −2  a ≠ b a | b since−2 = (−1) · 2  a R2 b  (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) b | a since 2 = (−1)(−2)  b R2 a 16 Partial Order Relations  Let R be a relation defined on a set A. R is a partial order relationR is reflexive antisymmetric and transitiveR is a partial order relationR is reflexive, antisymmetric,and transitive  Example: The “Subset” Relation Let A be any collection of sets and ك (the “subset”) relation on A: y ( ) For all U, V אA, U كV ֞ for all x, if x א U then x אV. ك is a partial order (reflexive, transitive and antisymmetric) Proof that ك is antisymmetric: for all sets U and V in A if U كV and V ك U then U = V (by definition of equality of sets) (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 17 The “Less Than or Equal to” Relation  The “less than or equal to” relation ≤ on R (reals): for all x,y R x ≤ y x < y or x = y. ≤ is a partial order relation: ≤ is reflexive: x ≤ x for all real numbers. x ≤ x means that x < x or x = x, and x = x is always true. ≤ is antisymmetric: for all x,y R, if x ≤ y and y ≤ x then x = y. ≤ is transitive: for all x,y,z R, if x ≤ y and y ≤ z then x ≤ z. (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 18 Lexicographic Order  Order in an English dictionary: compare letters one by one from left to right in words.from left to right in words.  Let A be a set with a partial order relation R, and let S be a set of strings over A. is a relation on S:for any 2 strings in g y g S,a1a2...am and b1b2...bn, m,n Z+: 1. If m ≤ n and ai=bi for all i=1,2,...,m, then a1a2...am b1b2...bn 2. If for some integer k with k≤m, k≤n, and k≥1,ai=bi for all i=1,2,...,k−1, and ak≠bk, but akRbk then a1a2...am b1b2...bn. 3 If h ll d S h 3. If ε is the null string and s is any string in S, then ε s. If no strings are related other than by these three conditions, then is a partial order relation (lexicographic order for S) (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) is a partial order relation (lexicographic order for S). 19 Lexicographic Order  Let A = {x, y} and R the partial order relation on A: R = {(x x) (x y) (y y)}R = {(x, x), (x, y), (y, y)}. Let S be the set of all strings over A, and the lexicographic order for S that corresponds to R.p x xx x xy yxy yxyxxx x yy y y y y xx xyx xxxy xy ε x ε xyxyyxy yy (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 20 Hasse Diagrams  A Hasse Diagram is a simpler graph with a partial order relation defined on a finite set  Example: let A = {1, 2, 3, 9, 18} and the “divides” relation | on A: for all a, b אA, a | b ֞ b = ka for some integer k.  Start with a directed graph of the relation placing vertices on the page so that all arrows  Start with a directed graph of the relation, placing vertices on the page so that all arrows point upward. Eliminate: 1. the loops at all the vertices 2 all arrows whose existence is implied by the transitive property2. all arrows whose existence is implied by the transitive property 3. the direction indicators on the arrows (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 21 Hasse Diagrams  The “subset” relation ك on the set P({a, b, c}): for all sets U and V in P({a, b, c}) U كV ֞׊x, if x א U then x אV Draw the directed graph of the relation in such a way that all arrows except loops point upward. Strip away all loops, unnecessary arrows, and direction indicators to obtain the Hasse diagram. (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 22 Hasse Diagrams  Obtain the original directed graph from the Hasse diagram: 1. Reinsert the direction markers on the arrows making all arrows point upward. 2. Add loops at each vertex. 3. For each sequence of arrows from one point to a second and from that second point to a third, add an arrow from the first point to the third. (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 23 Partially and Totally Ordered Sets  Let be a partial order relation on a set A. Elements a and b of A are comparable either a b or b a. Otherwise, a d b bland b are noncomparable.  If R is a partial order relation on a set A, and any two elements a and b in A are comparable then R is a total order elements a and b in A are comparable, then R is a total order relation on A.  The Hasse diagram for a total order relation can be drawn as a single vertical “chain.”  A set A is called a partially ordered set (or poset) with respect to l ti  i ti l d l ti Aa relation  is a partial order relation on A.  A set A is called a totally ordered set with respect to a relation A is partially ordered with respect to and is a total (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) A is partially ordered with respect to and is a total order. 24 Partially and Totally Ordered Sets  Let A be a set that is partially ordered with respect to a relation . A subset B of A is called a p chain the elements in each pair of elements in B is comparable. p  The length of a chain is one less than the number of elements in the chain.  Example: Chain of Subsets The set P({a b c}) is partially ordered with The set P({a, b, c}) is partially ordered with respect to . Ch i f l h 3 { } { b } { b } (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) Chain of length 3: {a} {a, b,} {a, b, c} 25 Partially and Totally Ordered Sets  An element a in A is called a maximal element for all b in A, either bعa or b and a are not comparable.  An element a in A is called a greatest element of A  for all b in A, bعa.g , ع  An element a in A is called a minimal element for all b in A, either aعb or b and a are not comparable.  An element a in A is called a least element of A  for all b in A aعb An element a in A is called a least element of A  for all b in A, aعb.  Example:  one maximal element = g = also the greatest element  minimal elements c d and i (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook)  minimal elements: c, d and i  there is no least element 26 Topological Sorting  Given partial order relations and ’ on a set A, ’ is compatible with  for all a and b in A, if a b then a ’bcompatible with for all a and b in A, if a b then a b  Given partial order relations and ’ on a set A, ’ is a topological sorting for  ’ is a total order that is compatible with .  Example: P({a, b, c}) with partial order Total order: , {a},{b},{c},{a, b}, {a, c}, {b, c}, {a, b, c} (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 27 Topological Sorting  Constructing a Topological Sorting: 1 Pick any minimal element x in A with respect to 1. Pick any minimal element x in A with respect to . [Such an element exists since A is nonempty.] 2 Set A’ = A − {x}2. Set A A {x} 3. Repeat steps a–c while A’ ≠ : a. Pick any minimal element y in A’.y y b. Define x ع’ y. c. Set A’ = A’−{y} and x = y. (c) 2010 Cengage Learning & P.Fodor (CS Stony Brook) 28