Transitive envelope (relation)

The transitive envelope or the transitive closure of a (two-digit) relation is an extension of this relation which - to put it simply - additionally contains all indirectly reachable pairs (and is thus transitive ). The transitive hull can be calculated with the Floyd-Warshall algorithm .

The reflexive-transitive envelope or the reflexive-transitive closure of the relation is obtained by adding the pairs on the diagonal that are still missing for reflexivity to the transitive envelope .

Illustrative example

Illustration of the example: solid arrows indicate direct relationships, dashed arrows the relationships in the transitive envelope

Let there be a relation "direct superior" with the following relationships:

• C is the direct superior of D and E.
• B is C's direct superior
• A is B's direct superior

The transitive envelope of this relation now also contains the indirect superiors:

• A is the superior of B, C, D, E
• B is the superior of C, D, E
• C is the superior of D and E.

Mathematical definition

The transitive envelope of a two-digit relation on a set is given by: ${\displaystyle \operatorname {t} (R)\equiv R^{+}}$ ${\displaystyle R}$ ${\displaystyle M}$

${\displaystyle x\ \operatorname {t} (R)\ y:\Leftrightarrow x\ R^{+}\ y:\Leftrightarrow \exists n\geq 0\ \exists x_{1},\dots ,x_{n}\in M:x\,R\,x_{1}\,R\,x_{2}\,R\dots \,R\,x_{n}\,R\,y}$

The reflexive envelope is simply the union with the diagonal (identity), which is how reflexivity is achieved: ${\displaystyle \operatorname {r} (R)\equiv R^{?}}$

${\displaystyle x\ \operatorname {r} (R)\ y:\Leftrightarrow x\ R^{?}\ y:\Leftrightarrow x=y\lor x\ R\ y}$, d. H. (see identity relation ). ${\displaystyle R^{?}=\mathrm {I} _{M}\cup R}$

The reflexive-transitive envelope then results from ${\displaystyle R^{*}}$

${\displaystyle x\ R^{*}\ y:\Leftrightarrow x=y\lor x\ R^{+}\ y}$

Supplement: Another shell formation of this type is the symmetrical shell:

${\displaystyle x\ \operatorname {s} (R)\ y:\Leftrightarrow x\ R^{\leftrightarrow }\ y:\Leftrightarrow x\ R\ y\ \lor \ y\ R\ x}$, equivalent to the definition (see inverse relation ). ${\displaystyle \operatorname {s} (R)\equiv R^{\leftrightarrow }:=R\cup R^{-}}$

For the equivalence envelope see: Equivalence relation §equivalence envelope .

Examples

• Is given by the two pairs and , then additionally contains the pair . For the other couples , and in addition . ${\displaystyle R}$ ${\displaystyle (a,b)}$ ${\displaystyle (b,c)}$ ${\displaystyle R^{+}}$ ${\displaystyle (a,c)}$ ${\displaystyle R^{*}}$ ${\displaystyle (a,a)}$ ${\displaystyle (b,b)}$ ${\displaystyle (c,c)}$
• If the successor relation is on the set of natural numbers (i.e. ), then the greater than relation results as the transitive envelope of . The reflexive-transitive envelope is the greater than or equal to relation . ${\displaystyle R}$ ${\displaystyle a\,R\,b:\Longleftrightarrow a=b+1}$ ${\displaystyle R}$ ${\displaystyle >\ }$ ${\displaystyle \geq }$
• The relation on the set of the 26 letters of the Latin alphabet is given by and (in the usual arrangement of the alphabet) are directly adjacent. The transitive envelope of results in the all relation , i.e. the relation that contains all pairs above the basic set (because by multiple transition to a neighbor one can reach any other letter from a letter). Since is already reflexive, applies here . ${\displaystyle R}$ ${\displaystyle \alpha \,R\,\beta :\Longleftrightarrow }$ ${\displaystyle \alpha \ }$ ${\displaystyle \beta \ }$ ${\displaystyle R}$ ${\displaystyle R^{+}}$ ${\displaystyle R^{*}=R^{+}}$

properties

• ${\displaystyle R^{+}}$is the smallest transitive relation that contains. ${\displaystyle R}$
• ${\displaystyle R^{*}}$is the smallest reflexive and transitive relation that contains. ${\displaystyle R}$
• The transition to the transitive envelope is an envelope operator in the abstract sense (which the name already suggests). The same applies to the reflexive-transitive envelope.
• The transitive envelope of a relation on a set is the intersection of all transitive supersets of , that is ${\displaystyle R}$ ${\displaystyle M}$ ${\displaystyle R}$

  ${\displaystyle R^{+}=\bigcap \{S\subseteq M\times M|S\ \mathrm {ist\ transitiv} ,R\subseteq S\}}$.

The set over which the average is formed here is not empty, since it always contains the all relation (i.e. ). ${\displaystyle M\times M}$

• The analogous statement applies to the reflexive-transitive envelope.
• With the help of the powers regarding the concatenation of relations, the two envelopes of a relation can also be written as an (infinite) union : ${\displaystyle \circ }$ ${\displaystyle R}$

  ${\displaystyle R^{+}=R^{1}\cup R^{2}\cup R^{3}\cup \dots }$

  ${\displaystyle R^{*}=R^{0}\cup R^{1}\cup R^{2}\cup \dots }$

• In connection with a relation on a set , a path is understood to be a finite sequence of elements from with for all with . The length of the sequence reduced by 1 is the length of the path. The path leads from the starting point to the end point . The reflexive-transitive envelope generated by it can be described as a relation by the fact that it applies exactly when there is a path from to . The same applies for the transitive closure , that if and only if there is a way of to is of a length greater than the 0th ${\displaystyle R}$ ${\displaystyle M}$ ${\displaystyle c=(c_{0},c_{1},\dotsc ,c_{n})}$ ${\displaystyle M}$ ${\displaystyle c_{i}\ R\ c_{i+1}}$ ${\displaystyle i}$ ${\displaystyle 0\leq i<n}$ ${\displaystyle n\in \mathbb {N} _{0}}$ ${\displaystyle c_{0}}$ ${\displaystyle c_{n}}$
  ${\displaystyle R}$ ${\displaystyle R^{*}}$ ${\displaystyle a\ R^{*}\ b}$ ${\displaystyle a}$ ${\displaystyle b}$
  ${\displaystyle R^{+}}$ ${\displaystyle a\ R^{+}\ b}$ ${\displaystyle a}$ ${\displaystyle b}$
• There are a finite number of elements with , and for each or . ${\displaystyle c_{0},c_{1},\dotsc ,c_{n}}$ ${\displaystyle c_{0}=a}$ ${\displaystyle c_{n}=b}$ ${\displaystyle 0\leq i<n}$ ${\displaystyle c_{i}\ R\ c_{i+1}}$ ${\displaystyle c_{i+1}\ R\ c_{i}}$
• The following applies to reflexive relations . However, it can also happen for non- reflexive relations that the transitive closure is already reflexive. ${\displaystyle R}$ ${\displaystyle R^{*}=R^{+}}$
• There is a quasi-order for any relations . ${\displaystyle R}$ ${\displaystyle R^{*}}$
• Idempotency the Hülloperatoren: . ${\displaystyle R^{+\!+}=R^{+},R^{*\!*}=R^{*},R^{?\!?}=R^{?},R^{\leftrightarrow \leftrightarrow }=R^{\leftrightarrow }}$

Applications

In theoretical computer science , derivations are defined in a formal grammar as a series of derivation steps. The derivability is the reflexive-transitive conclusion of the transition relation . ${\displaystyle v\Rightarrow w}$ ${\displaystyle \Rightarrow ^{*}}$ ${\displaystyle \Rightarrow }$

Transitive reduction

The counterpart to the transitive envelope is the transitive reduction. A transitive reduction of a relation is a minimal relation , so that , thus a minimal relation with the same transitive envelope. ${\displaystyle R}$ ${\displaystyle R^{\prime }}$ ${\displaystyle R^{+}=(R^{\prime })^{+}}$

There are relations for which no transitive reduction exists, as well as those for which several different transitive reductions exist. For directed finite acyclic graph , however, the transitive reduction exists and is unique: . In this case, the following figure shows graphs that correspond to a non-transitory binary relation (left) and its transitive reduction (right): ${\displaystyle R^{\prime }=R^{+}\setminus (R^{+})^{2}}$

Related terms:

• Reflexive reduction: The reflexive reduction of a relation to a set is the minimal relation , with the same reflexive envelope. That means that is equivalent to or . ${\displaystyle R}$ ${\displaystyle M}$ ${\displaystyle R^{\neq }}$ ${\displaystyle a\;R^{\neq }\;b}$ ${\displaystyle aRb\land a\neq b}$ ${\displaystyle R^{\neq }=R\setminus \mathrm {I} _{M}}$
• There is no comparable concept of a symmetrical reduction of relations, such as the (symmetrical) relation . ${\displaystyle R\cap R^{-}}$ 

See also

• Transitive envelope (quantity)

Web links

• Joost-Pieter Katoen : Data structures and algorithms , RWTH Aachen University, Chair for Computer Science 2, July 6, 2010 (accessed on April 16, 2018)
• Daniel Reinhold, Shenja Leiser: Algorithms for Computing the Transitive Shell of a Database Relation , Humboldt University Berlin (Wayback Machine), February 6, 2006 (accessed April 16, 2018)
• Hans-Rudolf Metz: Relations, Paths, Hüllen , FH Gießen-Friedberg, Discrete Mathematics (Computer Science), SS 2010 - Script 16, June 2, 2010 (accessed May 1, 2018)
• Renate Winter: Transitive envelope of a relation , University of Halle, Theoretical Computer Science, WS 2010 (accessed on April 16, 2018)

Individual evidence

1. ↑ ^{a b c} Kenneth H. Rosen: Closure of binary relation , in: CS381 Discrete Structures, Old Dominion University , Norfolk, Virginia, in 1999. The author uses the notations , , . ${\displaystyle \operatorname {t} (R)}$ ${\displaystyle \operatorname {r} (R)}$ ${\displaystyle \operatorname {s} (R)}$
2. ↑ HW Lang: Mathematical Basics: Quantity, Relation, Figure , Hochschule Flensburg, 1997-2016, §Relation
3. ↑ Notation as in Symmetric Closure , on: ProofWiki from September 12, 2016 ${\displaystyle R^{\leftrightarrow }}$
4. ↑ Kenneth Rosen: Closures of Relations , Rutgers School of Arts and Sciences, Department of Computer Sciences (CS), Discrete Mathematics and Its Applications: Section 6.4, p. TP 2f. That of the author is . ${\displaystyle \operatorname {s} (R)}$
5. ↑ See Metz 2010, p. 1. In the graph-theoretical sense, it is a directed path (without edge weights) of the given length.
6. ↑ Eric Weisstein: Transitive Reduction , Wolfram Research: Wofram MathWorld 1999-2018
7. ↑ See Transitive reduction (English)
8. ↑ Eric Weisstein: Reflexive Reduction , Wolfram Research: Wofram MathWorld 1999-2018
9. ↑ Notation follows [1] , based on: ProofWiki of February 21, 2018
10. ↑ Symmetric Closure §Notes , on: ProofWiki from September 12, 2016