Composition of Relations is not Commutative

From ProofWiki
Jump to: navigation, search

Theorem

Composition of relations is, in general, not commutative:


That is, it is usually the case that:

$\mathcal R_1 \circ \mathcal R_2 \ne \mathcal R_2 \circ \mathcal R_1$

for relations $\mathcal R_1$ and $\mathcal R_2$.


Proof

Proof by Counterexample:

Let $\mathcal R_1 := \left({S, S, R_1}\right)$ and $\mathcal R_2 := \left({S, S, R_2}\right)$ be relations defined as:

Let:

$S = \left\{ {0, 1, 2}\right\}$
$R_1 = \left\{ {\left({0, 1}\right)}\right\}$
$R_2 = \left\{ {\left({1, 2}\right)}\right\}$

We have that:

$\mathcal R_1 \circ \mathcal R_2 = \left({S, S, \left\{ {\left({0, 2}\right)}\right\} }\right\}$

while:

$\mathcal R_2 \circ \mathcal R_1 = \left({S, S, \varnothing}\right\}$

$\blacksquare$


Sources