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 clsoureby 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

zis a parent ofyfits the first clause (the "either" part) of theancestordefinition. In other words, every parent is an ancestor. Consequently, we can replace the fact thatzis a parent ofywith the fact thatzis an ancestor ofyto obtain

xis a parent of somezandzis an ancestor ofy.But this fits the second clause (the "or" part) of the ancestor definition. hence

xis an ancestor ofy.Consider the case of great grand parents. We have

xis a parent ofz1 andz1 is a parent ofz2 andz2 is a parent of y;

xis a parentz1 andz1 is a parent ofz2 andz2 is an ancestor of y;

xis a parent ofz1 andz1 is an ancestor of y;

xis an ancestor ofy.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*yiff eitherxRyor there is somezsuch thatxRzandzR*y.(Steinhart, pp. 32-33)

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