Ordering
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 [math]\le[/math] is a partial ordering [math]\iff <[/math] 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.
Contents
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) | [math]\le[/math] | [math]<[/math] |
(Other ordering symbol) | [math]\preceq[/math] | [math]\prec[/math] |
proper subset (or equal to) | [math]\subseteq[/math] | [math]\subset[/math] |
Partial Ordering
A binary relation that is antisymmetric, reflexive and transitive is a partial ordering. Example [math]\le[/math]
Strict ordering
A relation [ilmath]S[/ilmath] in [ilmath]A[/ilmath] is a strict ordering if it is asymmetric and transitive. Example [math]< [/math]
Reminder of terms
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] | # | # |
Moving between partial and strict relations
Given a partial relation [math]\le[/math] we may define a strict relation [math]<[/math] by:
[math]a< b\iff[a\le b\wedge a\ne b][/math]
If given a [math]<[/math] we can define a [math]\le[/math] by:
[math]a\le b\iff[a< b\vee a=b][/math]
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]
Properties
Given a partial ordering [math]\le[/math] of [math]A[/math] and let [ilmath]B\subset A[/ilmath]
Property | Statement |
---|
Proof that [math]\le[/math] is a partial ordering [math]\iff <[/math] is a strict ordering
Proof that [math]\le[/math] is a partial ordering [math]\iff <[/math] is a strict ordering
First: [math]\le[/math] is partial [math]\implies <[/math] is strict
- [math]<[/math] is transitive
- Suppose [math]x< y[/math] and [math]y < z[/math] (which may be written more compactly as [math]x< y< z[/math]) then:
- [math]x\le y\wedge x\ne y[/math]
- [math]y\le z\wedge y\ne z[/math]
- As [math]x\le y[/math] and [math]y\le z[/math] by transitivity of [math]\le[/math] we see [math]x\le z[/math]
- However all we know is [math]x\ne y\wedge y\ne z[/math] so we cannot yet conclude [math]x=z[/math] or [math]x\ne z[/math]
- Suppose [math]x=z[/math] we already know [math][x\le y]\wedge [y\le z][/math] but [math]z=x[/math]
- thus [math][x\le y]\wedge[y \le x][/math] but [math]\iff y=x[/math] contradicting that [math]y\ne x[/math]
- Now we know [math]x\ne z[/math]
- Noting that [math][x< y\wedge y< z]\implies [x\le z\wedge x\ne z]\implies x< z[/math]. We conclude [math]<[/math] is transitive.
- Suppose [math]x< y[/math] and [math]y < z[/math] (which may be written more compactly as [math]x< y< z[/math]) then:
- [math]<[/math] is asymmetric (we have [math]a< b\implies b\not< a[/math])
- If [math]x< y[/math] then we know [math]x\le y\wedge x\ne y[/math]
- So we must have [math]y\not\le x[/math] as if:
- [math]y\le x[/math] were true then we'd have [math][x\le y\wedge y\le x]\implies x=y[/math]
- contradicting that [math]x[/math] and [ilmath]y[/ilmath] are different
- [math]y\le x[/math] were true then we'd have [math][x\le y\wedge y\le x]\implies x=y[/math]
- But [math]y< x\iff[y\le x\wedge x\ne y][/math] - we do not have [math]y\le x[/math] so we cannot have [math]y< x[/math]
- Thus we see that [math]x< y\implies x\not< y[/math] - we conclude that [math]<[/math] is asymmetric
Second: [math]<[/math] is strict [math]\implies \le[/math] is partial
TODO: Fill this out