In mathematics, the transitive closure of a binary relation R on a set X is the smallest transitive relation on X that contains R. Wikibooks Wikiversity has more about this subject: School of Mathematics Wikiquote has a collection of quotations related to: Mathematics Look up Mathematics in Wiktionary, the free dictionary Wikimedia Commons has media related to: Mathematics Interactive Mathematics Miscellany and Puzzles — A collection of articles on various math topics, with interactive Java... In mathematics, the concept of binary relation, sometimes called dyadic relation, is exemplified by such ideas as is greater than and is equal to in arithmetic, or is congruent to in geometry, or is an element of or is a subset of in set theory. ... In mathematics, a set can be thought of as any collection of distinct things considered as a whole. ... In mathematics, a binary relation R over a set X is transitive if it holds for all a, b, and c in X, that if a is related to b and b is related to c, then a is related to c. ...

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. In mathematics, the intersection of two sets A and B is the set that contains all elements of A that also belong to B (or equivalently, all elements of B that also belong to A), but no other elements. ... In mathematics, an index set is another name for a function domain. ... In predicate logic, existential quantification is an attempt to formalize the notion that something (a logical predicate) is true for something, or at least one relevant thing. ...

We can describe the transitive closure of R in more concrete terms as follows. Define a relation T on X by saying xTy iff there exists a finite sequence of elements (x_i) such that x = x₀ and ↔ ⇔ ≡ For other possible meanings of iff, see IFF. In mathematics, philosophy, logic and technical fields that depend on them, iff is used as an abbreviation for if and only if. Common alternative phrases to iff or if and only if include Q is necessary and sufficient for P and P... In mathematics, a set is called finite if and only if there is a bijection between the set and some set of the form {1, 2, ..., n} where is a natural number. ... This is a page about mathematics. ...

x₀Rx₁, x₁Rx₂, …, x_n−1Rx_n, and x_nRy

Formal notation:

(for more info, see function composition)

It is easy to check that the relation T is transitive and contains R. Furthermore, any transitive relation containing R must also contain T, so T is the transitive closure of R. In mathematics, a composite function, formed by the composition of one function on another, represents the application of the former to the result of the application of the latter to the argument of the composite. ...

Demonstration that T is the smallest transitive relationship containing R

Let A be any set of elements.

Supposition: G_A transitive relationship R_AG_A T_AG_A. So, (a,b)G_A. So, that particular (a,b)R_A.

Now, by definition of T, we know that n (a,b)Rⁿ_A. Then, i, i < n e_iA. So, there is a path from a to b like this: aR_Ae₁R_A...R_Ae_(n-1)R_Ab.

But, by transitivity of G_A on R_A, i, i < n (a,e_i)G_A, so (a,e_(n-1))G_A (e_(n-1),b)G_A, so by transitivity of G_A, we get (a,b)G_A. A Contradiction of (a,b)G_A.

Therefore, (a,b)AA, (a,b)T_A (a,b)G_A. This means that TG, for any transitive G containing R. So, T is the smallest transitive relationship containing R.

Corollary

If R is transitive, then R = T.

Example

• If X is the set of humans (alive or dead) and R is the relation 'parent of', then the transitive closure of R is the relation "x is an ancestor of y."
• If X is a set of airports and xRy means "there is a direct flight from airport x to airport y", then the transitive closure of R is the relation "it is possible to fly from x to y in one or more flights."

Uses

Note that the union of two transitive relations need not be transitive. In order to preserve transitivity one must take the transitive closure. This occurs, for example, when taking the union of two equivalence relations or two preorders. In order to obtain a new equivalence relation or preorder one must take the transitive closure (reflexivity and symmetry—in the case of equivalence relations—are automatic). In set theory and other branches of mathematics, the union of a collection of sets is the set that contains everything that belongs to any of the sets, but nothing else. ... In mathematics, an equivalence relation on a set X is a binary relation on X that is reflexive, symmetric and transitive, i. ... This article is about the mathematics concept. ...

Relationship to complexity

In computational complexity theory, the complexity class NL corresponds precisely to the set of logical sentences expressible using first order logic together with transitive closure. This is because the transitive closure property has a close relationship with the NL-complete problem STCON for finding directed paths in a graph. Similarly, the class L is first order logic with the commutative, transitive closure. When transitive closure is added to second order logic instead, we obtain PSPACE. In computer science, computational complexity theory is the branch of the theory of computation that studies the resources required during computation to solve a given problem. ... In computational complexity theory, a complexity class is a set of problems of related complexity. ... In computational complexity theory, NL is the complexity class containing decision problems which can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space. ... First-order predicate calculus or first-order logic (FOL) is a theory in symbolic logic that permits the formulation of quantified statements such as there is at least one X such that. ... Overview ST Connectivity (Reachability) is a problem in computer science, specifically computational complexity theory of deciding if two vertices in a directed graph, labeled s and t are connected by a path. ... One major problem that has plagued graph theory since its inception is the lack of consistency in terminology. ... In computational complexity theory, L is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a logarithmic amount of memory space. ... In mathematical logic, second-order logic is an extension of either propositional logic or first-order logic which contains variables in predicate positions (rather than only in term positions, as in first-order logic), and quantifiers binding them. ... In complexity theory the class PSPACE, which equals NPSPACE by Savitchs theorem, is the set of decision problems that can be solved by a deterministic or nondeterministic Turing machine using a polynomial amount of memory and unlimited time. ...