Notes Relations Slides by Christopher M Bourke Instructor Berthe Y Choueiry Spring 2006 Computer Science Engineering 235 Introduction to Discrete Mathematics Sections 7 1 7 3 7 5 of Rosen cse235 cse unl edu Introduction Notes Recall that a relation between elements of two sets is a subset of their Cartesian product of ordered pairs Definition A binary relation from a set A to a set B is a subset R A B a b a A b B Note the difference between a relation and a function in a relation each a A can map to multiple elements in B Thus relations are generalizations of functions If an ordered pair a b R then we say that a is related to b We may also use the notation aRb and a6Rb Relations Notes To represent a relation you can enumerate every element in R Example Let A a1 a2 a3 a4 a5 and B b1 b2 b3 let R be a relation from A to B as follows R a1 b1 a1 b2 a1 b3 a2 b1 a3 b1 a3 b2 a3 b3 a5 b1 You can also represent this relation graphically Relations Notes Graphical View A B a1 a2 a3 b1 b2 a4 a5 b3 Figure Graphical Representation of a Relation Relations Notes On a Set Definition A relation on the set A is a relation from A to A I e a subset of A A Example The following are binary relations on N R1 a b a b a Z b R3 a b a b N a b 2 R2 a b a b N Exercise Give some examples of ordered pairs a b N2 that are not in each of these relations Reflexivity Definition There are several properties of relations that we will look at If the ordered pairs a a appear in a relation on a set A for every a A then it is called reflexive Definition A relation R on a set A is called reflexive if a A a a R Notes Reflexivity Notes Example Example Recall the following relations which is reflexive R1 a b a b R2 a b a b N ab Z R3 a b a b N a b 2 I R1 is reflexive since for every a N a a I R2 is also reflexive since I R3 is not reflexive since a a 0 for every a N a a 1 is an integer Symmetry I Notes Definition Definition A relation R on a set A is called symmetric if b a R a b R for all a b A A relation R on a set A is called antisymmetric if a b a b R b a R a b for all a b A Symmetry II Definition Some things to note I A symmetric relationship is one in which if a is related to b then b must be related to a I An antisymmetric relationship is similar but such relations hold only when a b I An antisymmetric relationship is not a reflexive relationship I A relation can be both symmetric and antisymmetric or neither or have one property but not the other I A relation that is not symmetric is not necessarily asymmetric Notes Symmetric Relations Notes Example Example Let R x y R2 x2 y 2 1 Is R reflexive Symmetric Antisymmetric I It is clearly not reflexive since for example 2 2 6 R I It is symmetric since x2 y 2 y 2 x2 i e addition is commutative I It is not antisymmetric since 13 but 1 3 6 8 3 R and 8 1 3 3 R 8 3 Transitivity Notes Definition Definition A relation R on a set A is called transitive if whenever a b R and b c R then a c R for all a b c R Equivalently a b c A aRb bRc aRc Transitivity Examples Example Is the relation R x y R2 x y transitive Yes it is transitive since x y y z x z Example Is the relation R a b b a a a transitive No since bRa and aRb but b6Rb Notes Transitivity Notes Examples Example Is the relation a b a is an ancestor of b transitive Yes if a is an ancestor of b and b is an ancestor of c then a is also an ancestor of b who is the youngest here Example Is the relation x y x2 y transitive No For example 2 4 R and 4 10 R i e 22 4 and 42 16 10 but 22 10 thus 2 10 6 R Other Properties Notes Definition I A relation is irreflexive if a a a 6 R I A relation is asymmetric if a b a b R b a 6 R Lemma A relation R on a set A is asymmetric if and only if I R is irreflexive and I R is antisymmetric Combining Relations Relations are simply sets that is subsets of ordered pairs of the Cartesian product of a set It therefore makes sense to use the usual set operations intersection union and set difference A B to combine relations to create new relations Sometimes combining relations endows them with the properties previously discussed For example two relations may not be transitive alone but their union may be Notes Combining Relations Notes Example Let A B R1 R2 1 2 3 4 1 2 3 1 2 1 3 1 4 2 2 3 4 4 1 4 2 1 1 1 2 1 3 2 3 Then I R1 R2 1 1 1 2 1 3 1 4 2 2 2 3 3 4 4 1 4 2 I R1 R2 1 2 1 3 I R1 R2 1 4 2 2 3 4 4 1 4 2 I R2 R1 1 1 2 3 Notes Definition Let R1 be a relation from the set A to B and R2 be a relation from B to C I e R1 A B R2 B C The composite of R1 and R2 is the relation consisting of ordered pairs a c where a A c C and for which there exists and element b B such that a b R1 and b c R2 We denote the composite of R1 and R2 by R1 R2 Powers of Relations Notes Using this composite way of combining relations similar to function composition allows us to recursively define powers of a relation R Definition Let R be a relation on A The powers Rn n 1 2 3 are defined recursively by R1 R Rn 1 Rn R Powers of Relations Notes Example Consider R 1 2 1 3 2 4 3 R2 R3 R4 Notice that Rn R3 for n 4 5 6 Powers of Relations Notes The powers of relations give us a nice characterization of transitivity Theorem A relation R is transitive if and only if Rn R for n 1 2 3 Representing Relations We have seen ways of graphically representing a function relation between two different sets specifically a graph with arrows between nodes that are …
View Full Document
Unlocking...