Strict partial ordering
From Maths
(Redirected from Strict partial order)
 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.
Definition
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.
 See Overview of partial orders for more information
Warnings
 ↑ 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
Notes
 ↑ 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
References
