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
[hide]Note
Partial orderings and strict orderings are very similar, and the terms differ slightly for each. For example for a and b to be comparable in a partial ordering (for a relation R in A) it means that aRb∨bRa - an example would be ≤
However! For a strict ordering for a and b to be comparable we must have: a≠b⟹[aRb∨bRa], for example <
It can be shown that if < is (strict and linear ordering) then ≤ defined by p≤q⟺[p<q∨p=q] 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 ≮
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 \le, notice a\le b and b\le a\implies a=b
Strict ordering
A relation S in A is a strict ordering if it is asymmetric and transitive.
Well ordering
(see Well-ordering)
Properties
Given a partial ordering \le of A and let B\subset A
| Property | Statement |
|---|
Required properties for definition
These are restated from the relation page for convenience
Here R will be a relation in A
| Property | Statement | Example | Partial | Strict |
|---|---|---|---|---|
| Symmetric | \forall a\in A\forall b\in A(aRb\implies bRa) | equiv relations | ||
| Antisymmetric | \forall a\in A\forall b\in A([aRb\wedge bRa]\implies a=b) | Let A=\mathbb{N} then [a\le b\wedge b\le a]\implies a=b | # | |
| Asymmetric | \forall a\in A\forall b\in B(aRb\implies (b,a)\notin R) | If a < b then b < a is false | # | |
| Reflexive | \forall a\in A(aRa) | equiv relations, Let A=\mathbb{N} then a\le a | # | |
| Transitive | \forall a\in A\forall b\in A\forall c\in A([aRb\wedge bRc]\implies aRc) | equiv relations, A=\mathbb{N} then a\le b\wedge b\le c\iff a\le b\le c\implies a\le c | # | # |
Comparable elements
We say a and b are comparable if the following hold:
Partial ordering
For a and b to be comparable we must have aRb\vee bRa
Strict ordering
For a and b to be comparable we require a\ne b\implies[aRb\vee bRa], notice that false implies false
Total ordering (Linear ordering)
A (partial or strict) ordering is a total (also known as linear) ordering if \forall a\in A\forall b\in B, a and b are comparable using the definitions above.
For example the ordering a|b meaning a divides b (example: (3,6)\iff 3|6) is not total, however \le is, as is >
