Closure Properties of Relations: Reflexive, Symmetric, and Transitive Closures
Learn about closure properties of relations in discrete mathematics, focusing on reflexive, symmetric, and transitive closures. This guide explains how to find the smallest relation containing a given relation that satisfies a specific property, using examples and formal definitions.
Closure Properties of Relations: Reflexive, Symmetric, and Transitive Closures
Introduction to Relation Closures
Given a relation R on a set A, a closure operation creates the smallest relation containing R that also satisfies a particular property (like reflexivity, symmetry, or transitivity). This is a fundamental concept in discrete mathematics used to analyze and understand relations. For example, if a relation is not transitive, you might want to find the smallest transitive relation that contains the original relation; that's the transitive closure.
1. Reflexive, Symmetric Closures
Let R be a relation on a set A. The reflexive closure adds pairs (a, a) for all elements a in A to the relation R (making it reflexive). The symmetric closure adds the inverse of any existing pairs (a,b) by adding (b,a).
Theorem:
The reflexive closure of R is R ∪ ΔA (where ΔA is the identity relation on A).
The symmetric closure of R is R ∪ R-1 (where R-1 is the inverse of R).
Example 1: Reflexive Closure
Let A = {k, l, m} and R = {(k, k), (k, l), (l, m), (m, k)}. The reflexive closure is R ∪ {(l, l), (m, m)}.
Example 2: Symmetric Closure
Let A = {4, 5, 6, 7} and R = {(4, 5), (5, 5), (5, 6), (6, 7), (7, 4), (7, 7)}. The symmetric closure is R ∪ {(5, 4), (6, 5), (7,6), (4,7)}.
2. Transitive Closures
The transitive closure of a relation R is the smallest transitive relation containing R. Remember that R² = R ◦ R (the composition of R with itself), and Rn = R ◦ Rn-1.
Theorem 1:
The transitive closure R* of R is R ∪ R² ∪ R³ ∪ ... ∪ Rn (where n is the number of elements in A).
Theorem 2:
If A is finite, the transitive closure is R ∪ R² ∪ ... ∪ Rn (where n is the number of elements in A).
Example 1: Transitive Closure
Let R = {(1, 2), (2, 3), (3, 3)} on A = {1, 2, 3}. Then R² = {(1, 3), (2, 3), (3, 3)}, and R³ = {(1, 3), (2, 3), (3, 3)}. The transitive closure is R ∪ R² = {(1, 2), (2, 3), (3, 3), (1, 3)}.
Example 2: Transitive Closure Using Matrix Representation
(An example using a matrix representation of a relation and computing the transitive closure by calculating powers of the matrix and performing a logical OR operation on the resulting matrices would be included here. Images showing the matrices at each step would be very helpful.)
Conclusion
Reflexive, symmetric, and transitive closures are fundamental concepts for understanding and manipulating relations. These operations create the smallest relations that satisfy the given properties, which is important for various mathematical and computational tasks.