Partial ordering

From Maths
Revision as of 13:17, 1 January 2016 by Alec (Talk | contribs) (Definition)

Jump to: navigation, search
Note to reader: this page defines [ilmath]\sqsubseteq[/ilmath] as the partial ordering under study, this is to try and make the concept distinct from [ilmath]\le[/ilmath], which the reader should have been familiar with from a young age (and thus can taint initial study)

Definition

Given a relation, [ilmath]\sqsubseteq[/ilmath] in [ilmath]X[/ilmath] (mathematically: [ilmath]\sqsubseteq\subseteq X\times X[/ilmath][Note 1]) we say [ilmath]\sqsubseteq[/ilmath] is a partial order[1][2][3] if:

  • The relation [ilmath]\sqsubseteq[/ilmath] is all 3 of the following:
Name Definition
1 Reflexive [ilmath]\forall x\in X[(x,x)\in\sqsubseteq][/ilmath] or equivalently
[ilmath]\forall x\in X[x\sqsubseteq x][/ilmath]
2 Identitive (AKA: antisymmetric) [ilmath]\forall x,y\in X[((x,y)\in\sqsubseteq\wedge(y,x)\in\sqsubseteq)\implies (x=y)][/ilmath] or equivalently

[ilmath]\forall x,y\in X[(x\sqsubseteq y\wedge y\sqsubseteq x)\implies(x=y)][/ilmath]

3 Transitive [ilmath]\forall x,y,z\in X[((x,y)\in\sqsubseteq\wedge(y,z)\in\sqsubseteq)\implies(x,z)\in\sqsubseteq][/ilmath] or equivalently

[ilmath]\forall x,y,z\in X[(x\sqsubseteq y\wedge y\sqsubseteq z)\implies(x\sqsubseteq z)][/ilmath]

  • Note: [ilmath]\le[/ilmath], [ilmath]\preceq[/ilmath] or [ilmath]\subseteq[/ilmath][Warning 1] are all commonly used for partial relations too.

Induced strict partial ordering

Here, let [ilmath]\preceq[/ilmath] be a partial ordering as defined above, then the relation, [ilmath]\prec[/ilmath] defined by:

  • [ilmath](x,y)\in\prec\iff[x\ne y\wedge x\preceq y][/ilmath]

is a strict partial ordering

  • Note: every strict partial ordering induces a partial ordering, given a strict partial ordering, [ilmath]<[/ilmath], we can define a relation [ilmath]\le[/ilmath] as:
    • [ilmath]x\le y\iff[x=y\vee x<y][/ilmath] or equivalently (in relational form): [ilmath](x,y)\in\le\iff[x=y\vee (x,y)\in<][/ilmath]

In fact there is a 1:1 correspondence between partial and strict partial orderings, this is why the term "partial ordering" is used so casually, as given a strict you have a partial, given a partial you have a strict.

Notes

  1. Here [ilmath]\sqsubseteq[/ilmath] is the name of the relation, so [ilmath](x,y)\in \sqsubseteq[/ilmath] means [ilmath]x\sqsubseteq y[/ilmath] - as usual for relations

Warnings

  1. I avoid using [ilmath]\subseteq[/ilmath] for anything other than denoting subsets, the relation and the set it relates on will go together, so you'll already be using [ilmath]\subseteq[/ilmath] to mean subset

References

  1. Analysis - Part 1: Elements - Krzysztof Maurin
  2. Set Theory - Thomas Jech - Third millennium edition, revised and expanded
  3. Real and Abstract Analysis - Edwin Hewitt & Karl Stromberg