# Equivalence of Definitions of Transitive Relation

## 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$