Ordering

(Unknown grade)

This page is currently being refactored (along with many others)

Please note that this does not mean the content is unreliable. It just means the page doesn't conform to the style of the site (usually due to age) or a better way of presenting the information has been discovered.

For partial orderings see partial ordering, the only useful thing on this page not on that page is the theorem at the bottom: Proof that $$\le$$ is a partial ordering $$\iff <$$ is a strict ordering

---

An ordering is a special kind of relation, we can define an order uniquely as a partial or strict ordering. That is the two are equivalent.

Definition

So far it varies so much as to what "Ordering" means that based on the context it could be either partial or strict. The big clue will be the symbols used:

Relation	Partial form	Strict form
Less than (or equal to)	$$\le$$	$$<$$
(Other ordering symbol)	$$\preceq$$	$$\prec$$
proper subset (or equal to)	$$\subseteq$$	$$\subset$$

Partial Ordering

A binary relation that is antisymmetric, reflexive and transitive is a partial ordering. Example $$\le$$

Strict ordering

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

Reminder of terms

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

Moving between partial and strict relations

Given a partial relation $$\le$$ we may define a strict relation $$<$$ by:

$$a< b\iff[a\le b\wedge a\ne b]$$

If given a $$<$$ we can define a $$\le$$ by:

$$a\le b\iff[a< b\vee a=b]$$

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

Properties

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

Property	Statement

Proof that $$\le$$ is a partial ordering $$\iff <$$ is a strict ordering

[Expand]

Proof that $$\le$$ is a partial ordering $$\iff <$$ is a strict ordering

---

First: $$\le$$ is partial $$\implies <$$ is strict

1. $$<$$ is transitive

   Suppose $$x< y$$ and $$y < z$$ (which may be written more compactly as $$x< y< z$$ ) then:

   • $$x\le y\wedge x\ne y$$
   • $$y\le z\wedge y\ne z$$

   As $$x\le y$$ and $$y\le z$$ by transitivity of $$\le$$ we see $$x\le z$$

   However all we know is $$x\ne y\wedge y\ne z$$ so we cannot yet conclude $$x=z$$ or $$x\ne z$$

   Suppose $$x=z$$ we already know $$[x\le y]\wedge [y\le z]$$ but $$z=x$$

   thus $$[x\le y]\wedge[y \le x]$$ but $$\iff y=x$$ contradicting that $$y\ne x$$

   Now we know $$x\ne z$$

   Noting that $$[x< y\wedge y< z]\implies [x\le z\wedge x\ne z]\implies x< z$$ . We conclude $$<$$ is transitive.

2. $$<$$ is asymmetric (we have $$a< b\implies b\not< a$$ )

   If $$x< y$$ then we know $$x\le y\wedge x\ne y$$

   So we must have $$y\not\le x$$ as if:

   • $$y\le x$$ were true then we'd have $$[x\le y\wedge y\le x]\implies x=y$$

     contradicting that $$x$$ and $y$ are different

   But $$y< x\iff[y\le x\wedge x\ne y]$$ - we do not have $$y\le x$$ so we cannot have $$y< x$$

   Thus we see that $$x< y\implies x\not< y$$ - we conclude that $$<$$ is asymmetric

Second: $$<$$ is strict $$\implies \le$$ is partial

---

TODO: Fill this out

---

Good resources

• http://www.math.uah.edu/stat/foundations/Order.html