CSE115/ENGR160 Discrete Mathematics 04/26/118.1 Relations and their propertiesBinary relationSlide 4ExampleSlide 6Slide 7Functions as relationsSlide 9Relation on a setSlide 11Slide 12Properties of relations: ReflexiveSlide 14SymmetricAntisymmetricSymmetric and antisymmetricSlide 18Slide 19TransitiveSlide 21Slide 22Combining relationsSlide 24Composite of relationsSlide 26Power of relationSlide 28Slide 29CSE115/ENGR160 Discrete Mathematics04/26/11Ming-Hsuan YangUC Merced18.1 Relations and their properties•Relationships between elements of sets are represented using the structure called a relation•A subset of Cartesian product of the sets•Example: a student and his/her ID2Binary relation•The most direct way to express a relationship between elements of two sets is to use ordered pairs made up of two related elements•Binary relation: Let A and B be sets. A binary relation from A to B is a subset of A×B•A binary relation from A to B is a set R of ordered pairs where the 1st element comes from A and the 2nd element comes from B3Binary relation•aRb denotes that (a,b)∊R •When (a,b) belongs to R, a is said to be related to b by R•Likewise, n-ary relations express relationships among n elements•Let A1, A2, …, An be sets. An n-ary relation of these sets is a subset of A1×A2×…×An. The sets A1, A2, ..., An are called the domains of the relation, and n is called its degree4Example•Let A be the set of students and B be the set of courses•Let R be the relation that consists of those pairs (a, b) where a∊A and b∊B•If Jason is enrolled only in CSE20, and John is enrolled in CSE20 and CSE21•The pairs (Jason, CSE20), (John,CSE20), (John, CSE 21) belong to R•But (Jason, CSE21) does not belong to R5Example•Let A be the set of all cities, and let B be the set of the 50 states in US. Define a relation R by specifying (a,b) belongs to R if city a is in state b•For instance, (Boulder, Colorado), (Bangor, Maine), (Ann Arbor, Michigan), (Middletown, New Jersey), (Middletown, New York), (Cupertino, California), and (Red Bank, New Jersey) are in R6Example•Let A={0, 1, 2} and B={a, b}. Then {(0, a), (0, b), (1, a), (2, b)} is a relation from A to B•That is 0Ra but not 1Rb7Functions as relations•Recall that a function f from a set A to a set B assigns exactly one element of B to each element of A•The graph of f is the set of ordered pairs (a, b) such that b=f(a)•Because the graph of f is a subset of A x B, it is a relation from A to B•Furthermore, the graph of a function has the property that every element of A is the first element of exactly one ordered pair of the graph8Functions as relations•Conversely, if R is a relation from A to B such that every element in A is the first element of exactly one ordered pair of R, then a function can be defined with R as its graph•A relation can be used to express one-to-many relationship between the elements of the sets A and B where an element of A may be related to more than one element of B•A function represents a relation where exactly one element of B is related to each element of A•Relations are a generalization of functions9Relation on a set•A relation on the set A is a relation from A to A, i.e., a subset of A x A•Let A be the set {1, 2, 3, 4}. Which ordered pairs are in the relation R={(a,b)|a divides b}?•R={(1,1),(1,2),(1,3),(1,4),(2,2),(2,4),(3,3),(4,4)}1012341234R 1 2 3 41 X X X X2 X X 3 X 4 XExample•Consider these relations on set of integers R1={(a,b)|a≤b} R2={(a,b)|a>b} R3={(a,b)|a=b or a=-b} R4={(a,b)|a=b} R5={(a,b)|a=b+1} R6={(a,b)|a+b≤3} Which of these relations contain each of the pairs (1,1), (1,2), (2,1), (1, -1) and (2, 2)?•(1,1) is in R1, R3, R4 and R6; (1,2) is in R1 and R6; (2,1) is in R2, R5, and R6; (1,-1) is in R2, R3, and R6; (2,2) is in R1, R3, and R411Example•How many relations are there on a set with n elements?•A relation on a set A is a subset of A x A•As A x A has n2 elements, there are subsets•Thus there are relations on a set with n elements•That is, there are relations on the set {a, b, c} 1222n22n51222932Properties of relations: Reflexive•In some relations an element is always related to itself•Let R be the relation on the set of all people consisting of pairs (x,y) where x and y have the same mother and the same father. Then x R x for every person x•A relation R on a set A is called reflexive if (a,a) ∊ R for every element a∊A•The relation R on the set A is reflexive if ∀a((a,a) ∊ R)13Example•Consider these relations on {1, 2, 3, 4} R1={(1,1),(1,2),(2,1),(2,2),(3,4),(4,1),(4,4)} R2={(1,1),(1,2),(2,1)} R3={(1,1),(1,2),(1,4),(2,1),(2,2),(3,3),(4,1),(4,4)} R4={(2,1),(3,1),(3,2),(4,1),(4,2),(4,3)} R5={(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,3),(3,4),(4,4)} R6={(3,4)} Which of these relations are reflexive?•R3 and R5 are reflexive as both contain all pairs of the (a,a)•Is the “divides” relation on the set of positive integers reflexive?14Symmetric•In some relations an element is related to a second element if and only if the 2nd element is also related to the 1st element•A relation R on a set A is called symmetric if (b,a) ∊ R whenever (a,b) ∊ R for all a, b ∊ A•The relation R on the set A is symmetric if ∀a ∀b ((a,b)∊R→(b,a) ∊R)•A relation is symmetric if and only if a is related to b implies that b is related to a15Antisymmetric•A relation R on a set A such that for all a, b ∊ A, if (a, b)∊R and (b, a)∊ R, then a=b is called antisymmetric•Similarly, the relation R is antisymmetric if ∀a∀b(((a,b)∊R∧(b,a)∊R)→(a=b)) •A relation is antisymmetric if and only if there are no pairs of distinct elements a and b with a related to b and b related to a•That is, the only way to have a related to b and b related to a is for a and b to be the same element16Symmetric and antisymmetric•The terms symmetric and antisymmetric are not opposites as a relation can have both of these properties or may lack both of them•A relation cannot be both symmetric and antisymmetric if it contains some pair of the form (a, b) where a ≠ b17Example•Consider these relations on {1, 2, 3, 4} R1={(1,1),(1,2),(2,1),(2,2),(3,4),(4,1),(4,4)} R2={(1,1),(1,2),(2,1)} R3={(1,1),(1,2),(1,4),(2,1),(2,2),(3,3),(4,1),(4,4)} R4={(2,1),(3,1),(3,2),(4,1),(4,2),(4,3)}