Category:Definitions/Transitive Closures

From ProofWiki
Jump to navigation Jump to search

This category contains definitions related to Transitive Closures in the context of Relation Theory.
Related results can be found in Category:Transitive Closures.


Smallest Transitive Superset

Let $\RR$ be a relation on a set $S$.


The transitive closure of $\RR$ is defined as the smallest transitive relation on $S$ which contains $\RR$ as a subset.


Intersection of Transitive Supersets

Let $\RR$ be a relation on a set $S$.


The transitive closure of $\RR$ is defined as the intersection of all transitive relations on $S$ which contain $\RR$.


Finite Chain

Let $\RR$ be a relation on a set or class $S$.


The transitive closure of $\RR$ is the relation $\RR^+$ defined as follows:

For $x, y \in S$, $x \mathrel {\RR^+} y$ if and only if for some $n \in \N_{>0}$ there exist $s_0, s_1, \dots, s_n \in S$ such that $s_0 = x$, $s_n = y$, and:

\(\ds s_0\) \(\RR\) \(\ds s_1\)
\(\ds s_1\) \(\RR\) \(\ds s_2\)
\(\ds \) \(\vdots\) \(\ds \)
\(\ds s_{n - 1}\) \(\RR\) \(\ds s_n\)


Union of Compositions

Let $\RR$ be a relation on a set $S$.

Let:

$\RR^n := \begin{cases} \RR & : n = 1 \\ \RR^{n-1} \circ \RR & : n > 1 \end{cases}$

where $\circ$ denotes composition of relations.

Finally, let:

$\ds \RR^+ = \bigcup_{i \mathop = 1}^\infty \RR^i$


Then $\RR^+$ is called the transitive closure of $\RR$.