Definition:Ordering
Contents |
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 \land b \mathcal R c \implies a \mathcal R c$
- $\mathcal R$ is antisymmetric, that is, $\forall a, b \in S: a \mathcal R b \land 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.
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$.
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.
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.
Also see
Sources
- Nathan Jacobson: Lectures in Abstract Algebra: I. Basic Concepts (1951): Introduction $\S 4$
- Paul R. Halmos: Naive Set Theory (1960)... (previous)... (next): $\S 14$: Order
- W.E. Deskins: Abstract Algebra (1964): $\S 1.2$: Definition $1.7 \ \text{(b)}$
- Seth Warner: Modern Algebra (1965): $\S 14$
- A.N. Kolmogorov and S.V. Fomin‎: Introductory Real Analysis (1968): $\S 3.1$
- T.S. Blyth: Set Theory and Abstract Algebra (1975): $\S 6, \ \S 7$
- Keith Devlin: The Joy of Sets: Fundamentals of Contemporary Set Theory (1993): $\S 1.5$
