Difference between revisions of "Ordering"

From Maths
Jump to: navigation, search
(Created page with "An ordering is a special kind of relation, other than the concept of a relation we require three properties before we can define it. ==Required properties== Thes...")
 
m
 
(4 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:
 +
[[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/>
  
−
==Required properties==
+
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.
−
These are restated from the [[Relation|relation]] page for convenience
+
−
===Symmetric===
+
−
''Note:'' this isn't actually needed, it is stated to allow the reader to contrast with antisymmetric and asymmetric
+
  
−
A relation {{M|R}} in {{M|A}} is symmetric if for all {{M|a,b\in A}} we have that {{M|aRb\implies bRa}} - a property of [[Equivalence relation|equivalence relations]]
 
−
===Antisymmetric===
 
−
A binary relation {{M|R}} in {{M|A}} is antisymmetric if for all {{M|a,b\in A}} we have <math>aRb\text{ and }bRA\implies a=b</math><br/>
 
−
Symmetric implies elements are related to each other, antisymmetric implies only the same things are related to each other.
 
−
===Reflexive===
 
−
For a relation {{M|R}} and for all {{M|a\in A}} we have {{M|aRa}} - {{M|a}} is related to itself.
 
−
===Transitive===
 
−
A relation {{M|R}} in {{M|A}} is transitive if for all {{M|a,b,c\in A}} we have <math>[aRb\text{ and }bRc\implies aRc]</math>
 
−
===Asymmetric===
 
−
A relation {{M|S}} in {{M|A}} is asymmetric if {{M|aSb\implies(b,a)\notin S}}, for example {{M|<}} has this property, we can have {{M|a<b}} or {{M|b<a}} but not both.
 
 
==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:
 +
{| 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===
 
===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>
+
A binary relation that is antisymmetric, reflexive and transitive is a partial ordering. Example <math>\le</math>
 
===Strict ordering===
 
===Strict ordering===
−
A relation {{M|S}} in {{M|A}} is a strict ordering if it is asymmetric and transitive.
+
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}}
 
{{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 "https://www.maths.kisogo.com/index.php?title=Ordering&oldid=1489"