Study Guides for Discrete Mathematics

Section 6.4 - Closure of Relations

A relation may or may not possess certain propertiessuch as reflexivity, symmetry and transitivity. When a relation does not possess some particular property P, it is often the case that we may add ordered pairs (elements) to the relation until it does possess P.

Closures

Reflexive closure:

Suppose that relation S has some property, P. If S Ê R and if for relation T Ê R, T Ê S then S is called the closure of R with respect to property P. Restated, S is contained in every relation with property P that contains R.

Some closures are easy to compute. For example, in order to create the reflexive closure of a relation R Í AXA, we need only start with R and add all elements of the form (a,a) to R where a Î A.

Example:

R = {(1, 2), (1, 3), (2, 2), (2, 3), (3,1)}

Transitive closure of R = {(1, 2), (1, 3), (2, 2), (2, 3), (3,1)} È {(1, 1), (3, 3)}

Definition:

The diagonal relation (denoted by D ) is defined on AXA as follows:

D = {(a, a) | a Î A}

It follows immediately that

Transitive closure of R = R È D

Symmetric closure:

Recall that R-1 = {(b, a) | (a, b) Î R}

Recall also that symmetry requires that (a, b) Î R Þ (b, a) Î R

Then, the symmetric closure of R = R È R-1 (Verify this for yourself)

Transitive closure:

Transitive closure is a little more complicated.

Recall that R is transitive iff (a, b) Î R /\ (b, c) Î R Þ (a, c) Î R

As with reflexivity and symmetry we may add elements to a relation R and create a new relation that is the transitive closure of R. However, the procedure may require an iterative process.

The transitive closure of R is often denoted R* for reasons which will become apparent.

We may find the transitive closure by examining every pair of elements of R where the second element of the first pair matches the first element of the second pair.

I.e. (a, b) Î R and (b, c) Î R.

Transitivity requires that (a, c) must also be an element of R. If it is not then we must add it to the new relation that we are building into the transitive closure. Let's call the new relation R'.

(Initially R' = R and when the process of adding edges is over R' = R*.)

After we have examined all such pairs of members of R and added the required edges to R' where needed we must then begin the same process again.

Why?

Because adding, say, (a, c) to R' may have created another qualifying pair (say, (a, c) and (c, d)) which did not exist before. In this case (a, d) will also have to be added to R'. This iterative process continues until no more new edges are added during a complete iteration or until we complete the nth iteration, (where n = |A|) whichever comes first.

Example:

Find the transitive closure of R Í AXA where R = {(a, b), (b, c), (c, d)} and

where a, b, c, d Î A

Let R' = R

First iteration

(a, b) Î R' /\ (b, c) Î R' Þ (a, c) Î R'

(b, c) Î R' /\ (c, d) Î R' Þ (b, d) Î R'

Second iteration

(a, b) Î R' /\ (b, d) Î R' Þ (a, d) Î R'

(a, c) Î R' /\ (c, d) Î R' Þ (a, d) Î R' (already added this element)

Third iteration

No new additions are generated. Therefore procedure is complete and R' = R*.

 

Connectivity relation:

If there is a path from node a to node b in the digraph of a relation R then (a, b) is an element of the connectivity relation.

The connectivity relation of R, R* = the transitive closure of R.

More formally, the transitive closure of R Í AXA = connectivity relation, R* = È RN where N = |A|. (See pg. 384).

NOTE: Keep in mind that, in general, the closure of a relation, R, with respect to a property P often may not exist.

Since a relation represented as a subset of a crossproduct is equivalent to the relation represented as a matrix or a digraph, methods exist that enable one to find the transitive closure using matrix or graph operations. (See pages 383 and 384 I the text). More specifically, for matrices, if MR is the matrix associated with a relation, R, then \/MRI (1<= I <= N) represents the transitive closure of R where R Í AXA and N = |A|. It is useful to note that the nonzero entries of MRK represent the paths of length K in the digraph representing R.

Warshall's Algorithm is a more efficient method of finding the transitive closure of a relation. The algorithm is adequately covered in the text on pages 388-389. The basic idea of the algorithm and the reason that it yields the efficiency improvement is the following. Each iteration of the algorithm is applied only to a part of the relation rather than the entire relation. More specifically, the ith iteration is applied only to the first i elements of A (where R Í AXA). The final iteration is applied to the entire relation and this is sufficient to find the transitive closure.