• We know that some relations have these properties and some don't.
• The question here is: how can we turn a relation into one that does have these properties?

• … or maybe so it has some other property?

• $R_c$ has property $\mathbf{P}$.
• $R\subseteq R_c$.
• For every relation $S$ with $R\subseteq S$, if $S$ has property $\mathbf{P}$ then $R_c\subseteq S$.
• Note: not every relation and property has a closure, but we can find them for the ones we're interested in.

Theorem: The reflexive closure of a relation $R$ is $R\cup \Delta$.

Proof Idea: Any reflexive relation containing $R$ must contain $R\cup \Delta$. If not it would either not be a superset of $R$ or not be reflexive.

• That is, the reflexive closure of $<$ is $\le$

Corollary: If $R$ is a reflexive relation, the reflexive closure of $R$ is $R$.

Proof: If $R$ is reflexive, then $\Delta\subseteq R$. Thus, $R\cup \Delta= R$.∎

• We already have a way to express all of the pairs in that form: $R^{-1}$.

Theorem: The symmetric closure of a relation $R$ is $R\cup R^{-1}$.

Proof Idea: Any symmetric relation containing $R$ must contain $R\cup R^{-1}$. If not it would either not be a superset of $R$ or not be symmetric.

• So, the symmetric closure of $<$ is $\ne$.

Corollary: If $R$ is a symmetric relation, the symmetric closure of $R$ is $R$.

Proof: If $R$ is symmetric, then by an earlier theorem, $R=R^{-1}$. Thus, $R\cup R^{-1}= R$.∎

• But that doesn't work. Consider the relation with this graph:

• If we add all of the edges as described, we get this:

• That's still not transitive: we still need $(a,d)$ in the relation to make it transitive.

• We will say that this is a path of length $n$ from $x_0$ to $x_n$.
• If $x_0=x_n$, then we will call it a cycle or circuit.
• In the first example graph above, there is one path from $a$ to $d$.
• In the second, there are three: $a,b,c,d$ and $a,b,d$ and $a,c,d$.

• Paths are allowed to cross themselves, or even use the same edges multiple times.
• For example, in this graph, to get from $a$ to $d$, there are paths of length 3, 5, 7, 9, 11,…

Theorem: Let $R$ be a relation on $A$. There is a path from $a$ to $b$ of length $n$ in the graph of $R$ iff $(a,b)\in R^n$.

Proof: For $n=1$, the path must be a single edge. Such a path will exist if and only if $(a,b)\in R$.

Now assume for induction that the theorem is true for paths of length $n$ with $n\ge 1$. If there is a path of length $n+1$ from $a$ to $b$, then let $c$ be the last vertex in that path, so $(c,b)$ is the last edge, and the remainder of the path is length $n$ from $a$ to $c$. Thus $(a,c)\in R^n$ and by definition of relation composition, $(a,b)\in R^{n+1}$.

If $(a,b)\in R^{n+1}$, then there is a $c$ such that $(a,c)\in R^{n}$ and $(c,b)\in R$. From the inductive hypothesis, there is a path of length $n$ from $a$ to $c$ and adding $(c,b)$ gives a path of length $n+1$ from $a$ to $b$.

So, we have a path of length $n+1$ iff $(a,b)\in R^{n+1}$, and by induction for all $n\ge 1$, we have a path of length $n$ iff $(a,b)\in R^n$.∎

• $R^n$ was the cities you can get between in exactly $n$ flights.
• We have now proved that is really true in the above theorem.
• It's then perfectly reasonable to ask what cities we can get between in any number of flights.
• $R^{*}$ gives us a notation for that (and formal definition of what we're talking about).
• If $(a,b)\in R^{*}$, then it is possible to take a series of flights to get from $a$ to $b$ (without taking the bus in between or something).

Lemma: For a transitive relation $R$, all $R^n$ are transitive.

Proof: Consider any $(a,b),(b,c)\in R^n$. From the above theorem, there is a path of length $n$ from $a$ to $b$ and from $b$ to $c$ in $R$. Then we have a path of length $2n$ from $a$ to $c$ in $R$.

Since $R$ is transitive, we can replace the edges in this path with their two-step counterparts (they must exist since $R$ is transitive). The $n=3$ case would look like this:

This constructs a path of length $n$ from $a$ to $c$. Thus, $(a,c)\in R^n$ and $R^n$ is transitive.∎

Theorem: The transitive closure of a relation $R$ is $R^{*}$.

Proof: In order for $R^{*}$ to be the transitive closure, it must contain $R$, be transitive, and be a subset of in any transitive relation that contains $R$. By the definition of $R^{*}$, it contains $R$.

If there are $(a,b),(b,c)\in R^{*}$, then there are $j$ and $k$ such that $(a,b)\in R^j$ and $(b,c)\in R^k$. Then $(a,c)\in R^{j+k}\subseteq R^{*}$. Thus, $R^{*}$ is transitive.

Now suppose we have a transitive relation $S$ with $R\subseteq S$. Since $S$ is transitive, $S^n$ is transitive for all $n$ (from the lemma) and then from an earlier theorem, $S^n\subseteq S$. It then follows that $S^{*}=\bigcup_{n=1}^{\infty} S^n\subseteq S$.

Since $R\subseteq S$, we know that any path in $R$ must also be a path in $S$ so $R^{*}\subseteq S^{*}$. Thus, $R^{*}\subseteq S^{*}\subseteq S$. So, $R^{*}$ is a subset of any transitive relation that contains $R$ and it meets all of the criteria required to be the transitive closure.∎

• We found that the matrix of $R^2$ was: $$\mathbf{M}_{R^2}=\left[\begin{smallmatrix}1&1&1&0 \\ 1&1&1&0 \\ 1&1&1&0 \\ 0&0&0&1 \end{smallmatrix}\right]$$
• This is also the transitive closure: $R\subseteq R^2$, and if we continue to compose with $R$ the matrix doesn't change: ${R^2}={R^3}={R^4}=\cdots$.

• It's not transitive, so $R^*$ might be interesting.
• We established that $R^2$ was the relation containing all pairs $(a,a+2)$.
• Similarly, $R^k$ is the set of $(a,a+k)$ for each integer $a$.
• The union of all of these is $R^{*}=\{(a,b)\mid a<b\}$.
• That is, it is the relationship “less than” over the integers.
• That's a little surprising.

• Unfortunately, since it's a union of infinitely many things, it's not exactly practical to compute.
• But it turns out that we don't actually need to compute an infinite number of $R^n$ to get the transitive closure (of a finite set).

Theorem: Let $R$ be a relation on $A$ with $|A|=n$. If there is a path from $a$ to $b$ in $R$, then there is a path with at most $n$ steps.

Proof: Suppose there is a path from $a$ to $b$ in $R$. Let $m$ be the length of the shortest such path. Assume for contradiction that $m> n$.

Since there are only $n$ vertexes in the graph of $R$, by the pigeonhole principle, the path from $a$ to $b$ must pass by at least one of them twice. That is, there must be a loop in the graph:

We can form a shorter path from $a$ to $b$ by simply removing the loop. This contradicts the assumption that the path was the shortest. Thus, $m\le n$.∎

• There may be more paths of length $>n$, but they connect elements that were already connected by some other path.

• Let's assume we're representing our relation as a matrix as described earlier.
• When we use $R$ in the algorithm, we mean $\mathbf{M}_R$: the $n\times n$ matrix described earlier.
• $\odot$ denotes the operation to compute the composition of two relations.
• Calculating one entry in the matrix for $A\odot B$ requires computing $(a_{i1}\wedge a_{1j})\vee (a_{i2}\wedge a_{2j})\vee\cdots \vee (a_{in}\wedge a_{nj})$.
• So computing one entry takes $\Theta(n)$ steps, and calculating the whole matrix for a composition takes $\Theta(n^3)$.

procedure transitive_closure(R)
    C = R
    P = R
    for k from 2 to n:
        P = P ⊙ R             # P = R^k
        C = C ∨ P             # C = R ∪ R^2 ∪ ... ∪ R^k
    return C

• That's pretty bad, but the best I could do.
• Fortunately, there are people smarter than me.

• Label the elements of $A$ as $a_1,a_2,\ldots,a_n$.

• The path will be something like $a,i_1,i_2,\ldots,i_k,b$, where $(a,i_1),(i_1,i_2),\ldots,(i_k,b)\in R$.
• We will call the $i_j$ interior vertices of that path.
• That is, things in the path that aren't the endpoints.

• In particular, we are interested in path that use only the first $k$ elements of $A$ as interior vertices.

• There is a path using $a_1,a_2\ldots,a_{k-1}$, or
• There is a path that uses $a_k$: $a,\ldots,a_k,\ldots,b$.

• Let $\mathbf{W}_k$ be the binary matrix where there is a 1 in entry $i,j$ if you can get from $a_i$ to $a_j$ using only interior vertices $a_1,\ldots,a_k$.
• We'll call the $i,j$ element of this matrix $w_{ij}^{(k)}$.

• It is the elements you can get between using no interior vertices.
• That is, $\mathbf{M}_R=\mathbf{W}_0$.

• It gives the nodes we can get between using any combination of interior vertices.

• $w_{ij}^{(k-1)}$ is one, or
• $w_{ik}^{(k-1)} \wedge w_{j,k}^{(k-1)}$ is one.

procedure warshall(R):
    W = R
    for k from 1 to n
        for i from 1 to n
            for j from 1 to n
                w[i,j] = w[i,j] ∨ (w[i,k] ∧ w[k,j])
    return W

• At the end of each iteration of the “for k”, W is $\mathbf{W}_k$
• [Actually, it might be somewhere between $\mathbf{W}_k$ and $\mathbf{W}_{k+1}$ since we might overwrite other zeros with ones as we process the matrix.]

• Our naïve algorithm above was $\Theta(n^4)$.
• A pretty good improvement.

• Not very useful for transitive closure, but useful as we move on to graph theory.