# Definition:Ordering

## Definition

Let $S$ be a set.

### Definition 1

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

\((1)\) | $:$ | $\RR$ is reflexive | \(\displaystyle \forall a \in S:\) | \(\displaystyle a \mathrel \RR a \) | ||||

\((2)\) | $:$ | $\RR$ is transitive | \(\displaystyle \forall a, b, c \in S:\) | \(\displaystyle a \mathrel \RR b \land b \mathrel \RR c \implies a \mathrel \RR c \) | ||||

\((3)\) | $:$ | $\RR$ is antisymmetric | \(\displaystyle \forall a \in S:\) | \(\displaystyle 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$