Relations PDF

Course : MATH6198051– Discrete Mathematics Effective Period : September 2022 Relations Session 15-18  Acknowledgement These slides have been adapted from : Kenneth H. Rosen, “ Discrete Mathematics and its Applications”, 8th edition,2019, M...

Course : MATH6198051– Discrete Mathematics Effective Period : September 2022 Relations Session 15-18  Acknowledgement These slides have been adapted from : Kenneth H. Rosen, “ Discrete Mathematics and its Applications”, 8th edition,2019, McGraw-Hill Education, New York, ISBN 978-1- 259-67651-2 Chapter 9 2  Learning Objectives On successful completion of this course, students will be able to: LO 3 Analyze the Relations and Partial Order Set  Sub Topics Relations 1 Properties of Relations 2 Equivalence Relations 3 Partial Orderings 4 Representing Relations 5 4 Relations and Their Properties 5  Introduction Definition 1 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 first element of each ordered pair comes from A and the second element comes from B. ❑ The notation aRb to denote that (a, b) ∈ R and a R b to denote that (a, b) ∉ R. Moreover, when (a, b) belongs to R, a is said to be related to b by R. ❑ Binary relations represent relationships between the elements of two sets. 6  Relations on a Set Definition 2 A relation on a set A is a relation from A to A. Example Let A be the set {1, 2, 3, 4}. Which ordered pairs are in the relation R = {(a, b) ∣ a divides b}? Solution: Because (a, b) is in R if and only if a and b are positive integers not exceeding 4 such that a divides b, we see that R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)}. 7  Relations on a Set Displaying the ordered pairs in the relation R 8  Properties of Relations 1. Reflexive Definition 3 A relation R on a set A is called reflexive if (a, a) ∈ R for every element a ∈ A. Example Consider the following 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? 9  1. Reflexive Solution: ✓ The relations R3 and R5 are reflexive because they both contain all pairs of the form (a, a), namely, (1, 1), (2, 2), (3, 3), and (4, 4). ✓ The other relations are not reflexive because they do not contain all of these ordered pairs. ✓ In particular, R1, R2, R4, and R6 are not reflexive because (3, 3) is not in any of these relations. 10  2. Symmetric Definition 4 A relation R on a set A is called symmetric if (b, a) ∈ R whenever (a, b) ∈ R, for all a, b ∈ A. 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 Example Consider the following 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 symmetric and which are antisymmetric?? 11  2. Symmetric Solution: ✓ The relations R2 and R3 are symmetric, o For R2, the only thing to check is that both (2, 1) and (1, 2) are in the relation. o For R3, it is necessary to check that both (1, 2) and (2, 1) belong to the relation, and (1, 4) and (4, 1) belong to the relation. ✓ The relations R4, R5, and R6 are all antisymmetric. For each of these relations there is no pair of elements a and b with a ≠ b such that both (a, b) and (b, a) belong to the relation 12  3. Transitive 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. Example Consider the following 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 transitive? 13  3. Transitive Solution: ✓ R4, R5, and R6 are transitive. o R4 is transitive, because (3, 2) and (2, 1), (4, 2) and (2, 1), (4, 3) and (3, 1), and (4, 3) and (3, 2) are the only such sets of pairs, and (3, 1), (4, 1), and (4, 2) belong to R4. o R5 and R6 are transitive. ✓ R1 is not transitive because (3, 4) and (4, 1) belong to R1, but (3, 1) does not. ✓ R2 is not transitive because (2, 1) and (1, 2) belong to R2, but (2, 2) does not. ✓ R3 is not transitive because (4, 1) and (1, 2) belong to R3, but (4, 2) does not. 14 Equivalence Relations 15  Equivalence Relations Definition 1 A relation on a set A is called an equivalence relation if it is reflexive, symmetric, and transitive. Definition 2 Two elements a and b that are related by an equivalence relation are called equivalent. The notation a ∼ b is often used to denote that a and b are equivalent elements with respect to a particular equivalence relation. 16  Equivalence Relations Example 1: Let R be the relation on the set of real numbers such that aRb if and only if a − b is an integer. Is R an equivalence relation? Solution: ▪ Because a−a = 0 is an integer for all real numbers a, aRa for all real numbers a. Hence, R is reflexive. ▪ Suppose that aRb. Then a−b is an integer, so b−a is also an integer. Hence, bRa. It follows that R is symmetric. ▪ If aRb and bRc, then a−b and b−c are integers. Therefore, a−c = (a−b) + (b−c) is also an integer. Hence, aRc. Thus, R is transitive. Consequently, R is an equivalence relation. 17  Equivalence Relations Example 2 : Let R be the relation on the set of real numbers such that xRy if and only if x and y are real numbers that differ by less than 1, that is, |x − y| < 1. Show that R is not an equivalence relation. Solution: ▪ R is reflexive because |x − x| = 0 < 1 whenever x ∈ R. ▪ R is symmetric, for if xRy, where x and y are real numbers, then |x − y| < 1, which tells us that |y − x| = |x − y| < 1, So that yRx. ▪ R is not transitive. Take x = 2.8, y = 1.9, and z = 1.1, so that |x − y| = |2.8 − 1.9| = 0.9 < 1, |y − z| = |1.9 − 1.1| = 0.8 < 1, but |x − z| = |2.8 − 1.1| = 1.7 > 1. That is, 2.8R 1.9, 1.9R 1.1, but 2.8 R 1.1. Hence R is not an equivalence relation 18  Equivalence Classes Definition 3 Let R be an equivalence relation on a set A. The set of all elements that are related to an element a of A is called the equivalence class of a. The equivalence class of a with respect to R is denoted by [a]𝑅. When only one relation is under consideration, we can delete the subscript R and write [a] for this equivalence class. If R is an equivalence relation on a set A, the equivalence class of the element a is [a]𝑅 = {s ∣ (a, s) ∈ R}. If b ∈ [a]𝑅 , then b is called a representative of this equivalence class 19  Equivalence Classes Example 1 : What is the equivalence class of an integer for the equivalence relation R such that aRb if and only if a = b or a = −b. Solution : Because an integer is equivalent to itself and its negative in this equivalence relation,it follows that [a] = {−a, a}. This set contains two distinct integers unless a = 0. For instance, = {−7, 7}, [−5] = {−5, 5}, and = {0}. 20  Equivalence Classes Example 2 What are the equivalence classes of 0, 1, 2, and 3 for congruence modulo 4? Solution: ▪ The equivalence class of 0 contains all integers a such that a ≡ 0 (mod 4).. Hence, the equivalence class of 0 for this relation is = {…,−8,−4, 0, 4, 8,…}. ▪ The equivalence class of 1 contains all the integers a such that a ≡ 1 (mod 4). Hence, the equivalence class of 1 for this relation is = {…,−7,−3, 1, 5, 9,…}. ▪ The equivalence class of 2 contains all the integers a such that a ≡ 2 (mod 4). Hence, the equivalence class of 2 for this relation is = {…,−6,−2, 2, 6, 10,…}. ▪ The equivalence class of 3 contains all the integers a such that a ≡ 3 (mod 4). Hence, the equivalence class of 3 for this relation is = {…,−5,−1, 3, 7, 11,…}. 21  Equivalence Classes and Partitions THEOREM 1 Let R be an equivalence relation on a set A. These statements for elements a and b of A are equivalent: (i) aRb (ii) [a] = [b] (iii) [a] ∩ [b] ≠ ∅ ✓ Let R be an equivalence relation on a set A. The union of the equivalence classes of R is all of A, because an element a of A is in its own equivalence class, namely, [a]𝑅. ✓ From Theorem 1, it follows that these equivalence classes are either equal or disjoint, so when [a]𝑅 ≠ [b]𝑅. 22  Equivalence Classes and Partitions Theorem 2 Let R be an equivalence relation on a set S. Then the equivalence classes of R form a partition of S. Conversely, given a partition {Ai ∣ i ∈ I} of the set S, there is an equivalence relation R that has the sets Ai, i ∈ I, as its equivalence classes. Example : Suppose that S = {1, 2, 3, 4, 5, 6}. The collection of sets A1 = {1, 2, 3}, A2 = {4, 5}, and A3 = {6} forms a partition of S, because these sets are disjoint and their union is S. List the ordered pairs in the equivalence relation R Solution: The pair (a, b) ∈ R if and only if a and b are in the same subset of the S in the partition. R= (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), and (3, 3) (4, 4), (4, 5), (5, 4), and (5, 5), (6, 6) 23 Partial Orderings 24  Partial Orderings Definition 1 A relation R on a set S is called a partial ordering or partial order if it is reflexive, antisymmetric, and transitive. A set S together with a partial ordering R is called a partially ordered set, or poset, and is denoted by (S, R). Members of S are called elements of the poset. Example 1 : Show that the greater than or equal to relation (≥) is a partial ordering on the set of integers. Solution: ▪ Because a ≥ a for every integer a, ≥ is reflexive. ▪ If a ≥ b and b ≥ a, then a =b. Hence, ≥ is antisymmetric. ▪ Relation ≥ is transitive because a ≥ b and b ≥ c imply that a ≥ c. It follows that ≥ is a partial ordering on the set of integers and (Z, ≥) is a poset. 25  Partial Orderings Example 2: Let R be the relation on the set of people such that xRy if x and y are people and x is older than y. Show that R is not a partial ordering. Solution: ▪ R is antisymmetric because if a person x is older than a person y, then y is not older than x. That is, if xRy, then yRx. ▪ The relation R is transitive because if person x is older than person y and y is older than person z, then x is older than z. That is, if xRy and yRz, then xRz. ▪ R is not reflexive, because no person is older than himself or herself. That is, xRx for all people x. It follows that R is not a partial ordering. 26  Partial Orderings Definition 2 The elements a and b of a poset (S,≼ ) are called comparable if either a ≼ b or b ≼ a. When a and b are elements of S such that neither a ≼ b nor b ≼ a, a and b are called incomparable. Example In the poset (Z+ , ∣), are the integers a. 3 and 9 comparable? b. 5 and 7 comparable? Solution: a. The integers 3 and 9 are comparable, because 3 ∣ 9. b. The integers 5 and 7 are incomparable,because 5 ∤7 and 7 ∤ 5. 27  Partial Orderings Definition 3 If (S, ≼) is a poset and every two elements of S are comparable, S is called a totally ordered or linearly ordered set, and ≼ is called a total order or a linear order. A totally ordered set is also called a chain. Example : 1. The poset (Z,≤) is totally ordered, because a ≤ b or b ≤ a whenever a and b are integers 2. The poset (Z+ , ∣ ) is not totally ordered because it contains elements that are incomparable, such as 5 and 7. 28  Hasse Diagrams Procedure of Hasse Diagrams : 1. Represent a finite poset (S, ≼ ) with the directed graph for this relation. 2. Remove these loops. 3. Remove all edge transitivity 4. Remove all the arrows on the directed edges Example 1 : Consider ({1, 2, 3, 4},≤). Partial ordering for {(a, b) ∣ a ≤ b} on the set {1, 2, 3, 4}, The directed graph Hasse Diagrams 29  Hasse Diagrams Example 2 : Draw the Hasse diagram representing the partial ordering {(a, b) ∣a divides b} on {1, 2, 3, 4, 6, 8, 12}. Solution : R= (1, 4), (1, 6), (1, 8), (1, 12), (2, 8), (2, 12), and (3, 12). Fig (c) is the resulting Hasse diagram 30  Maximal and Minimal Elements ❑ An element of a poset is called maximal if it is not less than any element of the poset. That is, a is maximal in the poset (S, ≼) if there is no b ∈ S such that a ≺ b. ❑ An element of a poset is called minimal if it is not greater than any element of the poset. That is, a is minimal if there is no element b ∈ S such that b ≺ a. Example : Which elements of the poset ({2, 4, 5, 10, 12, 20, 25}, ∣) are maximal, and which are minimal? Solution : The maximal elements are 12, 20, and 25, The minimal elements are 2 and 5 31  The greatest element and The least element ❑ An element in a poset that is greater than every other element. That is, a is the greatest element of the poset (S, ≼ ) if b a for all b ∈ S. The greatest element is unique when it exists. ❑ An element is called the least element if it is less than all the other elements in the poset. That is, a is the least element of (S, ≼ ) if a b for all b ∈ S. The least element is unique when it exists. Example : Hasse Greatest Least Diagram element Elemen t (a) - a (b) - - (c) d - (d) d a 32  Upper Bound and Lower Bound ❑ an element that is greater than or equal to all the elements in a subset A of a poset poset (S, ≼ ). If u is an element of S such that a ≼ u for all elements a ∈ A, then u is called an upper bound of A. ❑ an element less than or equal to all the elements in A If l is an element of S such that l ≼ a for all elements a ∈ A, then l is called a lower bound of A. ❑ The element x is called the least upper bound of the subset A (lub(A)) if a ≼ x whenever a ∈ A, and x ≼ z whenever z is an upper bound of A. ❑ The element y is called the greatest lower bound of A (glb(A)) if y is a lower bound of A and z ≼ y whenever z is a lower bound of A. ❑ The least upper bound and the greatest lower bound of A is unique if it exists 33  Example In the poset with the Hasse diagram below : a. Find the lower and upper bounds of the subsets {a, b, c}, {j, h}, and {a, c, d, f } b. Find the greatest lower bound and the least upper bound of {b, d, g}, if they exist Solution: a. UB {a, b, c} = e, f, j, and h, LB {a, b, c} = a UB {j, h} = - LB {j, h} = a, b, c, d, e, and f UB {a, c, d, f } = f , h, and j LB {a, c, d, f } = a b. UB {b, d, g} = g and h. LUB {b, d, g} =g LB {b, d, g} = a and b. GLB {b, d, g} = b 34  Lattices A partially ordered set in which every pair of elements has both a least upper bound and a greatest lower bound is called a lattice. Example : ▪ Hasse diagrams in (a) and (c) are both lattices ▪ Hasse diagram shown in (b) is not a lattice, because the elements b and c have no least upper bound 35 Representing Relations 36  Representing Relations Using Matrices Generally, matrices are appropriate for the representation of relations in computer programs. Suppose that R is a relation from A = {a1, a2,…, am} to B = {b1, b2,…, bn}. The relation R can be represented by the matrix MR = [mij], where 37  Representing Relations Using Matrices Example 1 Suppose that A = {1, 2, 3} and B = {1, 2}. Let R be the relation from A to B containing (a, b) if a ∈ A, b ∈ B, and a > b. What is the matrix representing R if a1 = 1, a2 = 2, and a3 = 3, and b1 = 1 and b2 = 2? Solution: Because R = {(2, 1), (3, 1), (3, 2)}, the matrix for R is The 1s in MR show that the pairs (2, 1), (3, 1), and (3, 2) belong to R. The 0s show that no other pairs belong to R. 38  Representing Relations Using Matrices Example 2 Let A = {a1, a2, a3} and B = {b1, b2, b3, b4, b5}. Which ordered pairs are in the relation R represented by the matrix Solution: Because R consists of those ordered pairs (ai, bj) with mij = 1, it follows that R = {(a1, b2), (a2, b1), (a2, b3), (a2, b4), (a3, b1), (a3, b3), (a3, b5)}. 39  The matrix of a relation on a set The zero–one matrix The zero–one matrices for for a reflexive antisymmetric relations. relation. The zero–one matrices for symmetric 40  Representing Relations Using Matrices Example 3 Suppose that the relation R on a set is represented by the matrix Is R reflexive, symmetric, and/or antisymmetric? Solution: R is reflexive. Because all the diagonal elements of this matrix are equal to 1 R is symmetric , because MR is symmetric R is not antisymmetric. 41  Representing Relations Using Digraphs Definition 1 A directed graph, or digraph, consists of a set V of vertices (or nodes) together with a set E of ordered pairs of elements of V called edges (or arcs). The vertex a is called the initial vertex of the edge (a, b), and the vertex b is called the terminal vertex of this edge Example A directed graph The directed graph with vertices a, b, c, and d, and edges (a, b), (a, d), (b, b), (b, d), (c, a), (c, b), and (d, b) 42  Reference Kenneth H. Rosen, “ Discrete Mathematics and its Applications”, 8th edition,219, McGraw-Hill Education, New York, ISBN 978-1-259-67651-2 43 Thank You