The Transitive Closure Of A Relation

The Transitive Closure of a Relation
Definition: The Transitive closure of a relation R is the smallest transitive relation containing R. It is denoted by R^∞ .

Example: Let A = {1, 2, 3, 4} and R = [(1, 2), (2, 3), (3, 4), (2, 1)] Find the transitive closure of R.
Solution: The digraph of R is

We note that from vertex 1, we have paths to the vertices 2, 3, 4 and 1. Note that path from 1 to 1proceeds from 1 to 2 to 1. Thus we see that the ordered
pairs (1, 1), (1, 2), (1, 3) and (1, 4) are in R∞. Starting from vertex 2, we have paths to vertices 2, 1, 3 and 4 so the ordered pairs (2, 1), (2, 2), (2, 3) and (2, 4) are in R∞. The only other path is from vertex 3 to 4, so we have

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

Example: Let R be the set of all equivalence relations on a set A. As such R consists of subsets of A X A and so R is a partially ordered set under the partial order of set inclusion. If R and S are equivalence relations on A, the same property may be expressed in relational notations as follows:

R ⊆ S if and only if x R y ->
x S y for all x y ∈ A.

Then (R, ⊆) is a poset. R is a lattice, where the meet of the equivalence relations R and S is their intersection R ∩ S and their join is (R ∪ S)∞, the transitive closure of their union.

Definition: Let (L, ≤) be a poset and let (L, ≥) be the dual poset. If (L, ≤) is a lattice, we can show that (L, ≥) is also a lattice. In fact, for any a and b in L, the L U B of a and b in (L, ≤) is equal to the GLB of a and b in (L, ≥). Similarly, the GLB of a and b in (L, ≤) is equal to L U B in (L, ≥).

The operation ∨ and ∧ are called dual of each other.

Example: Let S be a set and L = P(S). Then (L, ⊆) is a lattice and its dual lattice is (L, ⊇), where ⊇ represents “contains”. We note that in the poset (L, ⊇), the join A ∨ B is the set A ∩ B and the meet A ∧ B is the set A ∪ B.