Difference between revisions of "Ordering"

Revision as of 15:43, 5 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.

Required properties

These are restated from the 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 [ilmath]R[/ilmath] in [ilmath]A[/ilmath] is symmetric if for all [ilmath]a,b\in A[/ilmath] we have that [ilmath]aRb\implies bRa[/ilmath] - a property of equivalence relations

Antisymmetric

A binary relation [ilmath]R[/ilmath] in [ilmath]A[/ilmath] is antisymmetric if for all [ilmath]a,b\in A[/ilmath] we have [math]aRb\text{ and }bRA\implies a=b[/math]
Symmetric implies elements are related to each other, antisymmetric implies only the same things are related to each other.

Reflexive

For a relation [ilmath]R[/ilmath] and for all [ilmath]a\in A[/ilmath] we have [ilmath]aRa[/ilmath] - [ilmath]a[/ilmath] is related to itself.

Transitive

A relation [ilmath]R[/ilmath] in [ilmath]A[/ilmath] is transitive if for all [ilmath]a,b,c\in A[/ilmath] we have [math][aRb\text{ and }bRc\implies aRc][/math]

Asymmetric

A relation [ilmath]S[/ilmath] in [ilmath]A[/ilmath] is asymmetric if [ilmath]aSb\implies(b,a)\notin S[/ilmath], for example [ilmath]<[/ilmath] has this property, we can have [ilmath]a<b[/ilmath] or [ilmath]b<a[/ilmath] but not both.

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.