View source for Ordering

{{Refactor notice}}
For partial orderings see [[partial ordering]], the only useful thing on this page not on that page is the theorem at the bottom:
[[Ordering#Proof_that_.5Bmath.5D.5Cle.5B.2Fmath.5D_is_a_partial_ordering_.5Bmath.5D.5Ciff_.3C.5B.2Fmath.5D_is_a_strict_ordering|Proof that <math>\le</math> is a partial ordering <math>\iff <</math> is a strict ordering]]
<hr/>

An ordering is a special kind of [[Relation|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:
{| class="wikitable" border="1"
|-
! 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 {{M|S}} in {{M|A}} is a strict ordering if it is asymmetric and transitive. Example <math>< </math>
===Reminder of terms===
These are restated from the [[Relation|relation]] page for convenience 

Here {{M|R}} will be a relation in {{M|A}}
{| class="wikitable" border="1"
|-
! Property
! Statement
! Example
! Partial
! Strict
|-
| Symmetric
| <math>\forall a\in A\forall b\in A(aRb\implies bRa)</math>
| [[Equivalence relation|equiv relations]]
|
|
|-
| Antisymmetric
| <math>\forall a\in A\forall b\in A([aRb\wedge bRa]\implies a=b)</math>
| Let {{M|1=A=\mathbb{N} }} 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 {{M|a < b}} then {{M|b < a}} is false
|
| #
|-
| Reflexive
| <math>\forall a\in A(aRa)</math>
| [[Equivalence relation|equiv relations]], Let {{M|1=A=\mathbb{N} }} 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>
| [[Equivalence relation|equiv relations]], {{M|1=A=\mathbb{N} }} 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 {{M|a}} and {{M|b}} are comparable if the following hold:
===Partial ordering===
For {{M|a}} and {{M|b}} to be comparable we must have <math>aRb\vee bRa</math>

===Strict ordering===
For {{M|a}} and {{M|b}} to be comparable we require <math>a\ne b\implies[aRb\vee bRa]</math>, notice that false [[Implies|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>, {{M|a}} and {{M|b}} are comparable using the definitions above. 

For example the ordering <math>a|b</math> meaning {{M|a}} divides {{M|b}} (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 {{M|B\subset A}}
{| class="wikitable" border="1"
|-
! Property
! Statement
|-
|}

==Proof that <math>\le</math> is a partial ordering <math>\iff <</math> is a strict ordering==
{{Begin Theorem}}
Proof that <math>\le</math> is a partial ordering <math>\iff <</math> is a strict ordering
{{Begin Proof}}
'''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.
#:
#:
# '''<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 {{M|y}} are different
#: 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}}
{{End Proof}}
{{End Theorem}}

==Good resources==
* [http://www.math.uah.edu/stat/foundations/Order.html http://www.math.uah.edu/stat/foundations/Order.html]

{{Definition|Set Theory}}