Equivalence of Definitions of Transitive Closure (Relation Theory)

From ProofWiki
Jump to navigation Jump to search

Theorem

The following definitions of the concept of Transitive Closure in the context of Relation Theory are equivalent:

Definition 1

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.

Definition 2

Let $\mathcal R$ be a relation on a set $S$.


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

Definition 3

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


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

For $x, y \in S$, $x \mathrel {\mathcal R^+} 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:

\(\displaystyle s_0\) \(\mathcal R\) \(\displaystyle s_1\)
\(\displaystyle s_1\) \(\mathcal R\) \(\displaystyle s_2\)
\(\displaystyle \) \(\vdots\) \(\displaystyle \)
\(\displaystyle s_{n - 1}\) \(\mathcal R\) \(\displaystyle s_n\)

Definition 4

Let $\mathcal R$ be a relation on a set $S$.

Let:

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

where $\circ$ denotes composition of relations.

Finally, let:

$\displaystyle \mathcal R^+ = \bigcup_{i \mathop \in \N} \mathcal R^i$


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


Proof

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

First note that by Smallest Element is Unique, once it has been shown that some relation, $\QQ$, is the smallest transitive superset of $\RR$, it is the only such.

Thus we need only prove that each of the other definitions lead to relations with this property.


First we have:


Intersection of Transitive Supersets is Smallest Transitive Superset

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


Then the intersection of all transitive relations on $S$ that contain $\RR$ is the smallest transitive relation on $S$ that contains $\RR$.


The Finite Chain Definition is Equivalent to the Union of Compositions Definition

Follows from the definition of composition of relations.

$\blacksquare$


Union of Compositions is Smallest Transitive Superset

$\RR^+$ is Transitive

By Relation contains Composite with Self iff Transitive, we can prove that $\RR^+$ is transitive by proving the following:

$\RR^+ \circ \RR^+ \subseteq \RR^+$


Let $\tuple {a, c} \in \RR^+ \circ \RR^+$.

Then:

$\exists b \in S: \tuple {a, b} \in \RR^+, \tuple {b, c} \in \RR^+$

Thus:

$\exists n \in \N: \tuple {a, b} \in \RR^n$
$\exists m \in \N: \tuple {b, c} \in \RR^m$

From Composition of Relations is Associative:

$\RR^{n + m} = \RR^n \circ \RR^m$

so:

$\tuple {a, c} \in \RR^{n + m} \subseteq \RR^+$

Since this holds for all $\tuple {a, c} \in \RR^+ \circ \RR^+$:

$\RR^+ \circ \RR^+ \subseteq \RR^+$

Thus $\RR^+$ is transitive.

$\Box$


$\RR^+$ contains $\RR$

$\RR \subseteq \RR^+$ by Set is Subset of Union.


$\RR^+$ is Smallest

Let $\RR'$ be a transitive relation on $S$ such that $\RR \subseteq \RR'$.

We must show that $\RR^+ \subseteq \RR'$.

Let $\tuple {a, b} \in \RR^+$.

That is:

$a \mathrel \RR b$

Then:

$\exists n \in \N: \tuple {a, b} \in \RR^n$

Thus by the definition of composition of relations, there exists $x_{n-1} \in S$ such that:

$a \mathrel {\RR^{n - 1} } x_{n - 1} \land x_{n - 1} \mathrel \RR b$

Likewise there exists $x_{n-2} \in S$ such that:

$a \mathrel {\RR^{n - 2} } x_{n - 2} \land x_{n - 2} \mathrel \RR x_{n - 1}$

And so forth there exist elements $x_0, \dots, x_n \in S$ such that:

$x_0 = a$
$x_n = b$
$\forall k \in \N_n: x_k \mathrel \RR x_{k + 1}$

Since $\RR \subseteq \RR'$:

$\forall k \in \N_n: x_k \mathrel {\RR'} x_{k + 1}$

Since $\RR'$ is transitive:

$a \mathrel {\RR'} b$

That is:

$\tuple {a, b} \in \RR'$

Since this holds for all $\tuple {a, b} \in \RR^+$:

$\RR^+ \subseteq \RR'$

Since this holds for all transitive relations $\RR'$ that contain $\RR$:

$\RR^+$ is the smallest transitive relation containing $\RR$.

$\blacksquare$


Finite Chain Definition gives Smallest Transitive Superset

Let $S$ be a set or class.

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

Let $\RR^+$ be the transitive closure of $\RR$ by the finite chain definition.

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

$\forall k \in \N_n: s_k \mathrel \RR s_{k+1}$


Then $\RR^+$ is transitive and if $\QQ$ is a transitive relation on $S$ such that $\RR \subseteq \QQ$ then $\RR \subseteq \QQ$.


Also see