Difference between revisions of "Partial ordering"
From Maths
(Created page with ":: '''Note to reader: ''' this page defines {{M|\sqsubseteq}} as the partial ordering under study, this is to try and make the concept distinct from {{M|\le}}, which the reade...") |
m (→Definition) |
||
Line 2: | Line 2: | ||
__TOC__ | __TOC__ | ||
==Definition== | ==Definition== | ||
− | Given a [[relation]], {{M|\sqsubseteq}} in {{M|X}} (mathematically: {{M|\sqsubseteq\subseteq X\times X}}<ref group="Note">Here {{M|\sqsubseteq}} is the name of the relation, so {{M|(x,y)\in \sqsubseteq}} means {{M|x\sqsubseteq y}} - as usual for [[relation|relations]]</ref>) we say {{M|\sqsubseteq}} is a ''partial order''{{rAPIKM}} if: | + | Given a [[relation]], {{M|\sqsubseteq}} in {{M|X}} (mathematically: {{M|\sqsubseteq\subseteq X\times X}}<ref group="Note">Here {{M|\sqsubseteq}} is the name of the relation, so {{M|(x,y)\in \sqsubseteq}} means {{M|x\sqsubseteq y}} - as usual for [[relation|relations]]</ref>) we say {{M|\sqsubseteq}} is a ''partial order''{{rAPIKM}}{{rSTTJ}}{{rRAAAHS}} if: |
* The relation {{M|\sqsubseteq}} is all 3 of the following: | * The relation {{M|\sqsubseteq}} is all 3 of the following: | ||
{| class="wikitable" border="1" | {| class="wikitable" border="1" | ||
Line 15: | Line 15: | ||
|- | |- | ||
! 2 | ! 2 | ||
− | | [[Relation#Types_of_relation|Identitive]] | + | | [[Relation#Types_of_relation|Identitive]] ({{AKA}}: [[Relation#Types_of_relation|antisymmetric]]) |
| {{M|1=\forall x,y\in X[((x,y)\in\sqsubseteq\wedge(y,x)\in\sqsubseteq)\implies (x=y)]}} or equivalently<br/> | | {{M|1=\forall x,y\in X[((x,y)\in\sqsubseteq\wedge(y,x)\in\sqsubseteq)\implies (x=y)]}} or equivalently<br/> | ||
{{M|1=\forall x,y\in X[(x\sqsubseteq y\wedge y\sqsubseteq x)\implies(x=y)]}} | {{M|1=\forall x,y\in X[(x\sqsubseteq y\wedge y\sqsubseteq x)\implies(x=y)]}} | ||
Line 26: | Line 26: | ||
* '''Note:''' {{M|\le}}, {{M|\preceq}} or {{M|\subseteq}}<ref group="Warning">I avoid using {{M|\subseteq}} for anything other than denoting [[subset|subsets]], the relation and the set it relates on will go together, so you'll already be using {{M|\subseteq}} to mean subset</ref> are all commonly used for partial relations too. | * '''Note:''' {{M|\le}}, {{M|\preceq}} or {{M|\subseteq}}<ref group="Warning">I avoid using {{M|\subseteq}} for anything other than denoting [[subset|subsets]], the relation and the set it relates on will go together, so you'll already be using {{M|\subseteq}} to mean subset</ref> are all commonly used for partial relations too. | ||
** The corresponding [[strict partial ordering|strict partial orderings]] are {{M|<}}, {{M|\prec}} and {{M|\subset}} | ** The corresponding [[strict partial ordering|strict partial orderings]] are {{M|<}}, {{M|\prec}} and {{M|\subset}} | ||
+ | |||
==Induced [[strict partial ordering]]== | ==Induced [[strict partial ordering]]== | ||
Here, let {{M|\preceq}} be a ''partial ordering'' as defined above, then the relation, {{M|\prec}} defined by: | Here, let {{M|\preceq}} be a ''partial ordering'' as defined above, then the relation, {{M|\prec}} defined by: |
Revision as of 13:17, 1 January 2016
- Note to reader: this page defines ⊑ as the partial ordering under study, this is to try and make the concept distinct from ≤, which the reader should have been familiar with from a young age (and thus can taint initial study)
Definition
Given a relation, ⊑ in X (mathematically: ⊑⊆X×X[Note 1]) we say ⊑ is a partial order[1][2][3] if:
- The relation ⊑ is all 3 of the following:
Name | Definition | |
---|---|---|
1 | Reflexive | ∀x∈X[(x,x)∈⊑] or equivalently ∀x∈X[x⊑x] |
2 | Identitive (AKA: antisymmetric) | ∀x,y∈X[((x,y)∈⊑∧(y,x)∈⊑)⟹(x=y)] or equivalently ∀x,y∈X[(x⊑y∧y⊑x)⟹(x=y)] |
3 | Transitive | ∀x,y,z∈X[((x,y)∈⊑∧(y,z)∈⊑)⟹(x,z)∈⊑] or equivalently ∀x,y,z∈X[(x⊑y∧y⊑z)⟹(x⊑z)] |
- Note: ≤, ⪯ or ⊆[Warning 1] are all commonly used for partial relations too.
- The corresponding strict partial orderings are <, ≺ and ⊂
Induced strict partial ordering
Here, let ⪯ be a partial ordering as defined above, then the relation, ≺ defined by:
- (x,y)∈≺⟺[x≠y∧x⪯y]
- Note: every strict partial ordering induces a partial ordering, given a strict partial ordering, <, we can define a relation ≤ as:
- x≤y⟺[x=y∨x<y] or equivalently (in relational form): (x,y)∈≤⟺[x=y∨(x,y)∈<]
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
Notes
Warnings
- Jump up ↑ I avoid using ⊆ for anything other than denoting subsets, the relation and the set it relates on will go together, so you'll already be using ⊆ to mean subset