Introduction Relations Recall that a relation between elements of two sets is a subset of their Cartesian product of ordered pairs Slides by Christopher M Bourke Instructor Berthe Y Choueiry Definition A binary relation from a set A to a set B is a subset R A B a b a A b B Fall 2007 Computer Science Engineering 235 Introduction to Discrete Mathematics Sections 8 1 8 3 8 5 of Rosen cse235 cse unl edu Relations 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 aR6 b Relations Graphical View To represent a relation you can enumerate every element in R A Example a1 Let A a1 a2 a3 a4 a5 and B b1 b2 b3 let R be a relation from A to B as follows a2 a3 R a1 b1 a1 b2 a1 b3 a2 b1 a3 b1 a3 b2 a3 b3 a5 b1 B b1 b2 a4 a5 b3 Figure Graphical Representation of a Relation You can also represent this relation graphically Relations Reflexivity On a Set Definition 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 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 Reflexivity Symmetry I Example Definition Example Definition Recall the following relations which is reflexive A relation R on a set A is called symmetric if 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 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 1 is an integer for all a b A Symmetry II Symmetric Relations Definition Example 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 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 Transitivity Transitivity Definition Examples 6 8 3 R and 8 3 Example Definition Is the relation R x y R2 x y transitive 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 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 bR6 b 8 1 3 3 R Transitivity Other Properties Examples Definition Example Is the relation I A relation is irreflexive if a b a is an ancestor of b transitive a a a 6 R I Yes if a is an ancestor of b and b is an ancestor of c then a is also an ancestor of c who is the youngest here A relation is asymmetric if a b a b R b a 6 R Example Lemma Is the relation x y R2 x2 y transitive A relation R on a set A is asymmetric if and only if 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 Combining Relations I R is irreflexive and I R is antisymmetric Combining Relations Example Let Relations are simply sets that is subsets of ordered pairs of the Cartesian product of a set A B R1 R2 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 1 2 3 4 1 2 3 4 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 Powers of Relations 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 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 Powers of Relations Example Consider R 1 1 2 1 3 2 4 3 R2 The powers of relations give us a nice characterization of transitivity R3 Theorem R4 A relation R is transitive if and only if Rn R for n 1 2 3 Notice that Rn R3 for n 4 5 6 Representing Relations 0 1 Matrices I A 0 1 matrix is a matrix whose entries are either 0 or 1 We have seen ways of graphically representing a function relation between two different sets specifically a graph with arrows between …
View Full Document
Unlocking...