Definition:Ordering

From ProofWiki

Jump to: navigation, search

Let S be a set.

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


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.

Personal tools