Relations: Closure Properties
Relations
A relation R on a set A is a subset of the Cartesian product A×A. It consists of ordered pairs of
elements from A. The closure of a relation refers to the smallest relation that contains R and satisfies
certain properties.
Types of Closure
1. Reflexive Closure
The reflexive closure of a relation R on a set A is the smallest relation R′ that contains R and is
reflexive. This means that every element in A is related to itself.
Formula: R′ = R ∪ {(a,a) ∣ a ∈ A}
Example: Let A = {1,2} and R={(1,2)}. The reflexive closure of R is: R′ = {(1,2),(1,1),(2,2)}.
2. Symmetric Closure
The symmetric closure of a relation R on a set A is the smallest relation R′ that contains R and is
symmetric. This means that if (a,b) ∈ R′, then (b,a) ∈ R′
Formula: R′ = R ∪ {(b,a) ∣ (a,b) ∈ R}
Example: Let A = {1,2} and R = {(1,2)}. The symmetric closure of R is: R′ = {(1,2),(2,1)}.
3. Transitive Closure
The transitive closure of a relation R on a set A is the smallest relation R′ that contains R and is
transitive. This means that if (a,b) ∈ R and (b,c) ∈ R′, then (a,c) ∈ R′
Algorithm (Warshall’s Algorithm)
1. Initialize R′ = R.
2. For each (a,b) ∈ R′ and (b,c) ∈ R, add (a,c) to R′.
Example:
Let A = {1,2,3} and R = {(1,2),(2,3)}. The transitive closure of R is:
R′ = {(1,2),(2,3),(1,3)}.
Applications in Engineering
1. Database Theory
In database theory, the closure of relations is used in query optimization and integrity constraints.
Example: Ensuring that a database relation maintains transitive dependencies helps in normalizing
the database and reducing redundancy.
2. Computer Networks
Closure of relations helps in network routing algorithms to ensure that connections are efficiently
managed.
Example: Using the transitive closure to find the shortest path in a network by considering all
possible routes.
3. Formal Verification
In formal methods, closure properties are used to verify the correctness of systems and protocols.
Example: Verifying that a system maintains certain properties under all possible transitions can be
achieved by computing the transitive closure of the state transition relation.
4. Compiler Design
Closure properties are used in data flow analysis to optimize and validate code.
Example: Using the transitive closure in reaching definitions analysis to determine all definitions that
can reach a particular point in the code.
5. Social Network Analysis
In social network analysis, closure properties help understand the reachability and influence within a
network.
Example: Computing the transitive closure to find all indirect connections between individuals in a
social network.
Solved Examples on Closure of Relations
Example 1: Find Reflexive Closure
Given: R = {(1,2), (2,3), (3,4)} on set A = {1, 2, 3, 4}
To find the reflexive closure, we need to add all pairs (a,a) that are missing from R for all a ∈ A.
Reflexive closure of R = R ∪ {(1,1), (2,2), (3,3), (4,4)}
= {(1,1), (1,2), (2,2), (2,3), (3,3), (3,4), (4,4)}
Example 2: Find Symmetric Closure
Given: R = {(1,2), (2,3), (1,3)} on set A = {1, 2, 3}
To find the symmetric closure, we need to add (b,a) for every (a,b) in R.
Symmetric closure of R = R ∪ {(2,1), (3,2), (3,1)}
= {(1,2), (2,1), (2,3), (3,2), (1,3), (3,1)}
Example 3: Find Transitive Closure
Given: R = {(1,2), (2,3), (3,4)} on set A = {1, 2, 3, 4}
To find the transitive closure, we need to add all pairs (a,c) where (a,b) and (b,c) are in R.
Step 1: R⁰ = R = {(1,2), (2,3), (3,4)}
Step 2: R¹ = R⁰ ∪ {(1,3)} (because (1,2) and (2,3) are in R⁰)
Step 3: R² = R¹ ∪ {(1,4), (2,4)} (because (1,3) and (3,4), and (2,3) and (3,4) are in R¹)
Step 4: R³ = R² (no new pairs added)
Therefore, the transitive closure of R is:
{(1,2), (2,3), (3,4), (1,3), (1,4), (2,4)}
Example 4: Find All Closures Combined
Given: R = {(1,2), (2,1)} on set A = {1, 2, 3}
Reflexive Closure:
R ∪ {(1,1), (2,2), (3,3)} = {(1,1), (1,2), (2,1), (2,2), (3,3)}
Symmetric Closure:
R is already symmetric
Transitive Closure:
R is already transitive
Reflexive, Symmetric, and Transitive Closure:
{(1,1), (1,2), (2,1), (2,2), (3,3)}
Example 5 : Let R be a relation on set A = {1, 2, 3} defined as R = {(1,2), (2,3)}.Find the reflexive
closure:
To find the reflexive closure:
Add all pairs (a,a) for each element a in A that are not already in R.
Reflexive closure = R ∪ {(1,1), (2,2), (3,3)}
Final result: {(1,2), (2,3), (1,1), (2,2), (3,3)}
Example 6 : Let R be a relation on set A = {a, b, c} defined as R = {(a,b), (b,c), (c,a)}.Find the reflexive
closure:
To find the symmetric closure:
For each pair (x,y) in R, add (y,x) if it’s not already present.
Symmetric closure = R ∪ {(b,a), (c,b), (a,c)}
Final result: {(a,b), (b,c), (c,a), (b,a), (c,b), (a,c)}
Example 7 : Let R be a relation on set A = {1, 2, 3, 4} defined as R = {(1,2), (2,3), (3,4)}.Find the
reflexive closure:
To find the transitive closure:
Add all pairs (x,z) where (x,y) and (y,z) are in R for some y.
In this case, we need to add (1,3), (2,4), and (1,4).
Transitive closure = R ∪ {(1,3), (2,4), (1,4)}
Final result: {(1,2), (2,3), (3,4), (1,3), (2,4), (1,4)}
Example 8 : Let R be a relation on set A = {x, y, z} defined as R = {(x,y), (y,z), (z,x)}.Find the reflexive
closure:
To find the reflexive closure:
Add all pairs (a,a) for each element a in A that are not already in R.
Reflexive closure = R ∪ {(x,x), (y,y), (z,z)}
Final result: {(x,y), (y,z), (z,x), (x,x), (y,y), (z,z)}
Example 9 : Find Symmetric Closure:
Let R be a relation on set A = {1, 2, 3, 4} defined as R = {(1,2), (2,3), (3,4), (4,1)}.
To find the symmetric closure:
For each pair (a,b) in R, add (b,a) if it’s not already present.
Symmetric closure = R ∪ {(2,1), (3,2), (4,3), (1,4)}
Final result: {(1,2), (2,3), (3,4), (4,1), (2,1), (3,2), (4,3), (1,4)}
Transitive Closure:
Example 10 : Let R be a relation on set A = {a, b, c, d} defined as R = {(a,b), (b,c), (c,d), (d,a)}.
To find the transitive closure:
Add all pairs (x,z) where (x,y) and (y,z) are in R for some y.
We need to add: (a,c), (b,d), (c,a), (d,b)
Then we need to add: (a,d), (b,a), (c,b), (d,c)
Finally, we add: (a,a), (b,b), (c,c), (d,d)
Transitive closure = R ∪ {(a,c), (b,d), (c,a), (d,b), (a,d), (b,a), (c,b), (d,c), (a,a), (b,b), (c,c), (d,d)}
Final result: {(a,b), (b,c), (c,d), (d,a), (a,c), (b,d), (c,a), (d,b), (a,d), (b,a), (c,b), (d,c), (a,a), (b,b), (c,c),
(d,d)}
Practice Problems on Closure of Relations
1).Find the reflexive closure of R = {(1,2), (2,3), (3,1)} on set A = {1, 2, 3}.
2).Determine the symmetric closure of R = {(a,b), (b,c), (c,d)} on set A = {a, b, c, d}.
3).Calculate the transitive closure of R = {(1,2), (2,3), (3,4)} on set A = {1, 2, 3, 4}.
4).Find the reflexive and symmetric closure of R = {(x,y), (y,z)} on set A = {x, y, z}.
5).Determine the transitive closure of R = {(a,b), (b,c), (c,a), (a,d)} on set A = {a, b, c, d}.
6).Calculate the reflexive, symmetric, and transitive closure of R = {(1,2), (2,3)} on set A = {1, 2, 3}.
7).Find the symmetric closure of R = {(1,1), (1,2), (2,3), (3,1)} on set A = {1, 2, 3}.
8).Determine the reflexive closure of R = {(a,b), (b,a), (b,c), (c,c)} on set A = {a, b, c}.
9).Calculate the transitive closure of R = {(1,2), (2,1), (2,3), (3,4)} on set A = {1, 2, 3, 4}.
10).Find the reflexive and transitive closure of R = {(x,y), (y,z), (z,x)} on set A = {x, y, z}.
