Equivalence of Definitions of Strict Ordering

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ be a set.

Let $\mathcal R$ be a relation on $S$.

The following definitions of the concept of Strict Ordering are equivalent:


Definition 1

Let $\mathcal R$ be a relation on a set $S$.

Then $\mathcal R$ is a strict ordering (on $S$) if and only if the following two conditions hold:

\((1)\)   $:$   Asymmetry      \(\displaystyle \forall a, b \in S:\)    \(\displaystyle a \mathrel {\mathcal R} b \)   \(\displaystyle \implies \)   \(\displaystyle \neg \paren {b \mathrel {\mathcal R} a} \)             
\((2)\)   $:$   Transitivity      \(\displaystyle \forall a, b, c \in S:\)    \(\displaystyle \paren {a \mathrel {\mathcal R} b} \land \paren {b \mathrel {\mathcal R} c} \)   \(\displaystyle \implies \)   \(\displaystyle a \mathrel {\mathcal R} c \)             

Definition 2

Let $\mathcal R$ be a relation on a set $S$.

Then $\mathcal R$ is a strict ordering (on $S$) if and only if the following two conditions hold:

\((1)\)   $:$   Antireflexivity      \(\displaystyle \forall a \in S:\) \(\displaystyle \neg \paren {a \mathrel {\mathcal R} a} \)             
\((2)\)   $:$   Transitivity      \(\displaystyle \forall a, b, c \in S:\) \(\displaystyle \paren {a \mathrel {\mathcal R} b} \land \paren {b \mathrel {\mathcal R} c} \implies a \mathrel {\mathcal R} c \)             


Proof

Let $\mathcal R$ be transitive.

Then by Transitive Relation is Antireflexive iff Asymmetric it follows directly that:

$(1): \quad$ If $\mathcal R$ is antireflexive then it is asymmetric
$(2): \quad$ If $\mathcal R$ is asymmetric then it is antireflexive.

$\blacksquare$