Honors Discrete Mathematics
Honors Discrete Mathematics MAD 2104
Popular in Course
Popular in Mathematics Discrete
This 6 page Class Notes was uploaded by Chaya Botsford II 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 22 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
13RELATIONS Given two sets A and B we wish to pair some elements of A with some elements of B in a certain way according to a rule we establish The end result will then be a set of ordered pairs a b with a in A and b in B When a is paired to b we say quota is related to b or that the ordered pair ab satis es the relation A relation R from A to B is any non empty subset of A x B Therefore ab E R indicates that a is related to b We simplify the notation by writing aRb instead which is read quota is related to b through the relation R speci ed in each case J Viola Prioli When AB we refer to quotrelations on A instead of saying quotrelations from A to A Let us see some examples of relations EXAMPLES 1 Let A 1 2 3 B 1 2 4 and de ne R from A to B as follows declare aRb if and only if a lt b 1 Let us list the pairs of the relation to begin with who is related to 1 Only 2 and 4 so we have the pairs 1 2 1 4 Do the same with 2 get 2 2 and 2 4 And with 3 we obtain 3 4 So the pairs are 1 2 1 4 2 2 2 4 3 4 Notice that although 0 4 satis es a lt b1 the pair 0 4 is not in R because 0 i A Notice also that although 1 1E A x B 1 1 R since 1 is not related to 1 J Viola Prioli 2 Consider A 1 2 9 10 and declare a relation in A as follows aRb if a divides b and a t b An easy calculation shows that R 2 42 62 82 10 3 6 3 9 4 8 5 10 Notice for instance that 7 is not related to any number 3 Consider A 1 2 9 10 and declare a relation in A as follows aRb if a divides b g a gt b We see that 1 is related to any number So 1Rb for all b in A Let us consider 2 2R1 because 2gt139 2R2 because 2 divides 2 Likewise 2R4 2R6 2R8 and 2R10 With 3 We have 3R1 3R23R3 3R6 3R9 With 4 4R1 4R2 4R3 4R4 4R8 With 5 5R15R25R35R45R55R10 Likewise 6Rn for all n16 7Rn for all n1 7 8Rn for all n 1 8 9Rn for all n 1 9 10Rn for all n in A It is worth noticing that in this relation we have 4 related to 3 but 3 is not related to 4 J Viola Prioli 4 Let A 1 2 and B 2A Q 1 2 1 2 Notice that A x B consists of pairs with rst component is a number 1 or 2 and second component one ofthe four sets in B Consider the following relation from A to B the pair a X is in R if a is an element of the set X Thus we have 1R1 1R12 2R2 and 2R12 5 Let A and B be as in 4 This time we de ne a relation on B Observe that the pairs are of the form XY with X and Y subsets of 12 We set XRY if x Y Thus RQ 1R1 1R2 12R12 Summing up as you could see in the examples above and also from the very de nition of relation one has ample freedom to de ne a relation Some relations may turn out to be of interest whereas some others might be irrelevant In fact we can easily see how many relations from A to B we can construct They will be many J Viola Prioli So assume A m and B n Therefore IA x B mn Since the number of subsets of A x B is 2 quot and the only subset we can not consider in a relation is the empty set see the de nition of relation we end up with 2mn 1 relations In conclusion of relations from an melement set to an nelement set is 2mn 1 Given a relation from A to B we can de ne a relation from B to A by simply reversing the ordered pairs of R This is called the inverse relation denoted by R39l Of course since R Q A x B we have that R391 Q BxA J Viola Prioli Three of the most important types of relations are the equivalence relations the order relations and the functions We will explore next the rst type J Viola Prioli