Definition:Ordering

From ProofWiki

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$

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] 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.

[edit] Weak vs. Strict Orderings

Compare strict ordering.

If it is necessary to emphasise that an ordering $\preceq$ is not strict, then the term weak ordering may be used.

Definition:Ordering

From ProofWiki

[edit] Partial vs. Total Orderings

[edit] Weak vs. Strict Orderings

Views

Personal tools

Navigation

ProofWiki.org

Search

ToDo

Toolbox