Relation Closures

A relation closure means extending the relation by the smallest amount necessary to satisfy a given property. We most commonly talk about reflexive, symmetric, or transitive closure.

Reflexive Closure

In the reflexive closure, we add (a,a) pairs to every element to make the relation reflexive.

For example, if R = { (1,2) } and A = {1,2}, then R_ref = { (1,2), (1,1), (2,2) }.

Symmetric Closure

In the symmetric closure, we add the inverse pair to every pair to make the relation symmetric.

For example, if R = { (1,2) }, then R_sym = { (1,2), (2,1) }.

Transitive Closure

In the transitive closure, we add every pair that follows from transitivity. This is the smallest transitive relation that contains the original relation.

In other words: if (a,b) ∈ R and (b,c) ∈ R, then (a,c) will also be in the transitive closure. For example, if R = { (1,2), (2,3) }, then R_trans = { (1,2), (2,3), (1,3) }.

Example Comparing the Three Closures

Let A = {1,2,3} and R = { (1,2), (2,3) }.

• Reflexive closure: { (1,2), (2,3), (1,1), (2,2), (3,3) }
• Symmetric closure: { (1,2), (2,1), (2,3), (3,2) }
• Transitive closure: { (1,2), (2,3), (1,3) }

Properties

• The closure is always the smallest relation that satisfies the given property.
• The reflexive closure always includes all (a,a) pairs.
• The symmetric closure always includes all inverse pairs.
• The transitive closure includes every connection that follows from chains of intermediate elements.

Summary

Relation closures allow us to supplement a relation with the necessary pairs to make it reflexive, symmetric, or transitive. This is crucial in mathematics, as many proofs and algorithms are built on these.

Practice Exercise