Strict partial ordering
From Maths
Revision as of 13:09, 1 January 2016 by Alec (Talk | contribs) (Created page with ":: '''Note to reader: ''' this page defines {{M|\sqsubset}} as the strict partial ordering under study, this is to try and make the concept distinct from {{M|<}}, which the re...")
- 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.
- Additionally
- 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
