Difference between revisions of "Ordering"
m |
m |
||
| Line 6: | Line 6: | ||
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|<}} | 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== | + | |
| + | 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}} | ||
| + | |||
| + | |||
| + | ==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 {{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" | ||
| + | |- | ||
| + | ! Property | ||
| + | ! Statement | ||
| + | |- | ||
| + | |} | ||
| + | |||
| + | ==Required properties for definition== | ||
These are restated from the [[Relation|relation]] page for convenience | These are restated from the [[Relation|relation]] page for convenience | ||
| Line 48: | Line 80: | ||
| # | | # | ||
|} | |} | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
==Comparable elements== | ==Comparable elements== | ||
Revision as of 14:35, 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.
Contents
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]
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
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.
Well ordering
(see Well-ordering)
Properties
Given a partial ordering [math]\le[/math] of [math]A[/math] and let [ilmath]B\subset A[/ilmath]
| Property | Statement |
|---|
Required properties for definition
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] | # | # |
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]
