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
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.
 
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.
 +
 +
==Note==
 +
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}}
 +
 +
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|<}}
  
 
==Required properties==
 
==Required properties==
 
These are restated from the [[Relation|relation]] page for convenience  
 
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]]
+
Here {{M|R}} will be a relation in {{M|A}}
−
===Antisymmetric===
+
{| class="wikitable" border="1"
−
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.
+
! Property
−
===Reflexive===
+
! Statement
−
For a relation {{M|R}} and for all {{M|a\in A}} we have {{M|aRa}} - {{M|a}} is related to itself.
+
! Example
−
===Transitive===
+
! Partial
−
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>
+
! Strict
−
===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.
+
| 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>
 +
| #
 +
| #
 +
|}
 +
 
 
==Definition==
 
==Definition==
 
If we have "just an ordering" it refers to a partial ordering.
 
If we have "just an ordering" it refers to a partial ordering.
Line 22: Line 55:
 
===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.
 +
 +
==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>
  
 
{{Definition|Set Theory}}
 
{{Definition|Set Theory}}

Revision as of 09:45, 12 March 2015

An ordering is a special kind of relation, other than the concept of a relation we require three properties before we can define it.

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]

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