Section 14.1 Basic closures
Many times we will have a mathematical object in hand but desire it to have a property it does not have. For example, suppose we have the natural numbers \(\mathbb{N}\text{,}\) but would like to be able to subtract these numbers. Sometimes we will be successful. For instance, \(5-3=2 \in \mathbb{N}\text{.}\) But othertimes we will not; say, in the case of \(3-5=-2\text{,}\) which is not a natural number.
Then we construct a new object, the closure of the original, that contains the same data and the minimum amount of extra data required to allow the desired property. In the case of closing \(\mathbb{N}\) under subtraction, the result is the set of integers \(\mathbb{Z}\text{,}\) the smallest set containing both the natural numbers and the results of subtracting any two natural numbers.
A closure \(X^*\) of the set \(X\) under the property \(P\) must satisfy the following three conditions:
\(X^*\) must have property \(P\text{.}\)
\(X \subseteq X^*\text{.}\) In other words, \(X^*\) must be a superset of \(X\text{.}\) ("Subset" and "superset" are converses.)
For any \(S\) such that \(S\) has property \(P\) and \(X \subseteq S\text{,}\) it must also be the case that \(X^* \subseteq S\text{.}\) In this sense \(X^*\) is minimal among the supersets of \(X\) that have \(P\text{.}\)
In this chapter we will close a relation under reflexiveness, symmetry, and transitivity. The third of these will require a detour into the operation of composing relations, where we will use the tools of Boolean matrices we have learned.
Subsection 14.1.1 Reflexive closure
In this section, \(R\) is a relation on the set \(X\text{.}\) The set \(X\) need not be finite unless we want to talk about a matrix or a directed graph.
Example 14.1.1.
Suppose we have the relation \(R = \{(a,b), (a,c), (b,b), (c,b)\}\) on \(\{a,b,c\}\text{.}\) To construct the reflexive closure of \(R\text{,}\) we must add the pairs \((a,a)\) and \((c,c)\text{.}\) (Notice \((b,b)\in R\) already.) So the reflexive closure of \(R\) is the new relation
Recall that the diagonal relation on a set \(X\) is the relation
The diagonal relation is the smallest reflexive relation on a set.
Definition 14.1.2.
Given a relation \(R\) on a set \(X\text{,}\) the reflexive closure of \(R\) is the relation \(R \cup \Delta\text{.}\)
In other words, to close a relation under reflexiveness it is only necessary to ensure it contains all the pairs in the diagonal relation.
An aside: is the above really the right definition of reflexive closure? Well, no. In the Form of discrete math textbook in the library of Heaven, the definition of closure is the one given in the preamble to the section — in this case, the smallest reflexive superset of \(R\) — and then it is a theorem that \(R \cup \Delta\) is the reflexive closure. (It is also a theorem that a closure is necessarily unique, but this is easier to prove and only needs proving once for all closures.) Fortunately for us, this is not the Form of the discrete math textbook in the library of Heaven; so we will take this as the definition. If you like, as an exercise, you can define the reflexive closure as the smallest reflexive superset of \(R\) and then prove both that it is unique and that one of the sets that works is \(R \cup \Delta\) (hence, the only set that works is \(R \cup \Delta\)).
Subsection 14.1.2 Symmetric closure
Next we will construct the symmetric closure of any relation.
Example 14.1.3.
Again take \(R = \{(a,b), (a,c), (b,b), (c,b)\}\) on \(\{a,b,c\}\text{.}\) To construct the symmetric closure of \(R\text{,}\) we must add the pairs \((b,a)\text{,}\) \((c,a)\text{,}\) and \((b,c)\text{.}\) (As previously discussed, \((b,b)\) is invertible automatically.) Therefore the symmetric closure of \(R\) is
Definition 14.1.4.
Given a relation \(R\) on a set \(X\text{,}\) its inverse relation is the relation
Example 14.1.5.
You have seen this before. If \(f\) is a function that has an inverse and \((x,y) \in f\) (meaning \(y=f(x)\)), then \((y,x) \in f^{-1}\) (meaning \(x=f(y)\)).
Definition 14.1.6.
Given a relation \(R\) on a set \(X\text{,}\) the symmetric closure of \(R\) is the relation \(R \cup R^{-1}\text{.}\)
Subsection 14.1.3 The idea of the transitive closure
We can't define a transitive closure yet, but we can probably build one. Let's do an example.
Example 14.1.7.
In the past two weeks, Alicia has hung out with Bob. Bob and Carlos are roommates, and Davina was Carlos's cashier at the grocery store the other day. Davina lives with her boyfriend, Erik. If Alicia gets sick, who is at risk?
The underlying relation is
on the set \(\{a,b,c,d,e\}\) (where \(a\) refers to Alicia, etc.), the set of all pairs \((x,y)\) where \(x\) interacted with \(y\) over the past two weeks. The order of the arrows is defined by who could deliver Alicia's illness to whom (which is why we don't have \((c,b)\) even though Bob and Carlos live together). However, this is still not the relation that totally represents the spread of the illness, because if \(y\) was exposed to the illness by \(x\) and likewise \(z\) was exposed by \(y\text{,}\) then \(z\) could have caught something from \(x\text{.}\) So if \((x,y)\) and \((y,z)\) are in \(R\text{,}\) we would like \((x,z)\) to be in our relation. Therefore we are looking for the transitive closure of \(R\text{.}\)
Transitivity is best understood visually. Draw a directed graph with vertices representing \(a\text{,}\) \(b\text{,}\) \(c\text{,}\) \(d\text{,}\) and \(e\text{,}\) and draw the appropriate arrows from the relation. Then, draw the arrows “induced” by transitivity, as shown below.
Directed graph for the above relation. The element \(a\) is related to \(b\text{;}\) \(b\) is related to \(c\text{;}\) \(c\) is related to \(d\text{;}\) \(d\) is related to \(e\text{.}\)
The transitive closure for the relation above. The original arrows are included, as well as arrows from \(a\) to \(c\text{,}\) \(d\text{,}\) and \(e\text{;}\) from \(b\) to \(d\) and \(e\text{;}\) and from \(c\) to \(e\text{.}\) The new arrows are highlighted in red.
You can verify for yourself that the relation
is transitive.
If you understand that example, then you understand the idea of a transitive closure. It remains to put some formal machinery behind the idea, which is where the idea of composition comes in.