Definition:Ordering

From ProofWiki

Jump to: navigation, search

Contents

[edit] Definition

Let S be a set.

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

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.


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


[edit] Also see



[edit] Sources

Personal tools