Concept
Transitive closure
Overview
In mathematics, the transitive closure R+ of a homogeneous binary relation R on a set X is the smallest relation on X that contains R and is transitive. For finite sets, "smallest" can be taken in its usual sense, of having the fewest related pairs; for infinite sets R+ is the unique minimal transitive superset of R.
For example, if X is a set of airports and x R y means "there is a direct flight from airport x to airport y" (for x and y in X), then the transitive closure of R on X is the relation R+ such that x R+ y means "it is possible to fly from x to y in one or more flights".
More formally, the transitive closure of a binary relation R on a set X is the smallest (w.r.t. ⊆) transitive relation R+ on X such that R ⊆ R+; see Lidl & Pilz (1998, p. 337). We have R+ = R if, and only if, R itself is transitive.
Conversely, transitive reduction reduces a minimal relation S from a given relation R such that they have the same closure, that is, S+ = R+; however, many different S with this property may exist.
Both transitive closure and transitive reduction are also used in the closely related area of graph theory.
Overview adapted from Wikipedia (CC BY-SA 4.0; see the article history for authors).
Possible passages
Found by search and not yet checked by a person; they may only mention the idea in passing.
This is nothing else than the necessity of abstract logic, which is the presupposition involved in the very fact of interrelated existence as disclosed in each immediate occasion of experience. The key to the pattern means this fact:—that from a select set of those general conditions, exemplified in any one and the same occasion, a pattern involving an infinite variety of other such conditions, also exemplified in…
Alfred North Whitehead, Science and the modern world
States what Transitive closure is.
It is supposed that we have a complete theory of points, straight lines, planes, and the order of points on planes--in fact, a complete theory of non-metrical geometry. We then enquire about congruence and lay down the set of conditions--or axioms as they are called--which this relation satisfies. It has then been proved that there are alternative relations which satisfy these conditions equally well and that there…
Alfred North Whitehead, The Concept of Nature The Tarner Lectures Delivered in Trinity College, November 1919
States what Transitive closure is.
However, even a cursory examination of a modern treatise on geometry makes clear what has taken place. For example, Professor Hilbert begins his _Grundlagen der Geometrie_, not with definition of points, lines, and planes, but with the assumption of three different systems of things (Dinge) of which the first, called…
John Dewey, Creative Intelligence
States what Transitive closure is.
Related ideas
- First-order logic
- Mathematics
- Intersection (set theory)
- Set (mathematics)
- Second-order logic
- Union (set theory)
- Computer science
- Equivalence relation
Place in the tradition
Part of Description logic.