Today s topics The notion of a relation properties of relations on a set Relations A relation is a fundamental mathematical notion expressing a relationship between sets It s an abstract notion useful for modeling many different relationships 1 Example Let S be set of UCF students and C be a set of classes Then we can consider the relation is taking class from S to C C S x y This relation can be described by the set of pairs is taking class x y x S y C and student x is taking class y 2 More examples of relations parent of child of likes meet one another today less then a b a b A and a b where A 1 2 10 equal a b a b Power A and a b subset a b a b Power A and a b If R is set of real numbers R R is set of points x y in plane circle x y x y R and x2 y2 1 3 You don t need to give a meaningful name to a relation The only thing that really matters about relations is that we know which elements in A are related to which element of B A relation R is completely described if we know R related pairs Suppose A 1 2 3 B r s and we know 1Rr 2Rs 3Rr then we know everything we need to know about R R can be specified by the list of pairs R 1 r 2 s 3 r The Cartesian product contains all possible pairs A B 1 r 1 s 2 r 2 s 3 r 3 s 4 Definition A binary relation from A to B is a subset R A B Conversely any subset of A B can be considered as a relation A binary relation on a set A is a relation from A to A R A A We can also define a ternary relation on A as a subset R A A A and in general an n ary relation as a subset R A1 A2 An if the sets Ai are different How many binary relations from A to B are there A B A B 2 A B subsets relations 5 Notation R A B a binary relation from a set A to a set B R a b a A b B and a is related to b in some way a b R aRb a is related to b by R a b R aRb a is not related to b by R R A A is a relation on A 6 If R A B is a relation from A to B there are two important sets associated with it Domain of R is subset of elements in A which are related to some element in B For relation F father from A set of living males to B living females the domain is the set of living males who have living daughters Range of R is the set of elements in B for which are second elements of pairs in R For the relation F the range is the set of living females who have living father 7 A relation can be represented as a matrix Let R A B A m B n then we can define the matrix mik with m rows and n columns 1 if ai bk R mik 0 if ai bk R Let A 1 2 3 B r s R 1 r 2 s 3 r A B Then the following matrix represents this relation r s MR 1 2 3 1 0 0 1 1 0 8 Consider the relation on A 1 2 3 4 5 represented by the following directed graph R A A 1 2 3 4 5 All edges of this graph correspond to related pairs R 1 1 1 2 2 2 2 3 3 3 4 4 4 5 5 5 What kind of relation is it R x y x y A and x y x 1 y 9 Properties of relations R A A Definition Let R A A be a binary relation on A 1 R is reflexive if for all a A aRa i e a a R In words each element of A is related to itself via R 2 R is irreflexive if for all a A a a R In words none of the elements in A is related to itself via R 3 R is symmetric if aRb implies bRa i e for all a b R b a R In words whenever a is related to b b is related to a 4 R is anti symmetric if aRb and bRa imply a b Equivalently this means if a b then a b R implies b a R In words whenever a is related to b and a b then b is not related to a 10 Symmetric anti symmetric or none a b a b c a b c 11 5 R is transitive if aRb and bRc imply aRc i e if a b R and b c R then a c R In words whenever a is related to b and b is related to c then a is related to c Which graphs represent transitive relations on a b c a a a b b b c c c a a b b 12 Give example of a relation on A a b c that is a reflexive but not symmetric R a a b b c c a b b a c b symmetric but not reflexive and not transitive a R a b b a b b b c c b b c 13 Counting relations Consider a finite set A with A n How many reflexive relations are there on A There exist n2 pairs on A n of them are self loops like a a A reflexive relation must include all n self loops So we are left with 2 choices include or not for any of n2 n pairs a b of distinct elements a b So the total number of different reflexive relations is 2n n n The next question is how many irreflexive relations are there on A This is for you to figure out 14 How many symmetric relations on A A n n n n2 n 2 coupled pairs n self loops n n2 n 2 n n 1 2 2n n 1 2 15 How many anti symmetric relations are on A We can include any number of self loops For any couple of distinct elements a b we have now 3 choices include a b but not include b a include b a but not include a b include neither a b nor b a We have n n 1 2 couples and it gives 3n n 1 2 possible selections This must be multiplied by 2n possible subsets of self loops The total number of anti symmetric relations is 2n 3n n 1 2 16 Suppose R1 and R2 are two relations on A Let s …
View Full Document
Unlocking...