Ordering

An ordering is a special kind of relation, other than the concept of a relation we require three properties before we can define it.

Note

Partial orderings and strict orderings are very similar, and the terms differ slightly for each. For example for $a$ and $b$ to be comparable in a partial ordering (for a relation $R$ in $A$) it means that

$$aRb\vee bRa$$ - an example would be $\le$

However! For a strict ordering for $a$ and $b$ to be comparable we must have:

$$a\ne b\implies[aRb\vee bRa]$$ , for example $<$

Required properties

These are restated from the relation page for convenience

Here $R$ will be a relation in $A$

Property	Statement	Example	Partial	Strict
Symmetric	$$\forall a\in A\forall b\in A(aRb\implies bRa)$$	equiv relations
Antisymmetric	$$\forall a\in A\forall b\in A([aRb\wedge bRa]\implies a=b)$$	Let $A=\mathbb{N}$ then $$[a\le b\wedge b\le a]\implies a=b$$	#
Asymmetric	$$\forall a\in A\forall b\in B(aRb\implies (b,a)\notin R)$$	If $a < b$ then $b < a$ is false		#
Reflexive	$$\forall a\in A(aRa)$$	equiv relations, Let $A=\mathbb{N}$ then $$a\le a$$	#
Transitive	$$\forall a\in A\forall b\in A\forall c\in A([aRb\wedge bRc]\implies aRc)$$	equiv relations, $A=\mathbb{N}$ then $$a\le b\wedge b\le c\iff a\le b\le c\implies a\le c$$	#	#

Definition

If we have "just an ordering" it refers to a partial ordering.

Partial Ordering

A binary relation that is antisymmetric, reflexive and transitive is a partial ordering. An example of a partial ordering is $\le$, notice $a\le b$ and

$$b\le a\implies a=b$$

Strict ordering

A relation $S$ in $A$ is a strict ordering if it is asymmetric and transitive.

Comparable elements

We say $a$ and $b$ are comparable if the following hold:

Partial ordering

For $a$ and $b$ to be comparable we must have

$$aRb\vee bRa$$

Strict ordering

For $a$ and $b$ to be comparable we require

$$a\ne b\implies[aRb\vee bRa]$$ , notice that false implies false

Total ordering (Linear ordering)

A (partial or strict) ordering is a total (also known as linear) ordering if

$$\forall a\in A\forall b\in B$$ , $a$ and $b$ are comparable using the definitions above.

For example the ordering

$$a|b$$ meaning $a$ divides $b$ (example: $$(3,6)\iff 3|6$$ ) is not total, however $$\le$$ is, as is $$>$$