Difference between revisions of "Ordering"

From Maths
Jump to: navigation, search
m
m
 
(2 intermediate revisions by the same user not shown)
Line 1: Line 1:
−
An ordering is a special kind of [[Relation|relation]], other than the concept of a relation we require three properties before we can define it.
+
{{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:
−
==Note==
+
[[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]]
−
Partial orderings and strict orderings are very similar, and the terms differ slightly for each. For example for {{M|a}} and {{M|b}} to be '''comparable''' in a partial ordering (for a relation {{M|R}} in {{M|A}}) it means that <math>aRb\vee bRa</math> - an example would be {{M|\le}}
+
<hr/>
−
 
+
−
However! For a strict ordering for {{M|a}} and {{M|b}} to be comparable we must have: <math>a\ne b\implies[aRb\vee bRa]</math>, for example {{M|<}}
+
−
 
+
−
 
+
−
It can be shown that if <math><</math> is (strict and linear ordering) then <math>\le</math> defined by <math>p\le q\iff[p< q\vee p=q]</math> 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 <math>\not <\iff\ge</math>
+
−
 
+
−
 
+
−
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}}
+
  
 +
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==
 
==Definition==
−
If we have "just an ordering" it refers to a partial ordering.
+
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:
−
 
+
−
===Partial Ordering===
+
−
A binary relation that is antisymmetric, reflexive and transitive is a partial ordering. An example of a partial ordering is {{M|\le}}, notice {{M|a\le b}} and <math>b\le a\implies a=b</math>
+
−
===Strict ordering===
+
−
A relation {{M|S}} in {{M|A}} is a strict ordering if it is asymmetric and transitive.
+
−
 
+
−
===Well ordering===
+
−
(see [[Well-ordering]])
+
−
 
+
−
 
+
−
==Properties==
+
−
Given a partial ordering <math>\le</math> of <math>A</math> and let {{M|B\subset A}}
+
 
{| class="wikitable" border="1"
 
{| class="wikitable" border="1"
 
|-
 
|-
−
! Property
+
! Relation
−
! Statement
+
! 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>
 
|}
 
|}
  
−
==Required properties for definition==
+
===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  
 
These are restated from the [[Relation|relation]] page for convenience  
  
Line 80: Line 73:
 
| #
 
| #
 
|}
 
|}
 +
 +
==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==
 
==Comparable elements==
Line 93: Line 95:
  
 
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>
 
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}}
 
{{Definition|Set Theory}}

Latest revision as of 13:21, 1 January 2016

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 [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.

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

  1. [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.
  2. [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
    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


Good resources

Retrieved from "http://wiki.unifiedmathematics.com/index.php?title=Ordering&oldid=1489"