In this chapter, the following content will be discussed: Transitive closure of a relations, combining relations, the relation induced by a partition, equivalence relations, equivalence classes of congruence modulo 3. | (CSC 102) Lecture 17 Discrete Structures Previous Lectures Summary Properties of relations Reflexive, Symmetric and Transitive Relations Properties of “Less than” relations Properties of Congruence Modulo 3 Relations Today’s Lecture Transitive closure of a relations Combining Relations The Relation Induced by a Partition Equivalence Relations Equivalence Classes of Congruence Modulo 3 Let A be a set and R a relation on A. The transitive closure of R is the relation Rt on A that satisfies the following three properties: 1. Rt is transitive. 2. R ⊆ Rt . 3. If S is any other transitive relation that contains R, then Rt ⊆ S. The Transitive Closure of a Relation Example Let A = {0, 1, 2, 3} and consider the relation R defined on A as follows: R = {(0, 1), (1, 2), (2, 3)}. Find the transitive closure of R. Solution: Every ordered pair in R is in Rt, so {(0, 1), (1, 2), (2, 3)} ⊆ Rt. Thus the directed graph of R contains the arrows shown below. The Transitive Closure of a Relation Since there are arrows going from 0 to 1 and from 1 to 2, Rt must have an arrow going from 0 to 2. Hence (0, 2) ∈ Rt. Then (0, 2) ∈ Rt and (2, 3) ∈ Rt, so since Rt is transitive, (0, 3) ∈ Rt. Also, since (1, 2) ∈ Rt and (2, 3) ∈ Rt, then (1, 3) ∈ Rt. Thus Rt contains at least the following ordered pairs: {(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)}. But this relation is transitive; hence it equals Rt. Note that the directed graph of Rt is as shown below. The Transitive Closure of a Relation Relations are sets, and therefore, we can apply the usual set operations to them. If we have two relations R1 and R2, and both of them are from a set A to a set B, then we can combine them to R1 R2, R1 R2, or R1 – R2. In each case, the result will be another relation from A to B. Combining Relations Combining Relations There is another important way to combine relations. Definition: Let R be a relation from a set A to a set B and S a relation from B to a set C. The composite of R and S is the relation | (CSC 102) Lecture 17 Discrete Structures Previous Lectures Summary Properties of relations Reflexive, Symmetric and Transitive Relations Properties of “Less than” relations Properties of Congruence Modulo 3 Relations Today’s Lecture Transitive closure of a relations Combining Relations The Relation Induced by a Partition Equivalence Relations Equivalence Classes of Congruence Modulo 3 Let A be a set and R a relation on A. The transitive closure of R is the relation Rt on A that satisfies the following three properties: 1. Rt is transitive. 2. R ⊆ Rt . 3. If S is any other transitive relation that contains R, then Rt ⊆ S. The Transitive Closure of a Relation Example Let A = {0, 1, 2, 3} and consider the relation R defined on A as follows: R = {(0, 1), (1, 2), (2, 3)}. Find the transitive closure of R. Solution: Every ordered pair in R is in Rt, so {(0, 1), (1, 2), (2, 3)} ⊆ Rt. Thus the directed graph of R contains the arrows shown below. The Transitive Closure of a Relation Since .
