18.7. Closure of a Relation

Next let us define what we call as closure of a relation. So, what do we mean by this? So, imagine you are given a set A that may be finite or infinite and you are given a relation R over the set A that means a relation R is a subset of A x A and I have some abstract property P, it is some abstract property and I am interested to check whether the relation R over the set A satisfies this property P or not? If it is satisfies the property well and good. But, that may not be the case R that is given to you need not satisfy the property.

The closure of a relation is a way to expand the relation in order to make it satisfy a certain desired property, referred to as property P. This property can be anything abstract, such as being reflexive, symmetric, or transitive. The original relation R is a subset of ordered pairs from set A. If R satisfies property P, then no modifications are necessary. However, if it does not, we need to add new pairs to form a larger relation that meets the criteria of property P.

Think of a classroom where students have different kinds of relationships with each other—friends, classmates, study partners, etc. A 'closure' of the relation could mean expanding a group to ensure that everyone is included in a study group. If some pairs of students don’t know each other (thus the relation is incomplete), we can add pairs to ensure that study partners can also help each other, fulfilling the property of being able to study together.

So, my first abstract property is the reflexive property and this gives us what we call as reflexive closure of a relation. So, you are given a relation R over the set A and I am interested to see whether this relation R satisfies the reflexive property or not, reflexive over the set A, so that is what is the reflexive closure of the relation R. So, how can you construct a reflexive closure of R? Well you just take the union of R with all ordered pairs of the form (a, a) where a is present in your set A.

The reflexive closure of a relation R is constructed by ensuring that for every element 'a' in set A, the pair (a, a) is included in relation R. This is done by taking the union of R with the set of all pairs (a, a) for all 'a' in A. If (a, a) is already in R, including it again has no effect. This ensures that the relation is reflexive, meaning every element is related to itself.

Imagine a company where each employee has to have a report with themselves to ensure performance evaluations. If no employee has created their own report, then we need to ensure that for every employee, there is a report that says, for example, "Employee A has a report on Employee A". By adding such pairs, every employee can now see their own performance, fulfilling the requirement of being able to evaluate oneself.

Now, let us take the case when my abstract property P is the symmetric property. So, again, I am given a relation R defined over the set A and I am interested to form a symmetric closure of R. Why I am calling it closure? Because I am trying to put a layer over, I am trying to enclose the original relation R and get a relation which has the original R as well as it satisfies the property P that is why it is called a closure.

To create the symmetric closure of a relation R, we need to ensure that if (a, b) is in R, then (b, a) must also be included in our new relation. This is achieved by forming the inverse of the relation R, which consists of all pairs (b, a) for every pair (a, b) in R. The union of R and its inverse gives us the symmetric closure, which retains all original relationships while ensuring that the property of symmetry is satisfied.

Think about friendships; if Alice is friends with Bob (Alice, Bob), then Bob must be friends with Alice (Bob, Alice) for the friendship to be considered symmetric. If we originally have only the relationship (Alice, Bob), our task is to add the friendship in the opposite direction to create a symmetric closure, ensuring that friendships are mutual.

Now, what about the transitive closure? So, it turns out that finding transitive closure is not that simple, why so? Let me demonstrate that with an example. So, you might say that intuitively to find the transitive closure I add all ordered pairs of the form (a, c). Such that a is related to b as well as b is related to c in the relation R because only when I add such order tuples of the form (a, c) in the relation R, it will ensure that the transitive property is satisfied.

Finding the transitive closure can be complex because simply adding pairs of the form (a, c) when (a, b) and (b, c) exist is not always sufficient. In fact, to achieve a transitive closure, one may need to repeatedly check and add pairs until no more pairs can be added that would create a new relationship. This iterative process ensures that the established relationships are maintained across all connections in the transitive sense.

Consider a social network where friends of friends should be recognized as friends. If Alice is friends with Bob, and Bob is friends with Charlie, we not only need to recognize the direct friendships but also ensure that Alice can be considered a friend of Charlie as well. This means we must keep adding these indirect connections until all possible friend pairs are acknowledged, which mimics the process of expanding a transitive closure.

--