Skip to main content
  1. Life
  2. Education & Schools
  3. General Education

Transitive closure

See also

Transitive closure is when we want to turn an intransitive (that is, non-transitive) relation into a transitive one. Like Steinhart, we will be using the relation "is-an-ancestor-of" in order to demonstrate how transitive closures work. The student of set theory will have to pay extra special attention to the transitive closure process, since transitive closure constructions are a bit more complicated than the others we have looked at.

P = {(x, y) | x is a parent of y}.

"Ancestors include grand parents as well as parents. The grand parent relation is a repetition or iteration of the parent relation: a parent of a parent y is a grand parent of y. More precisely,

x is a grand parent of y iff (there ies some z)((x is a parent of z) & (z is a parent of y))."(Steinhart, p. 30)

This iteration can be symbolized "by using the notion of the composition of a relation with itself"(Steinhart, p. 30).

Composition, formally stated, looks like this:

R ∘ R = {(x, y) | (there is some z)((x, z) ∈ R & (z, y) ∈ R}.

The relation "is-a-grand-parent-of" can be symbolized P ∘ P.

Steinhart summarizes:

"x is a great grand parent of y iff (there is some z)((x is a parent of z) & (z is a grand parent of y)).

The definition of a great grand parent is the composition of the parent relation within itself two times: is-a-great-grand-parent = P ∘ P ∘ P"(Steinhart, p. 31).

Steinhart notes that repeatedly composing a relation with itself provides us with the powers of the set. Thus:

R^1 = R;

R^2 = R ∘ R = R^1 ∘ R;

R^3 = R ∘ R ∘ R = R^2 ∘ R;

R^n+1 = R^n ∘ R (Steinhart, p. 31)

He notes that, when using the relation of ancestry, this translates to:

is-a-parent-of = P^1

is-a-grand-parent-of = P^2

is-a-great-grand-parent-of = P^3

is-a-great-great-grand-parent-of = P^4 (Steinhart, p. 31)

"We've got your ancestors defined by generation. But how do we define your ancestors? We define them by taking the union of all generations. Your ancestors are your parents unioned with your grand parents unioned with your great great grand parents and so on. Formally

is-an-ancestor-of = P^1 ∪ P^2 ∪ P^3 ... ∪ P^n ... and so on endlessly.

We said the ancestor relation is the transitive closure of the parenthood relation. And we can generalize. Given a relation R, we denote its transitive clsoure by R*. And we define the transitive closure like this:

R* = R^1 ∪ R^2 ∪ R^3 ... ∪ R^n ... and so on endlessly"(Steinhart, p. 31).

In order to formalize this with greater precision, we can use natural numbers. Thus:

the transitive closure of R = R* = ∪{R^n | n is any number} (Steinhart, p. 32).

"An equivalence relation is reflexive, esymmetric, and transitive. So we can transform a relation R into an equivalence relation by taking its reflexive, symmetric, and transitive closures. Since we have to take three closures , there are several ways in which we can transform R into an equivalence relation. The order in which we take the symmetric and transitive closures makes a difference"(Steinhart, p. 32).

Let's look briefly at the notions of recursive definitions and ancestrals relative to the concept of the closure. An "ancestral" of a relation is its transitive closure. "For any relation R, its ancestral is R*"(Steinhart, p. 32). An example of a recursive definition, "The relation is defined in terms of itself in a logically valid [even though circular] way"(Steinhart, p. 32).

Thus, using the relation of ancestry:

"x is an ancestor of y iff either x is a parent of y or there is some z such that x is a parent of y or there is some z such that x is a parent of z and z is an ancestor of y"(Steinhart, p. 32).

Steinhart summarizes:

"The fact that z is a parent of y fits the first clause (the "either" part) of the ancestor definition. In other words, every parent is an ancestor. Consequently, we can replace the fact that z is a parent of y with the fact that z is an ancestor of y to obtain

x is a parent of some z and z is an ancestor of y.

But this fits the second clause (the "or" part) of the ancestor definition. hence

x is an ancestor of y.

Consider the case of great grand parents. We have

x is a parent of z1 and z1 is a parent of z2 and z2 is a parent of y;

x is a parent z1 and z1 is a parent of z2 and z2 is an ancestor of y;

x is a parent of z1 and z1 is an ancestor of y;

x is an ancestor of y.

The circularity in a recursive definition allows you to nest this sort of reasoning endlessly. We can do it for great great grand parents, and so on. Here's the general way to give the recursive definition of the ancestral of a relation:

xR* y iff either x R y or there is some z such that x R z and z R* y. (Steinhart, pp. 32-33)

Steinhart, Eric. "More Precisely: The Mathematics You Need To Do Philosophy." Broadview Press, 2009.

Advertisement

Life

  • Dan Savage
    Dan Savage cares about LGBT youth, bullying and saving lives
    Today's Buzz
  • Raku
    Teachers and students can use this summer to learn a new skill
    Camera
    15 Photos
  • Beach body
    Fitness: Earn your beach body badge with bootcamp classes
    Camera
    10 Photos
  • Greek wine
    Unwind with these delicious wines: The thrilling wines of Greece
    Camera
    7 Photos
  • Mandy Moore
    Exclusive interview with Celebrity Mandy Moore concerning animal activism
    Camera
    5 Photos
  • Educational family vacations
    Find out how to take an educational family vacation that doesn't break the bank
    Camera
    9 Photos