Strict partial ordering

From Maths
(Redirected from Strict partial order)
Jump to: navigation, search
Note to reader: this page defines [ilmath]\sqsubset[/ilmath] as the strict partial ordering under study, this is to try and make the concept distinct from [ilmath]<[/ilmath], which the reader should have been familiar with from a young age (and thus can taint initial study), this notation corresponds with the notation in partial ordering.


Given a relation, [ilmath]\sqsubset[/ilmath] on [ilmath]X[/ilmath] (mathematically: [ilmath]\sqsubset\subseteq X\times X[/ilmath][Note 1]) we say that [ilmath]\sqsubset[/ilmath] is a strict partial ordering[1] if:

  • The relation [ilmath]\prec[/ilmath] is both of the following:
Name Meaning
1 Irreflexive
(not reflexive)
[ilmath]\forall x\in X[(x,x)\notin\sqsubset][/ilmath] or equivalently:

[ilmath]\forall x\in X[x\not\sqsubset x][/ilmath]

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

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

  • Note: [ilmath]<[/ilmath], [ilmath]\prec[/ilmath] and [ilmath]\subset[/ilmath] are all commonly used for strict relations too
    • Their corresponding partial orders are [ilmath]\le[/ilmath], [ilmath]\preceq[/ilmath] and [ilmath]\subseteq[/ilmath][Warning 1]

Induced partial ordering

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

  • [ilmath](x,y)\in\preceq\iff[x = y\vee x\prec y][/ilmath]

is a partial ordering

  • Note: every partial ordering induces a strict partial ordering, given a partial ordering, [ilmath]\le[/ilmath], we can define a relation [ilmath]<[/ilmath] as:
    • [ilmath]x< y\iff[x\ne y\wedge x\le y][/ilmath] or equivalently (in relational form): [ilmath](x,y)\in\le\iff[x\ne y\wedge (x,y)\in\le][/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.


  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


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


  1. Set Theory - Thomas Jech - Third millennium edition, revised and expanded