Report

CSE 20 DISCRETE MATH Prof. Shachar Lovett http://cseweb.ucsd.edu/classes/wi15/cse20-a/ Clicker frequency: CA Todays topics • Equivalence relations • Section 6.2 in Jenkyns, Stephenson (Binary) Relations • Model a relation between two families of objects • Formally: • U universe set • Relation: ⊆ × • For , ∈ we write: as a shorthand for "(, ) ∈ “ • Example 1: x<y, formally… • U=N • “ < ” represents the relation = , : , ∈ , < • Example 1: x<y, formally… • U = P(N) • “ ⊂ ” represents the relation = { , : , ∈ (), ⊂ } Three important properties of relations • There are several important properties of relations • We will focus on the most important three • A relation R is symmetric if ∀, , ⇔ • A relation R is reflexive if ∀, • A relation R is transitive if ∀, , , ∧ → • An equivalence relation is a relation which satisfies all of them Examples of equivalence relations • U=Z (integers) • xRy = “x=y” Prove that R is an equivalence relation Examples of equivalence relations • U=Z (integers) • xRy = “|x|=|y|” (absolute value of x = absolute value of y) Prove that R is an equivalence relation Examples of equivalence relations • U=“all students in this class” • xRy = “x and y have the same birthday” Prove that R is an equivalence relation Examples of equivalence relations • U=Z (integers) • xRy = “x+y is even” Prove that R is an equivalence relation What is so special about equivalence relations? • Equivalence relations describe a partition of the universe U to equivalence classes Equivalence classes • Let 1 , 2 , … , be a partition of U • For ∈ , define to be the (unique!) part that x belongs to • Equivalently, define : → {1, … , } and equivalence classes are defined by all elements with same image = { ∈ : = } • Theorem: let ⊆ × be an equivalence relation. Then there is a mapping : → such that ∀, ∈ , ⇔ = () Equivalence classes: example 1 • U=Z (integers) • xRy = “x=y” Class(x)= A. x B. y C. U D. “x=y” E. Other Equivalence classes: example 2 • U=Z (integers) • xRy = “|x|=|y|” Class(x)= A. x B. |x| C. “x=y” D. “|x|=|y|” E. Other Equivalence classes: example 3 • U=“all students in this class” • xRy = “x and y have the same birthday” Class(x)= A. x B. Birthday of x C. “x=y” D. “|x|=|y|” E. Other Equivalence classes: example 4 • U=Z (integers) • xRy = “x+y is even” Class(x)=??? Figure this out in your groups Equivalence classes: proof • Theorem: let ⊆ × be an equivalence relation. Then there is a mapping : → such that ∀, ∈ , ⇔ = () Proof: For each ∈ , define: Class = { ∈ : } (and so = : ∈ ⊂ () ) We need to show that ∀, ∈ , ⇔ = () Equivalence classes: proof (contd) For each ∈ , define: Class = { ∈ : } (⇐) Assume Class = (). We will show xRy. By definition: we need to show ∈ (). But ∈ since R is reflexive (and so )) and since we assume Class = () then also ∈ (). Equivalence classes: proof (contd) For each ∈ , define: Class = { ∈ : } (⇒) Assume xRy. We need to show Class = (). We will first show ⊆ (). Let ∈ . Then y. Since R is transitive, ∧ imply that x. So ∈ (). Since R is symmetric, we also have yRx. The same argument as above (with the roles of x,y reversed) then implies that ⊆ (). So: = (). Next class • Modular arithmetic • Section 6.2 in Jenkyns, Stephenson • Review session for midterm 2