# Definition:Ordering

Work In ProgressThe terminlogy around the subject of orderings is sufficiently complicated and ambiguous to justify a page containing transcluded definitions of all the various types of ordering, so as to have them all gathered conveniently into one place for direct comparison and individual interpretation (like what is done with the separation axioms).You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by completing it.To discuss this page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{WIP}}` from the code. |

## Definition

Let $S$ be a set.

### Definition 1

An **ordering on $S$** is a relation $\RR$ on $S$ such that:

\((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 \in S:\) | \(\ds a \mathrel \RR b \land b \mathrel \RR a \implies a = b \) |

### Definition 2

An **ordering on $S$** is a relation $\RR$ on $S$ such that:

- $(1): \quad \RR \circ \RR = \RR$
- $(2): \quad \RR \cap \RR^{-1} = \Delta_S$

where:

- $\circ$ denotes relation composition
- $\RR^{-1}$ denotes the inverse of $\RR$
- $\Delta_S$ denotes the diagonal relation on $S$.

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

- $a \preceq b$

can be read as:

**$a$ precedes, or is the same as, $b$**.

Similarly:

- $a \preceq b$

can be read as:

**$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.

### Notation for Dual Ordering

To denote the dual of an ordering, the conventional technique is to reverse the symbol.

Thus:

- $\succeq$ denotes $\preceq^{-1}$
- $\succcurlyeq$ denotes $\preccurlyeq^{-1}$
- $\curlyeqsucc$ denotes $\curlyeqprec^{-1}$

and so:

- $a \preceq b \iff b \succeq a$
- $a \preccurlyeq b \iff b \succcurlyeq a$
- $a \curlyeqprec b \iff b \curlyeqsucc a$

Similarly for the standard symbols used to denote an ordering on numbers:

- $\ge$ denotes $\le^{-1}$
- $\geqslant$ denotes $\leqslant^{-1}$
- $\eqslantgtr$ denotes $\eqslantless^{-1}$

and so on.

## Smaller and Larger

An ordering can often be considered to be a comparison of the **size** of objects, perhaps in some intuitive sense.

This is particularly applicable in the context of numbers.

Thus the expression $A \preceq B$ can in such contexts be interpreted as:

**$A$ is smaller than $B$****$A$ is less than $B$**

and $B \preceq A$ can similarly be interpreted as:

**$A$ is larger than $B$****$A$ is greater than $B$**

In natural language, such terms are called **comparative adjectives**, or just **comparatives**.

Depending on the nature of the set being ordered, and depending on the nature of the ordering relation, this interpretation of an ordering as a comparison of size may not be intellectually sustainable.

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

## Strict vs. Weak Ordering

Some sources define an **ordering** as we on $\mathsf{Pr} \infty \mathsf{fWiki}$ define a **strict ordering**.

Hence, in contrast with such a **strict ordering**, the term **weak ordering** is often used in this context to mean what we define on $\mathsf{Pr} \infty \mathsf{fWiki}$ as an **ordering**.

It is essential to be aware of the precise definitions used by whatever text is being studied so as not to fall into confusion.

## Also known as

An **ordering** is also referred to as an **order relation** or an **order**, although the latter term is also used for several other concepts so bears the risk of ambiguity.

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.

An **ordering** as defined here is sometimes referred to as a **weak ordering** if it is necessary to place emphasis on the fact that it is not a strict ordering.

## Also defined as

1955: John L. Kelley: *General Topology* defines an **ordering** as a transitive relation.

He also allows the synonyms **partial ordering** (which this is), and **quasi-ordering** (which is generally used as a synonym for preordering).

This approach glosses over the antisymmetric nature of an ordering, and in fact what is ended up with appears to be what on $\mathsf{Pr} \infty \mathsf{fWiki}$ is defined as a strict ordering.

This approach is not used on $\mathsf{Pr} \infty \mathsf{fWiki}$.

## Examples

### Integer Difference on Reals

Let $\preccurlyeq$ denote the relation on the set of real numbers $\R$ defined as:

- $a \preccurlyeq b$ if and only if $b - a$ is a non-negative integer

Then $\preccurlyeq$ is an ordering on $\R$.

### Example Ordering on Integers

Let $\preccurlyeq$ denote the relation on the set of integers $\Z$ defined as:

- $a \preccurlyeq b$ if and only if $0 \le a \le b \text { or } b \le a < 0 \text { or } a < 0 \le b$

where $\le$ is the usual ordering on $\Z$.

Then $\preccurlyeq$ is an ordering on $\Z$.

## Also see

- Definition:Ordered Set
- Definition:Partially Ordered Set
- Definition:Totally Ordered Set
- Definition:Well-Ordered Set

- Results about
**orderings**can be found here.

## Sources

- 1955: John L. Kelley:
*General Topology*... (previous) ... (next): Chapter $0$: Orderings - 1982: Peter T. Johnstone:
*Stone Spaces*... (next): Chapter $\text I$: Preliminaries, Definition $1.1$