Definition:Ordering/Definition 1
Definition
Let $S$ be a set.
Let $\RR$ be a relation $\RR$ on $S$.
$\RR$ is an ordering on $S$ if and only if $\RR$ satisfies the ordering axioms:
\((1)\) | $:$ | $\RR$ is reflexive | \(\ds \forall a \in S:\) | \(\ds a \mathrel \RR a \) | |||||
\((2)\) | $:$ | $\RR$ is transitive | \(\ds \forall a, b, c \in S:\) | \(\ds a \mathrel \RR b \land b \mathrel \RR c \implies a \mathrel \RR c \) | |||||
\((3)\) | $:$ | $\RR$ is antisymmetric | \(\ds \forall a, b \in S:\) | \(\ds a \mathrel \RR b \land b \mathrel \RR a \implies a = b \) |
Notation
Symbols used to denote a general ordering relation are usually variants on $\preceq$, $\le$ and so on.
On $\mathsf{Pr} \infty \mathsf{fWiki}$, to denote a general ordering relation it is recommended to use $\preceq$ and its variants:
- $\preccurlyeq$
- $\curlyeqprec$
To denote the conventional ordering relation in the context of numbers, the symbol $\le$ is to be used, or its variants:
- $\leqslant$
- $\leqq$
- $\eqslantless$
The symbol $\subseteq$ is universally reserved for the subset relation.
\(\ds a\) | \(\preceq\) | \(\ds b\) | can be read as: | \(\quad\) $a$ precedes, or is the same as, $b$ | ||||||||||
\(\ds a\) | \(\preceq\) | \(\ds b\) | can be read as: | \(\quad\) $b$ succeeds, or is the same as, $a$ |
If, for two elements $a, b \in S$, it is not the case that $a \preceq b$, then the symbols $a \npreceq b$ and $b \nsucceq a$ can be used.
When the symbols $\le$ and its variants are used, it is common to interpret them as follows:
\(\ds a\) | \(\le\) | \(\ds b\) | can be read as: | \(\quad\) $a$ is less than, or is the same as, $b$ | ||||||||||
\(\ds a\) | \(\le\) | \(\ds b\) | can be read as: | \(\quad\) $b$ is greater than, or is the same as, $a$ |
Partial vs. Total Ordering
It is not demanded of an ordering $\preceq$, defined in its most general form on a set $S$, that every pair of elements of $S$ is related by $\preceq$.
They may be, or they may not be, depending on the specific nature of both $S$ and $\preceq$.
If it is the case that $\preceq$ is a connected relation, that is, that every pair of distinct 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.
Beware that some sources use the word partial for an ordering which may or may not be connected, while others insist on reserving the word partial for one which is specifically not connected.
It is wise to be certain of what is meant.
As a consequence, on $\mathsf{Pr} \infty \mathsf{fWiki}$ we resolve any ambiguity by reserving the terms for the objects in question as follows:
- Partial ordering: an ordering which is specifically not total
- Total ordering: an ordering which is specifically not partial.
Also see
- Results about orderings can be found here.
Sources
- 1960: Paul R. Halmos: Naive Set Theory ... (previous) ... (next): $\S 14$: Order
- 1964: W.E. Deskins: Abstract Algebra ... (previous) ... (next): $\S 1.2$: Definition $1.7 \ \text {(b)}$
- 1965: Seth Warner: Modern Algebra ... (previous) ... (next): Chapter $\text {III}$: The Natural Numbers: $\S 14$: Orderings
- 1968: A.N. Kolmogorov and S.V. Fomin: Introductory Real Analysis ... (previous) ... (next): $\S 3.1$: Partially ordered sets
- 1968: Ian D. Macdonald: The Theory of Groups ... (previous) ... (next): Appendix: Elementary set and number theory
- 1972: A.G. Howson: A Handbook of Terms used in Algebra and Analysis ... (previous) ... (next): $\S 3$: Equivalence relations and quotient sets: Binary relations
- 1975: T.S. Blyth: Set Theory and Abstract Algebra ... (previous) ... (next): $\S 6$. Indexed families; partitions; equivalence relations
- 1975: T.S. Blyth: Set Theory and Abstract Algebra ... (previous) ... (next): $\S 7$
- 1982: P.M. Cohn: Algebra Volume 1 (2nd ed.) ... (previous) ... (next): Chapter $1$: Sets and mappings: $\S 1.5$: Ordered Sets
- 1993: Keith Devlin: The Joy of Sets: Fundamentals of Contemporary Set Theory (2nd ed.) ... (previous) ... (next): $\S 1$: Naive Set Theory: $\S 1.5$: Relations
- 1996: Winfried Just and Martin Weese: Discovering Modern Set Theory. I: The Basics ... (previous) ... (next): Part $1$: Not Entirely Naive Set Theory: Chapter $2$: Partial Order Relations
- 2002: B.A. Davey and H.A. Priestley: Introduction to Lattices and Order (2nd ed.): $\S 1$. Ordered sets: $\S 1.2$. Definitions
- 2008: Paul Halmos and Steven Givant: Introduction to Boolean Algebras ... (previous) ... (next): Appendix $\text{A}$: Set Theory: Order