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.
Contents
Note
Partial orderings and strict orderings are very similar, and the terms differ slightly for each. For example for [ilmath]a[/ilmath] and [ilmath]b[/ilmath] to be comparable in a partial ordering (for a relation [ilmath]R[/ilmath] in [ilmath]A[/ilmath]) it means that [math]aRb\vee bRa[/math] - an example would be [ilmath]\le[/ilmath]
However! For a strict ordering for [ilmath]a[/ilmath] and [ilmath]b[/ilmath] to be comparable we must have: [math]a\ne b\implies[aRb\vee bRa][/math], for example [ilmath]<[/ilmath]
Required properties
These are restated from the relation page for convenience
Here [ilmath]R[/ilmath] will be a relation in [ilmath]A[/ilmath]
| Property | Statement | Example | Partial | Strict |
|---|---|---|---|---|
| Symmetric | [math]\forall a\in A\forall b\in A(aRb\implies bRa)[/math] | equiv relations | ||
| Antisymmetric | [math]\forall a\in A\forall b\in A([aRb\wedge bRa]\implies a=b)[/math] | Let [ilmath]A=\mathbb{N}[/ilmath] then [math][a\le b\wedge b\le a]\implies a=b[/math] | # | |
| Asymmetric | [math]\forall a\in A\forall b\in B(aRb\implies (b,a)\notin R)[/math] | If [ilmath]a < b[/ilmath] then [ilmath]b < a[/ilmath] is false | # | |
| Reflexive | [math]\forall a\in A(aRa)[/math] | equiv relations, Let [ilmath]A=\mathbb{N}[/ilmath] then [math]a\le a[/math] | # | |
| Transitive | [math]\forall a\in A\forall b\in A\forall c\in A([aRb\wedge bRc]\implies aRc)[/math] | equiv relations, [ilmath]A=\mathbb{N}[/ilmath] then [math]a\le b\wedge b\le c\iff a\le b\le c\implies a\le c[/math] | # | # |
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 [ilmath]\le[/ilmath], notice [ilmath]a\le b[/ilmath] and [math]b\le a\implies a=b[/math]
Strict ordering
A relation [ilmath]S[/ilmath] in [ilmath]A[/ilmath] is a strict ordering if it is asymmetric and transitive.
Comparable elements
We say [ilmath]a[/ilmath] and [ilmath]b[/ilmath] are comparable if the following hold:
Partial ordering
For [ilmath]a[/ilmath] and [ilmath]b[/ilmath] to be comparable we must have [math]aRb\vee bRa[/math]
Strict ordering
For [ilmath]a[/ilmath] and [ilmath]b[/ilmath] to be comparable we require [math]a\ne b\implies[aRb\vee bRa][/math], notice that false implies false
Total ordering (Linear ordering)
A (partial or strict) ordering is a total (also known as linear) ordering if [math]\forall a\in A\forall b\in B[/math], [ilmath]a[/ilmath] and [ilmath]b[/ilmath] are comparable using the definitions above.
For example the ordering [math]a|b[/math] meaning [ilmath]a[/ilmath] divides [ilmath]b[/ilmath] (example: [math](3,6)\iff 3|6[/math]) is not total, however [math]\le[/math] is, as is [math] >[/math]
