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

It can be shown that if $$<$$ is (strict and linear ordering) then $$\le$$ defined by $$p\le q\iff[p< q\vee p=q]$$ is a partial ordering. So you can switch from a strict to a partial quite easily.

One can also use common sense, and notice that $$\not <\iff\ge$$

It can be shown that a partial ordering has a natural corresponding strict ordering and a strict ordering has a natural corresponding partial ordering.

---

TODO: corresponding orderings

---

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.

Well ordering

(see Well-ordering)

Properties

Given a partial ordering $$\le$$ of $$A$$ and let $B\subset A$

Property	Statement

Required properties for definition

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

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