Report

Equivalence Relations: Selected Exercises Equivalence Relation • Let E be a relation on set A. • E is an equivalence relation if & only if it is: – Reflexive – Symmetric – Transitive. • Examples – a E b when a ≡ b ( mod 5 ). (Over N) – a E b when a is a sibling of b. (Over humans) Copyright © Peter Cappello 2 Equivalence Class • Let E be an equivalence relation on A. • We denote aEb as a ~ b. (sometimes, it is denoted a ≡ b ) • The equivalence class of a is { b | a ~ b }, denoted [a]. • What are the equivalence classes of the example equivalence relations? • For these examples: – Do distinct equivalence classes have a non-empty intersection? – Does the union of all equivalence classes equal the underlying set? Copyright © Peter Cappello 3 Partition A partition of set S is a set of nonempty subsets, S1, S2, . . ., Sn, of S such that: 1. i j ( i ≠ j Si ∩ Sj = Ø ). 2. S = S1 U S2 U . . . U Sn. Copyright © Peter Cappello 4 Equivalence Relations & Partitions Let E be an equivalence relation on S. • Thm. E’s equivalence classes partition S. • Thm. For any partition P of S, there is an equivalence relation on S whose equivalence classes form partition P. Copyright © Peter Cappello 5 E’s equivalence classes partition S. 1. [a] ≠ [b] [a] ∩ [b] = Ø. Proof by contradiction: Assume [a] ≠ [b] [a] ∩ [b] ≠ Ø: (Draw a Venn diagram) Without loss of generality, let c [a] - [b]. Let d [a] ∩ [b]. We show that c [b] (which contradicts our assumption above) 2. 1. c ~ d ( c, d [a] ) 2. d ~ b ( d [b] ) 3. c ~ b ( c ~ d d ~ b E is transitive ) The union of the equivalence classes is S. Students: Show this use pair proving in class. Copyright © Peter Cappello 6 For any partition P of S, there is an equivalence relation whose equivalence classes form the partition P. Prove in class. 1. Let P be an arbitrary partition of S. 2. We define an equivalence relation whose equivalence classes form partition P. (Students: Show this (use pair proving) in class) Copyright © Peter Cappello 7 Exercise 40 a) What is the equivalence class of (1, 2) with respect to the equivalence relation given in Exercise 16? Exercise. 16: Ordered pairs of positive integers such that ( a, b ) ~ ( c, d ) ad = bc. Copyright © Peter Cappello 8 Exercise 40 a) Answer ( a, b ) ~ ( c, d ) ad = bc a/b = c/d [ ( 1, 2 ) ] = { ( c, d ) | ( 1, 2 ) ~ ( c, d ) } = { ( c, d ) | 1d = 2c c/d = ½ }. Copyright © Peter Cappello 9 Exercise 40 continued b) Interpret the equivalence classes of the equivalence relation R in Exercise 16. Copyright © Peter Cappello 10 Exercise 40 continued b) Interpret the equivalence classes of the equivalence relation R in Exercise 16. Answer Each equivalence class contains all (p, q), which, as fractions, have the same value (i.e., the same element of Q+). (The fact that 3/7 = 15/35 confuses some small children.) Copyright © Peter Cappello 11 Exercise 50 • A partition P’ is a refinement of partition P when x P’ y P x y. (Illustrate.) • Let partition P consist of sets of people living in the same US state. • Let partition P’ consist of sets of people living in the same county of a state. • Show that P’ is a refinement of P. Copyright © Peter Cappello 12 Exercise 50 continued It suffices to note that: Every county is contained within its state: No county spans 2 states. Copyright © Peter Cappello 13 Exercise 62 Determine the number of equivalent relations on a set with 4 elements by listing them. How would you represent the equivalence relations that you list? Copyright © Peter Cappello 14 End 8.5 Copyright © Peter Cappello 15 10 Suppose A & R is an equivalence relation on A. Show f X f: A X such that a ~ b f( a ) = f( b ). Proof. 1. Let f : A X, where 1. X = { [a] | [a] is an equivalence class of R } 2. a f (a ) = [a]. 2. Then, a b a ~ b f( a ) = [a] = [b] = f( b ). Copyright © Peter Cappello 16 Exercise 20 • Let P be the set of people who visited web page W. • Let R be a relation on P: xRy x & y visit the same sequence of web pages since visiting W until they exit the browser. • Is R an equivalence relation? • Let s( p ) be the sequence of web pages p visits since visiting W until p exits the browser. Copyright © Peter Cappello 17 Exercise 20 continued • That is, xRy means s( x ) = s( y ). • x xRx: R is reflexive. Since x s( x ) = s( x ). • x y ( xRy yRx ): R is symmetric. Since s( x ) = s( y ) s (y ) = s( x ). • x y z ( ( xRy yRz ) xRz ): R is transitive. Since ( s( x ) = s( y ) s( y ) = s( z ) ) s( x ) = s( z ). • Therefore, R is an equivalence relation. Copyright © Peter Cappello 18 Exercise 30 What are the equivalence classes of the bit strings for the equivalence relation of Exercise 11? Ex. 11: Let S = { x | x is a bit string of ≥ 3 bits. } Define xRy such that x agrees with y on the left 3 bits (e.g., 10111 ~ 101000). a) 010 b) 1011 c) 11111 d) 01010101 Copyright © Peter Cappello 19 Exercise 30 Answer • 010 (answer: all strings that begin with 010) • 1011 (answer: all strings that begin with 101) • 11111 (answer: all strings that begin with 111) • 01010101 (answer: all strings that begin with 010) How many equivalence classes are there? Copyright © Peter Cappello 20