Existence and Description
For any relation R, the transitive closure of R always exists. To see this, note that the intersection of any family of transitive relations is again transitive. Furthermore, there exists at least one transitive relation containing R, namely the trivial one: X × X. The transitive closure of R is then given by the intersection of all transitive relations containing R.
We can describe the transitive closure of R in more concrete terms as follows, intuitively constructing it step by step. To start, define
and, for ,
Each set in this construction takes the relation from the previous set, and adds any new elements necessary to make chains that are "one step" more transitive. The relation R+ is made by taking all of the together, which we write as
To show that R+ is the transitive closure of R, we must show that it contains R, that it is transitive, and that it is the smallest set with both of those characteristics.
- : contains all of the, so in particular contains .
- is transitive: every element of is in one of the, so must be transitive by the following reasoning: if and, then from composition's associativity, (and thus in ) because of the definition of .
- is minimal: Let be any transitive relation containing, we want to show that . It is sufficient to show that for every, . Well, since contains, . And since is transitive, whenever, according to the construction of and what it means to be transitive. Therefore, by induction, contains every, and thus also .
Read more about this topic: Transitive Closure
Famous quotes containing the words existence and, existence and/or description:
“We know then the existence and nature of the finite, because we also are finite and have extension. We know the existence of the infinite and are ignorant of its nature, because it has extension like us, but not limits like us. But we know neither the existence nor the nature of God, because he has neither extension nor limits.”
—Blaise Pascal (1623–1662)
“Every moment of one’s existence one is growing into more or retreating into less. One is always living a little more or dying a little bit.”
—Norman Mailer (b. 1923)
“The Sage of Toronto ... spent several decades marveling at the numerous freedoms created by a “global village” instantly and effortlessly accessible to all. Villages, unlike towns, have always been ruled by conformism, isolation, petty surveillance, boredom and repetitive malicious gossip about the same families. Which is a precise enough description of the global spectacle’s present vulgarity.”
—Guy Debord (b. 1931)