Honors Discrete Mathematics
Honors Discrete Mathematics MAD 2104
Popular in Course
Popular in Mathematics Discrete
This 17 page Class Notes was uploaded by Dino Corwin on Monday October 12, 2015. The Class Notes belongs to MAD 2104 at Florida Atlantic University taught by Jorge Viola-Prioli in Fall. Since its upload, it has received 14 views. For similar materials see /class/221637/mad-2104-florida-atlantic-university in Mathematics Discrete at Florida Atlantic University.
Reviews for Honors Discrete Mathematics
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/12/15
14EQUIVALENCE RELATIONS An important type of relation on a set A is given next A relation R on a set A is called an equivalence relation if it satis es simultaneously these three properties 1 R is re exive that is aRa for every a E A 2 R is symmetric that is whenever aRb we have bRa 3 R is transitive that is whenever aRb ancl bRc we have aRc J Viola Prioli Let us see some examples a In AZ de ne aRb ifa divides b This R is re exive and transitive but is not symmetric 2 divides 4 but 4 does not divide 2 Hence it is not an equivalence relation b In A N de ne aRb if a lt b This R is not re exive is not symmetric but is transitive Hence it is not an equivalence relation c In A 2X de ne BRC if B Q C This R is re exive and transitive But is not symmetric Hence it is not an equivalence relation d In AZ de ne aRb if b a lt 2 In other words two integers will be related by R if and only if they are at most 1 unit apart This R is re exive and symmetric but is not transitive Hence it is not an equivalence relation J Viola Prioli e Let A be the set of squares in the xyplane Two squares will be related by R if they have the same area This is an equivalence relation f Let A be the set of squares in the xyplane Two squares will be related by R if both have area equal to 2 square inches Although this R is symmetric and transitive it is not re exive because if a square has area 1 it is not related to itself Hence it is not an equivalence relation g In A N de ne aRb if the sum of the digits of a equals the sum of the digits of b or if a divides b For instance 35R26 and 4R16 This R is re exive but is not symmetric since 2 divides 4 but 4 does not divide 2 The relation is not transitive since 2R24 because 2 divides 24 24R51 because the sum of the digits in both cases evaluates to 6 but 2 is not related to 51 because neither 2 divides 51 nor the sum of digits coincide Recall that the negation ofOR is AND Hence it is not an equivalence relation J Viola Prioli h Let A be the set of squares in the xyplane Two squares will be related by R if they have a common side This R is re exive and symmetric However it is not transitive why Hence it is not an equivalence relation Refer to the de nition of equivalence relation to rephrase it in terms of pairs R re exive means that for every a in A the pair a a is in the relation R symmetric means that whenever the pair a b is in the relation so is the pair b a R transitive means that whenever the pairs a b and b c are in the relation so is the pair a c J Viola Prioli Another practical representation emerges when we use connectors inclicate with a path from a to b that aRb In this visualization R re exive means that for every a in A we have a loop from a to a R symmetric means that whenever there is a path from a to b there is also a path from b to a R transitive means that whenever there is a path from a to b and also a path from b to c then there is a path from a to c As the course progresses we will make use of a fundamental equivalence relation on the set of integers Here is its de nition J Viola Prioli Let n gt 0 be a xed integer In 2 de ne ny if n divides xv Observe that accordingly x and y are related if they differ in a multiple of n that is in their representation on a line we can go from x to y by one or more iumps of length n each The relation just de ned is called the congruence mod n Hence we say that two numbers are congruent mod n if their di 39erence is a multiple of n The symbol for this relation is a and the complete notation is x a y mod n summing up x a y mod n is read as quotx is congruent to y mod n and means x y is a multiple of n J Viola Prioli For instance we have 17 a 9 mod 4 because 17 9 8 a multiple of 4 Likewise 13 a 11 mod 4 because 13 11 24 a multiple of4 TH The congruence mod n is an equivalence relation on Z Proof We leave the rst two properties as an exercise Let us show here that the relation is transitive So assume aRb ancl bRc This translates into a a b mod n and b a c mod n We need to show that aRc that is a a c mod n J Viola Prioli We have a statement ofthe form quotif A then B where A means a a b mod n and b a c mod n and B means a E c mod n Unravel A a a b mod n means a b ns for some integer s b a c mod n means b c nt for some integer t Unravel B a E c mod n means a c nw for some integer w J Viola Prioli The link from A to B follows add the two equalities in A and get a b b c ns nt nst The left hand side equals a c Hence a c nst Therefore we just call w st and arrive to B the congruence mod 2 is a particular important case Observe that a a b mod 2 means a and b are separated by a multiple of 2 and this is equivalent to saying that either a and b are both even or a and b are both odd numbers Hence a a b mod 2 ltgt a and b even or a and b odd Returning to the general case of an equivalence relation R on a set A we de ne for every a in A the equivalence class of a as the set of elements of A related to a The equivalence class of a is denoted by a Thus a x E A xRa J Viola Prioli Observe that since R is symmetric we could have written it as well as a x E A aRx In words the equivalence class of a is the set of elements with quotsame attribute as a under the given relation R EXAMPLES a In N de ne ny ifthe sum of their digits coincide This is an equivalence relation Verify this Let us nd the class of 2 that is 2 We have 2 x39 the digits of x are one 2 and 0 s or two 1 s and 0 s This can be written simply as 2 10k 10139 with kj 2 0 Exercise As an illustration we have 10010 104 101 2 100 100 and 2000 103 103 J Viola Prioli b Let A be the set of subsets of 3 4 5 On A declare two sets related if they have the same size This is an equivalence relation Exercisel The class of the set 3 5 is made up of 3 5 3 4 and 4 5 c Take a a b mod 2 on Z The class of 1 is 1 x39 x is odd and 2 y39 y is even Observe that the class of 3 coincides with 1 because mR3 if and only if m a 3 mod 2 by de nition of congruence and since 3 is odd m must be so d Take a a b mod 3 on Z We therefore have 0 3k39 with kE Z 1 1 3k with kE Z 22 3k with k E Z There are no more classes since they start repeating To be precise 036 etc147 etc 258 etC J Viola Prioli Here are some basic results regarding the classes If R is an equivalence relation on a set A and a E A then a E a Proof In plain words the statement asserts that a belongs to the class of a This is obvious because R is re exive and so aRa That is a E a If R is an equivalence relation on A and a and b are elements of A then b E a lt9 ab Proof In plain words the statement asserts that if a is related to b if and only ifthey produce the very same equivalence class gt B E a implies that bRa by de nition of a To see that ab we must show two facts a Q b and b Q a J Viola Prioli For a Q b we pick x E a so xRa Since bRa then aRb symmetry Hence we have xRa and aRb Therefore xRbtransitive and so x E b We have proved that a Q b For b Q a pick any y E b so be Since bRa then yRa transitive Thus y E a We have proved that b Q a In conclusion ab lt Obvious In fact since R is re exive bRb so b E b By hypothesis ab so b E a as desired The proposition has been proved completely Let R be an equivalence relation on a set A Then any two different equivalence classes are disjoint Proof Observe that the statement claims that two classes are either equal or they are disjoint J Viola Prioli Suppose for sake of a contradiction that two classes a and b are distinct but are disjoint Hence we can pick an element 2 E a D b Therefore zRa and also sz Thus aRz and sz Since R is transitive we have aRb By the previous proposition a b a contradiction We have already at our disposal to present the following If R is an equivalence relation on a set A then the equivalence classes satisfy the following three conditions a they are non empty b they are pairwise disjoint c their union is the set A J Viola Prioli Proof a aRa for every a in A Hence in particular this implies that a E a so a is non empty b This is our previous proposition c This is clear since a E a for every a in A What is the signi cance of this result First of all let us illustrate it by referring to examples c and cl above In c we have A Z and just two equivalence classes 0 even numbers and 1odd numbers They are non empty they do not intersect and their union is Z J Viola Prioli In example d we dealt with A Z and congruence mod 3 We found three equivalence classes 0 1 and 2 Review our computations which showed that there were no more classes We see that they are non empty and they are pairwise disjoint Let us see that their union is Z Take any integer 2 Reduce it mod 3 Therefore 2 3q r with r O 1 or 2 In the rst case 2 3q so 2 E O In the second case 2 3q 1 so 2 E 1 and nally if r 2 z 3q 2 and so 2 E 2 We have veri ed that the union of the three equivalence classes is Z as asserted in our theorem Our theorem thus states that the distinct classes associated to a given equivalence relation quotpartitionquot or fragment the set A into blocks that are disjoint and that when put together reconstruct the original set A Of course even if A is kept xed we can de ne di erent equivalence relations on it Each relation will partition A in a different way as we saw above in the examples c and d J Viola Prioli Terminology is important so please be precise when using it Notice the difference between equivalence relation equivalence class equivalent or related elements Observe that quotthis element is re exive makes no sense quotthe relation is re exive does Likewise quota is re exive with a is a non sense a is related to a is the proper statement Please review the de nitions with extra care In our next section we will discuss more deeply the notion of partition IMPORTANT See the additional illustrations given in Section 14 Syllabus J Viola Prioli