Equivalence RelationsIntroductionOutlineEquivalence relationsEquivalence relation exampleRosen, section 7.5, question 1Rosen, section 7.5, question 5Rosen, section 7.5, question 8A bit of humor…Equivalence classesMore on equivalence classesSlide 12PartitionsRosen, section 7.5, question 32What we wish computers could doQuick surveySlide 17Slide 1811Equivalence RelationsEquivalence RelationsAaron BloomfieldAaron BloomfieldCS 202CS 202Rosen, section 7.5Rosen, section 7.522 IntroductionIntroductionCertain combinations of relation properties are very Certain combinations of relation properties are very usefulusefulWe won’t have a chance to see many applications in this courseWe won’t have a chance to see many applications in this courseIn this set we will study equivalence relationsIn this set we will study equivalence relationsA relation that is reflexive, symmetric and transitiveA relation that is reflexive, symmetric and transitiveNext slide set we will study partial orderingsNext slide set we will study partial orderingsA relation that is reflexive, antisymmetric, and transitiveA relation that is reflexive, antisymmetric, and transitiveThe difference is whether the relation is symmetric or The difference is whether the relation is symmetric or antisymmetricantisymmetric33 OutlineOutlineWhat is an equivalence relationWhat is an equivalence relationEquivalence relation examplesEquivalence relation examplesRelated itemsRelated itemsEquivalence classEquivalence classPartitionsPartitions44 Equivalence relationsEquivalence relationsA relation on a set A relation on a set AA is called an is called an equivalence equivalence relationrelation if it is reflexive, symmetric, and transitive if it is reflexive, symmetric, and transitiveThis is definition 1 in the textbookThis is definition 1 in the textbookConsider relation Consider relation RR = { ( = { (a,ba,b) | ) | lenlen((aa) = ) = lenlen((bb) }) }Where Where lenlen((aa) means the length of string ) means the length of string aaIt is reflexive: It is reflexive: lenlen((aa) = ) = lenlen((aa))It is symmetric: if It is symmetric: if lenlen((aa) = ) = lenlen(b), then (b), then lenlen((bb) = ) = lenlen((aa))It is transitive: if It is transitive: if lenlen((aa) = ) = lenlen(b) and (b) and lenlen(b) = (b) = lenlen(c), (c), then then lenlen(a) = (a) = lenlen(c)(c)Thus, Thus, RR is a equivalence relation is a equivalence relation55 Equivalence relation exampleEquivalence relation exampleConsider the relation Consider the relation RR = { ( = { (a,ba,b) | ) | aa ≡ ≡ bb (mod (mod mm) }) }Remember that this means that Remember that this means that mm | | a-ba-bCalled “congruence modulo Called “congruence modulo mm””Is it reflexive: (a,a) Is it reflexive: (a,a)  RR means that means that mm | | a-aa-aa-aa-a = 0, which is divisible by = 0, which is divisible by mmIs it symmetric: if (Is it symmetric: if (a,ba,b) )  RR then ( then (b,ab,a) )  RR((a,ba,b) means that ) means that mm | | a-ba-bOr that Or that kmkm = = a-ba-b. Negating that, we get . Negating that, we get b-ab-a = - = -kmkmThus, Thus, mm | | b-ab-a, so (b,a) , so (b,a)  RRIs it transitive: if (Is it transitive: if (a,ba,b) )  RR and ( and (b,cb,c) )  RR then ( then (a,ca,c) )  RR((a,ba,b) means that ) means that mm | | a-ba-b, or that , or that kmkm = = a-ba-b((b,cb,c) means that ) means that mm | | b-cb-c, or that , or that lmlm = = b-cb-c((a,ca,c) means that ) means that mm | | a-ca-c, or that , or that nmnm = = a-ca-c Adding these two, we get Adding these two, we get km+lm km+lm = (= (a-ba-b) + () + (b-cb-c))Or (Or (k+lk+l))mm = = a-ca-cThus, Thus, mm divides divides a-ca-c, where , where nn = = k+lk+lThus, congruence modulo Thus, congruence modulo mm is an equivalence relation is an equivalence relation66 Rosen, section 7.5, question 1Rosen, section 7.5, question 1Which of these relations on {0, 1, 2, 3} are equivalence Which of these relations on {0, 1, 2, 3} are equivalence relations? Determine the properties of an equivalence relations? Determine the properties of an equivalence relation that the others lackrelation that the others lacka)a){ (0,0), (1,1), (2,2), (3,3) }{ (0,0), (1,1), (2,2), (3,3) }Has all the properties, thus, is an equivalence relationHas all the properties, thus, is an equivalence relationb)b){ (0,0), (0,2), (2,0), (2,2), (2,3), (3,2), (3,3) }{ (0,0), (0,2), (2,0), (2,2), (2,3), (3,2), (3,3) }Not reflexive: (1,1) is missingNot reflexive: (1,1) is missingNot transitive: (0,2) and (2,3) are in the relation, but not (0,3)Not transitive: (0,2) and (2,3) are in the relation, but not (0,3)c)c){ (0,0), (1,1), (1,2), (2,1), (2,2), (3,3) }{ (0,0), (1,1), (1,2), (2,1), (2,2), (3,3) }Has all the properties, thus, is an equivalence relationHas all the properties, thus, is an equivalence relationd)d){ (0,0), (1,1), (1,3), (2,2), (2,3), (3,1), (3,2) (3,3) }{ (0,0), (1,1), (1,3), (2,2), (2,3), (3,1), (3,2) (3,3) }Not transitive: (1,3) and (3,2) are in the relation, but not (1,2)Not transitive: (1,3) and (3,2) are in the relation, but not (1,2)e)e){ (0,0), (0,1) (0,2), (1,0), (1,1), (1,2), (2,0), (2,2), (3,3) }{ (0,0), (0,1) (0,2), (1,0), (1,1), (1,2), (2,0), (2,2), (3,3) }Not symmetric: (1,2) is present, but not (2,1)Not symmetric: (1,2) is present, but not (2,1)Not transitive: (2,0) and (0,1) are in the relation, but not (2,1)Not transitive: (2,0) and (0,1) are in the relation, but not (2,1)77 Rosen, section 7.5, question 5Rosen, section 7.5, question 5Suppose that Suppose that AA is a non-empty set, and is a non-empty set, and ff is a function is a function that has that has AA as its domain. Let as its domain. Let RR be the relation on be the relation on AA consisting of all ordered pairs (consisting of all ordered pairs (x,yx,y) where ) where ff((xx) = ) = ff((yy))Meaning that Meaning that xx and and yy are related if and only if are related if and only if ff((xx) = ) = ff((yy))Show that Show that RR is an equivalence relation on is an equivalence relation on AAReflexivity: Reflexivity: ff((xx) = ) = ff((xx))True, as given the same input, a function always produces the True, as given the same input, a function always produces the same outputsame outputSymmetry: if