Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Equivalence RelationSlide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Take X and Y to be the set of real numbersXYx=yThis subset specifies the relation y >= xXYx2 + y2 =1 This subset specifies the relation x2 + y2 <=1Student InfoName UF_ID Major GPAJohn 1111-2221 Math 3.9Mary 2222-1111 CS 3.2Helen 2333-5555 CS 3.9Jean 5555-1234 Chemistry 3.8Relation TablesA simple example of a databaseColumns are attributes and each row is an element in a Cartesian product AxBxCxD (what are them?)Equivalence RelationA relation is an equivalence relation if it is reflexive, symmetric and transitive.= is an equivalent relation > and < are not equivalence relationThe relation (a, b and n are integers)a Ξ b (mod n) is an equivalence relation.a Ξ b (mod n) reads “a is congruent to b module n” (or a = b mod n).a Ξ b (mod n) if a- b divides n or a, b have the same remainder upon dividing by n.It is reflexive, symmetric and transitive.a Ξ a (mod n)a Ξ b (mod n) -> b Ξ a (mod n) a Ξ b (mod n) and b Ξ c (mod n) ->a Ξ c (mod n)ExampleR={ {1, 1}, {2, 1}, {3, 2}, {4, 3} }R2 = { {1, 1}, {2, 1}, {3, 1}, {4, 2} }R3 = { {1, 1}, {2, 1}, {3, 1}, {4, 1} }R4 = ?Theorem: The relation R is transitive if and only if Rn R for all n=1, 2, 3, …UProof: “if” part. (a, b), (b, c) are in R, then (a, c) is in R also.“only if” use induction. Suppose Rn is in R for n < = k Rn + 1 = Rn o R will be in R o R which is in