Definition:Ordering

From ProofWiki

[edit] Definition

Let $S$ be a set.

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

$\mathcal R$ is reflexive, that is, $\forall a \in S: a \mathcal R a$
$\mathcal R$ is transitive, that is, $\forall a, b, c \in S: a \mathcal R b \and b \mathcal R c \implies a \mathcal R c$
$\mathcal R$ is antisymmetric, that is, $\forall a, b \in S: a \mathcal R b \and b \mathcal R a \implies a = b$

It can be called an order relation or an order (although that last term is also used for several other concepts so bears the risk of ambiguity).

Symbols frequently used to define such a general ordering relation are variants on $\preceq$ or $\le$ , although the latter is usually used in the context of numbers.

" $a \preceq b$ " can be read as: " $a$ precedes, or is the same as, $b$ ".

Alternatively, " $a \preceq b$ " can be read as: " $b$ succeeds, or is the same as, $a$ ".

A symbol for an ordering can be reversed, and the sense is likewise inverted:

$a \preceq b \iff b \succeq a$

If, for two elements $a, b \in S$ , $\neg a \preceq b$ , then the symbols $a \not \preceq b$ and $b \not \succeq a$ can be used.

[edit] Smaller and Larger

An ordering is often considered to be a comparison of the "size" of objects, in some perhaps intuitive sense. Depending on the nature of the sets being ordered, and depending on the nature of the ordering relation, this aspect may or may not be intellectually sustainable.

Be that as it may, one frequently encounters terminology such as:

$A$ is smaller than $B$ to mean $A \preceq B$ ;
$A$ is larger than $B$ to mean $B \preceq A$ .

[edit] Partial vs. Total Orderings

Note that this definition of "ordering" does not demand that every pair of elements of $S$ is related by $\preceq$ . The way we have defined an ordering, they may be, or they may not be, depending on the context.

If it is the case that $\preceq$ is a connected relation, i.e. that every pair of elements is related by $\preceq$ , then $\preceq$ is called a total ordering.

If it is not the case that $\preceq$ is connected, then $\preceq$ is called a partial ordering.