Relation contains Composite with Self iff Transitive

From ProofWiki

Jump to: navigation, search

Theorem

A relation $\mathcal R$ is transitive iff:

$\mathcal R \circ \mathcal R \subseteq \mathcal R$

where $\circ$ denotes composite relation.

First, suppose $\mathcal R$ is transitive.

$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle \left({x, z}\right)$	$\in$	$\displaystyle \mathcal R \circ \mathcal R$	$\displaystyle $	$\displaystyle $	$\displaystyle $
$\displaystyle $	$\displaystyle \implies$	$\displaystyle $	$\displaystyle \exists y \in \mathcal R: \left({x, y}\right) \in \mathcal R$	$\land$	$\displaystyle \left({y, z}\right) \in \mathcal R$	$\displaystyle $	$\displaystyle $	$\displaystyle $	Definition of Composite Relation
$\displaystyle $	$\displaystyle \implies$	$\displaystyle $	$\displaystyle \left({x, z}\right)$	$\in$	$\displaystyle \mathcal R$	$\displaystyle $	$\displaystyle $	$\displaystyle $	$\mathcal R$ is transitive
$\displaystyle $	$\displaystyle \implies$	$\displaystyle $	$\displaystyle \mathcal R \circ \mathcal R$	$\subseteq$	$\displaystyle \mathcal R$	$\displaystyle $	$\displaystyle $	$\displaystyle $	Definition of Subset

$\Box$

Now suppose $\mathcal R$ is not transitive. Then:

$\displaystyle $	$\displaystyle $	$\displaystyle $	$\displaystyle \exists \left ({\left({x, y}\right) \in \mathcal R \land \left({y, z}\right) \in \mathcal R}\right): \left({x, z}\right)$	$\notin$	$\displaystyle \mathcal R$	$\displaystyle $	$\displaystyle $	$\displaystyle $	Definition of Non-Transitive
$\displaystyle $	$\displaystyle \implies$	$\displaystyle $	$\displaystyle \exists \left({x, z}\right) \in \mathcal R \circ \mathcal R: \left({x, z}\right)$	$\notin$	$\displaystyle \mathcal R$	$\displaystyle $	$\displaystyle $	$\displaystyle $	Definition of Composite Relation
$\displaystyle $	$\displaystyle \implies$	$\displaystyle $	$\displaystyle \mathcal R \circ \mathcal R$	$\not \subseteq$	$\displaystyle \mathcal R$	$\displaystyle $	$\displaystyle $	$\displaystyle $	Definition of Subset

Thus, by the Rule of Transposition, $\mathcal R \circ \mathcal R \subseteq \mathcal R \implies \mathcal R$ is transitive.

$\blacksquare$

Some sources use this as the definition of a transitive relation.

\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \left({x, z}\right)\)	\(\in\)	\(\displaystyle \mathcal R \circ \mathcal R\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle \exists y \in \mathcal R: \left({x, y}\right) \in \mathcal R\)	\(\land\)	\(\displaystyle \left({y, z}\right) \in \mathcal R\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of Composite Relation
\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle \left({x, z}\right)\)	\(\in\)	\(\displaystyle \mathcal R\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	$\mathcal R$ is transitive
\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle \mathcal R \circ \mathcal R\)	\(\subseteq\)	\(\displaystyle \mathcal R\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of Subset

\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \exists \left ({\left({x, y}\right) \in \mathcal R \land \left({y, z}\right) \in \mathcal R}\right): \left({x, z}\right)\)	\(\notin\)	\(\displaystyle \mathcal R\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of Non-Transitive
\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle \exists \left({x, z}\right) \in \mathcal R \circ \mathcal R: \left({x, z}\right)\)	\(\notin\)	\(\displaystyle \mathcal R\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of Composite Relation
\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle \mathcal R \circ \mathcal R\)	\(\not \subseteq\)	\(\displaystyle \mathcal R\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of Subset