Category:Orderings

From ProofWiki
Jump to navigation Jump to search

This category contains results about Orderings.
Definitions specific to this category can be found in Definitions/Orderings.


Let $S$ be a set.

Definition 1

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

\((1)\)   $:$   $\RR$ is reflexive      \(\ds \forall a \in S:\) \(\ds a \mathrel \RR a \)             
\((2)\)   $:$   $\RR$ is transitive      \(\ds \forall a, b, c \in S:\) \(\ds a \mathrel \RR b \land b \mathrel \RR c \implies a \mathrel \RR c \)             
\((3)\)   $:$   $\RR$ is antisymmetric      \(\ds \forall a \in S:\) \(\ds a \mathrel \RR b \land b \mathrel \RR a \implies a = b \)             


Definition 2

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

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

where:

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