Relations Section 8 1 8 3 8 5 of Rosen Spring 2010 CSCE 235 Introduction to Discrete Structures Course web page cse unl edu cse235 Questions cse235 cse unl edu Outline Relation Definition representation relation on a set Properties Reflexivity symmetry antisymmetric irreflexive asymmetric Combining relations composite of relations Representing relations 0 1 matrices directed graphs Closure of relations Reflexive closure diagonal relation Warshall s Algorithm Equivalence relations Equivalence class partitions CSCE 235 Spring 2010 Relations 2 Introduction A relation between elements of two sets is a subset of their Cartesian products set of all 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 Relation versus function In a relation each a A can map to multiple elements in B Relations are more general than functions When a b R we say that a is related to b Notation aRb aRb aRb a notR b CSCE 235 Spring 2010 Relations 3 Relations Representation To represent a relation we can enumerate every element of R Example Let A a1 a2 a3 a4 a5 and B b1 b2 b3 Let R be a relation from A to B defined as follows R a1 b1 a1 b2 a1 b3 a3 b1 a3 b2 a3 b3 a5 b1 We can represent this relation graphically A CSCE 235 Spring 2010 a1 b1 a2 b2 a3 a4 a5 b3 Relations B 4 Relations on a Set Definition A relation on the set A is a relation from A to A and is a subset of A A Example The following are binary relations on N R1 a b a b R2 a b a b N a b Z R3 a b a b N a b 2 Question Give some examples of ordered pairs a b N2 that are not in each of these relations CSCE 235 Spring 2010 Relations 5 Properties We will study several properties of relations Reflexive Symmetric Transitive Antisymmetric Asymmetric CSCE 235 Spring 2010 Relations 6 Properties Reflexivity In a relation on a set if all ordered pairs a a for every a A appears in the relation R is called reflexive Definition A relation R on a set A is called reflexive if a A a a R CSCE 235 Spring 2010 Relations 7 Reflexivity Examples Recall the relations below which is reflexive R1 a b a b R2 a b a b N a b Z R3 a b a b N a b 2 R1 is reflexive since for every a N a a R2 is reflexive since a a 1 is an integer R3 is not reflexive since a a 0 for every a N CSCE 235 Spring 2010 Relations 8 Properties Symmetry Definitions A relation R on a set A is called symmetric if a b A b a R a b R A relation R on a set A is called antisymmetric if a b A a b R b a R a b CSCE 235 Spring 2010 Relations 9 Symmetry versus Antisymmetry In a symmetric relation aRb bRa In an antisymmetric relation if we have aRb and bRa hold only when a b An antisymmetric relation is not necessarily a reflexive relation A relation can be both symmetric and antisymmetric or neither or have one property but not the other A relation that is not symmetric is not necessarily asymmetric CSCE 235 Spring 2010 Relations 10 Symmetric Relations Example Consider R x y R2 x2 y2 1 is R Reflexive Symmetric Antisymmetric R is not reflexive since for example 2 2 R2 R is symmetric because x y R xRy x2 y2 1 y2 x2 1 yRx R is not antisymmetric because 1 3 8 3 R and 8 3 1 3 R but 1 3 8 3 CSCE 235 Spring 2010 Relations 11 Properties Transitivity 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 A a b c A aRb bRc aRc CSCE 235 Spring 2010 Relations 12 Transitivity Examples 1 Is the relation R x y R2 x y transitive Yes it is transitive because xRy and yRz x y and y z x z xRz Is the relation R a b b a a a transitive No it is not transitive because bRa and aRb but bRb CSCE 235 Spring 2010 Relations 13 Transitivity Examples 2 Is the relation a b a is an ancestor of b transitive Yes it is transitive because aRb and bRc a is an ancestor of b and b is an ancestor of c a is an ancestor of c aRc Is the relation x y R2 x2 y transitive No it is not transitive because 2R4 and 4R10 but 2R10 CSCE 235 Spring 2010 Relations 14 More Properties Definitions A relation on a set A is irreflexive if a A a a R A relation on a set A is asymmetric if a b A a b R b a R Lemma A relation R on a set A is asymmetric if and only if R is irreflexive and R is antisymmetric CSCE 235 Spring 2010 Relations 15 Outline Relation Definition representation relation on a set Properties Reflexivity symmetry antisymmetric irreflexive asymmetric Combining relations composite of relations Representing relations 0 1 matrices directed graphs Closure of relations Reflexive closure diagonal relation Warshall s Algorithm Equivalence relations Equivalence class partitions CSCE 235 Spring 2010 Relations 16 Combining Relations Relations are simply sets of ordered pairs subsets of the Cartesian product of two sets Therefore in order to combine relations to create new relations it makes sense to use the usual set operations Intersection R1 R2 Union R1 R2 Set difference R1 R2 Sometimes combining relations endows them with the properties previously discussed For example two relations may be not transitive but their union may be CSCE 235 Spring 2010 Relations 17 Combining Relations Example Let A 1 2 3 4 B 1 2 3 4 R1 1 2 1 3 1 4 2 2 3 4 4 1 4 2 R2 1 1 1 2 1 3 2 3 Let R1 R2 R1 R2 R1 R2 R2 R1 CSCE 235 Spring 2010 Relations 18 Composite 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 and 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 an element b B such that a b R1 and b c R2 We denote the composite of R1 and R2 by R 2 R1 CSCE 235 Spring 2010 Relations 19 Powers of Relations Using the composite way of combining relations similar to function composition allows us to recursively define power of a relation R on a set A 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 CSCE 235 Spring …
View Full Document
Unlocking...