Ordering is Directed iff Composite with Inverse is Trivial Ordering

From ProofWiki
Jump to navigation Jump to search


Let $\struct {S, \RR}$ be an ordered set.

Then $\RR$ is a directed ordering if and only if:

$\RR^{-1} \circ \RR = S \times S$


$\circ$ denotes composite relation
$\RR^{-1}$ denotes inverse relation
$S \times S$ denotes the trivial relation, that is, the Cartesian product of $S$ with itself.


We are given that $\RR$ is an ordering.

Sufficient Condition

Let $\RR$ be a directed ordering on $S$.

Then by definition:

$\forall x, y \in S: \exists z \in S: x \mathrel \RR z \land y \mathrel \RR z$

By definition of inverse relation:

$\forall x, y \in S: \exists z \in S: z \mathrel {\RR^{-1} } x \land z \mathrel {\RR^{-1} } y$

By definition of composite relation

$\RR^{-1} \circ \RR := \set {\tuple {x, y} \in S \times S: \exists z \in S: \tuple {x, z} \in \RR \land \tuple {z, y} \in \RR^{-1} }$

Let $\tuple {x, y} \in S \times S$ be arbitrary.


$\exists z \in \RR: \tuple {x, z} \in \R \land \tuple {y, z} \in \R$

That is:

$\exists z \in \RR: \tuple {x, z} \in \R \land \tuple {z, y} \in \R^{-1}$

That is:

$\tuple {x, y} \in \RR^{-1} \circ \RR$

As $\tuple {x, y}$ is arbitrary, it follows that:

$\RR^{-1} \circ \RR = S \times S$


Necessary Condition

Let $\struct {S, \RR}$ be such that:

$\RR^{-1} \circ \RR = S \times S$

Then by definition of composite relation:

$\RR^{-1} \circ \RR = S \times S = \set {\tuple {x, y} \in S \times S: \exists z \in S: \tuple {x, z} \in \RR \land \tuple {z, y} \in \RR^{-1} }$

That is:

$\forall \tuple {x, y} \in S \times S: \exists z \in S: \tuple {x, z} \in \RR \land \tuple {z, y} \in \RR^{-1}$

That is, by definition of inverse relation:

$\forall \tuple {x, y} \in S \times S: \exists z \in S: \tuple {x, z} \in \RR \land \tuple {y, z} \in \RR$

That is, $\RR$ is a directed ordering.