Equivalence of Definitions of Ordering

From ProofWiki
Jump to navigation Jump to search

Theorem

The following definitions of the concept of Ordering are equivalent:

Definition 1

An ordering on $S$ is a relation $\mathcal R$ on $S$ such that:

\((1)\)   $:$   $\mathcal R$ is reflexive      \(\displaystyle \forall a \in S:\) \(\displaystyle a \mathop {\mathcal R} a \)             
\((2)\)   $:$   $\mathcal R$ is transitive      \(\displaystyle \forall a, b, c \in S:\) \(\displaystyle a \mathop {\mathcal R} b \land b \mathop {\mathcal R} c \implies a \mathop {\mathcal R} c \)             
\((3)\)   $:$   $\mathcal R$ is antisymmetric      \(\displaystyle \forall a \in S:\) \(\displaystyle a \mathop {\mathcal R} b \land b \mathop {\mathcal R} a \implies a = b \)             

Definition 2

An ordering on $S$ is a relation $\mathcal R$ on $S$ such that:

$(1): \quad \mathcal R \circ \mathcal R = \mathcal R$
$(2): \quad \mathcal R \cap \mathcal R^{-1} = \Delta_S$

where:

$\circ$ denotes relation composition
$\mathcal R^{-1}$ denotes the inverse of $\mathcal R$
$\Delta_S$ denotes the diagonal relation on $S$.


Proof 1

Definition 1 implies Definition 2

Let $\mathcal R$ be a relation on $S$ satisfying:

\((1)\)   $:$   $\mathcal R$ is reflexive      \(\displaystyle \forall a \in S:\) \(\displaystyle a \mathop {\mathcal R} a \)             
\((2)\)   $:$   $\mathcal R$ is transitive      \(\displaystyle \forall a, b, c \in S:\) \(\displaystyle a \mathop {\mathcal R} b \land b \mathop {\mathcal R} c \implies a \mathop {\mathcal R} c \)             
\((3)\)   $:$   $\mathcal R$ is antisymmetric      \(\displaystyle \forall a \in S:\) \(\displaystyle a \mathop {\mathcal R} b \land b \mathop {\mathcal R} a \implies a = b \)             


By Reflexive and Transitive Relation is Idempotent:

$\mathcal R \circ \mathcal R = \mathcal R$


By Relation is Antisymmetric and Reflexive iff Intersection with Inverse equals Diagonal Relation:

$\mathcal R \cap \mathcal R^{-1} = \Delta_S$


Thus $\mathcal R$ is an ordering by definition 2.

$\Box$


Definition 2 implies Definition 1

Let $\mathcal R$ be a relation which fulfils the conditions:

$(1): \quad \mathcal R \circ \mathcal R = \mathcal R$
$(2): \quad \mathcal R \cap \mathcal R^{-1} = \Delta_S$


By definition of set equality, it follows from $(1)$:

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

Thus, by definition, $\mathcal R$ is transitive.


By Relation is Antisymmetric and Reflexive iff Intersection with Inverse equals Diagonal Relation, it follows from $(2)$ that:

$\mathcal R$ is reflexive
$\mathcal R$ is antisymmetric.


Thus $\mathcal R$ is an ordering by definition 1.

$\blacksquare$


Proof 2

Definition 1 implies Definition 2

Let $\mathcal R$ be a relation on $S$ satisfying:

\((1)\)   $:$   $\mathcal R$ is reflexive      \(\displaystyle \forall a \in S:\) \(\displaystyle a \mathop {\mathcal R} a \)             
\((2)\)   $:$   $\mathcal R$ is transitive      \(\displaystyle \forall a, b, c \in S:\) \(\displaystyle a \mathop {\mathcal R} b \land b \mathop {\mathcal R} c \implies a \mathop {\mathcal R} c \)             
\((3)\)   $:$   $\mathcal R$ is antisymmetric      \(\displaystyle \forall a \in S:\) \(\displaystyle a \mathop {\mathcal R} b \land b \mathop {\mathcal R} a \implies a = b \)             


Condition $(1)$

Let $\left({x, y}\right) \in \mathcal R \circ \mathcal R$.

Then there exists a $z \in \mathcal R$ such that:

$\left({x, z}\right), \left({z, y}\right) \in \mathcal R$

By $\mathcal R$ being transitive:

$\left({x, y}\right) \in \mathcal R$

Hence:

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


Now let $\left({x, y}\right) \in \mathcal R$.

By $\mathcal R$ being reflexive:

$\left({y, y}\right) \in \mathcal R$

Hence by the definition of relation composition:

$\left({x, y}\right) \in \mathcal R \circ \mathcal R$

Hence:

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


Condition $(2)$

Follows immediately from Relation is Antisymmetric iff Intersection with Inverse is Coreflexive and $\mathcal R$ being reflexive.


Thus $\mathcal R$ is an ordering by definition 2.

$\Box$


Definition 2 implies Definition 1

Let $\mathcal R$ be a relation which fulfils the conditions:

$(1): \quad \mathcal R \circ \mathcal R = \mathcal R$
$(2): \quad \mathcal R \cap \mathcal R^{-1} = \Delta_S$


Reflexivity

By Intersection is Subset the condition:

$\mathcal R \cap \mathcal R^{-1} = \Delta_S$

implies:

$\Delta_S \subseteq \mathcal R$

Thus $\mathcal R$ is reflexive by definition


Antisymmetry

By Relation is Antisymmetric iff Intersection with Inverse is Coreflexive the condition:

$\mathcal R \cap \mathcal R^{-1} = \Delta_S$

implies that $\mathcal R$ is antisymmetric


Transitivity

Let $\left({x, y}\right), \left({y, z}\right) \in \mathcal R$.

Then by the definition of relation composition:

$\left({x, z}\right) \in \mathcal R \circ \mathcal R$

But by the condition:

$\mathcal R \circ \mathcal R = \mathcal R$

It follows that:

$\left({x, z}\right) \in \mathcal R$

Hence $\mathcal R$ is transitive.


Thus $\mathcal R$ is an ordering by definition 1.

$\blacksquare$