Equivalence of Definitions of Transitive Relation

From ProofWiki
Jump to navigation Jump to search

Theorem

The following definitions of the concept of Transitive Relation are equivalent:

Definition 1

$\RR$ is transitive if and only if:

$\tuple {x, y} \in \RR \land \tuple {y, z} \in \RR \implies \tuple {x, z} \in \RR$

that is:

$\set {\tuple {x, y}, \tuple {y, z} } \subseteq \RR \implies \tuple {x, z} \in \RR$

Definition 2

$\RR$ is transitive if and only if:

$\RR \circ \RR \subseteq \RR$

where $\circ$ denotes composite relation.


Proof

Definition 1 implies Definition 2

Let $\RR$ be a relation which fulfils the condition:

$\tuple {x, y} \in \RR \land \tuple {y, z} \in \RR \implies \tuple {x, z} \in \RR$


Then:

\(\displaystyle \tuple {x, z}\) \(\in\) \(\displaystyle \RR \circ \RR\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle \exists y \in \RR: \tuple {x, y} \in \RR\) \(\land\) \(\displaystyle \tuple {y, z} \in \RR\) Definition of Composite Relation
\(\displaystyle \leadsto \ \ \) \(\displaystyle \tuple {x, z}\) \(\in\) \(\displaystyle \RR\) $\RR$ is transitive
\(\displaystyle \leadsto \ \ \) \(\displaystyle \RR \circ \RR\) \(\subseteq\) \(\displaystyle \RR\) Definition of Subset


Thus $\RR$ is transitive by definition 2.

$\Box$


Definition 2 implies Definition 1

Let $\RR$ be a relation that fulfils the condition:

$\RR \circ \RR \subseteq \RR$

Aiming for a contradiction, suppose $\RR$ does not fulfil the condition:

$\tuple {x, y} \in \RR \land \tuple {y, z} \in \RR \implies \tuple {x, z} \in \RR$

Then:

\(\displaystyle \exists \paren {\tuple {x, y} \in \RR \land \tuple {y, z} \in \RR}: \tuple {x, z}\) \(\notin\) \(\displaystyle \RR\) Definition of Non-Transitive Relation
\(\displaystyle \leadsto \ \ \) \(\displaystyle \exists \tuple {x, z} \in \RR \circ \RR: \tuple {x, z}\) \(\notin\) \(\displaystyle \RR\) Definition of Composition of Relations
\(\displaystyle \leadsto \ \ \) \(\displaystyle \RR \circ \RR\) \(\not \subseteq\) \(\displaystyle \RR\) Definition of Subset

This contradicts our statement that $\RR \circ \RR \subseteq \RR$.

Hence by Proof by Contradiction $\RR$ does fulfils the condition:

$\tuple {x, y} \in \RR \land \tuple {y, z} \in \RR \implies \tuple {x, z} \in \RR$


Thus $\RR$ is transitive by definition 1.

$\blacksquare$


Sources