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 (→References) |
||
| (4 intermediate revisions by the same user not shown) | |||
| 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}} | ||
| + | ===Alternative definition=== | ||
| + | Alternatively, a ''partial order'' is simply a [[preorder]] that is also ''[[Relation#Types_of_relation|anti-symmetric]]'' ({{AKA}} ''[[Relation#Types_of_relation|Identitive]]''), that is to say{{rAITCTHS2010}}: | ||
| + | * Given a preorder in {{M|X}}, so a {{M|\preceq}} such that {{M|\preceq\subseteq X\times X}}, then {{M|\preceq}} is also a ''partial order'' if: | ||
| + | * {{M|1=\forall x,y\in X[((x,y)\in\preceq\wedge(y,x)\in\preceq)\implies (x=y)]}} or equivalently | ||
| + | ** {{M|1=\forall x,y\in X[(x\preceq y\wedge y\preceq x)\implies(x=y)]}} | ||
| + | ==Terminology== | ||
| + | A tuple consisting of a set {{M|X}} and a partial order {{M|\sqsubseteq}} in {{M|X}} is called a [[poset]]<ref name="AITCTHS2010"/>, then we may say that: | ||
| + | * {{M|(X,\sqsubseteq)}} is a ''poset''. | ||
| + | ==Notation== | ||
| + | Be careful, as {{M|\preceq}}, {{M|\le}} and {{M|\sqsubseteq}} are all used to denote both partial and preorders, so always be clear which one you mean at the point of definition. That is to say write: | ||
| + | * Let {{M|(X,\preceq)}} be a partial ordering in {{M|X}}. Or | ||
| + | * Given any {{M|\preceq}} that is a partial order of {{M|X}} | ||
| + | So forth | ||
==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: | ||
| Line 34: | Line 47: | ||
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. | 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 | * See [[Overview of partial orders]] for more information | ||
| + | ==See also== | ||
| + | * [[Poset]] - the term a tuple consisting of a set equipped with a partial order | ||
| + | * [[Preorder]] - like a partial order except it need not be ''anti-symmetric'' ({{AKA}} ''identitive'') | ||
| + | ** [[Preset]] (is to preorder as poset is to partial order) - a tuple consisting of a set and a pre-order on it. | ||
| + | * [[Strict partial order]] - which induces and is induced by the same ''partial order'', thus an equivalent statement to a partial order | ||
| + | |||
==Notes== | ==Notes== | ||
<references group="Note"/> | <references group="Note"/> | ||
| Line 40: | Line 59: | ||
==References== | ==References== | ||
<references/> | <references/> | ||
| − | {{Definition|Set Theory|Abstract Algebra}} | + | {{Order theory navbox|plain}} |
| + | {{Definition|Set Theory|Abstract Algebra|Order Theory}} | ||
Latest revision as of 10:11, 20 February 2016
- 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)
Contents
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.
- The corresponding strict partial orderings are [ilmath]<[/ilmath], [ilmath]\prec[/ilmath] and [ilmath]\subset[/ilmath]
Alternative definition
Alternatively, a partial order is simply a preorder that is also anti-symmetric (AKA Identitive), that is to say[4]:
- Given a preorder in [ilmath]X[/ilmath], so a [ilmath]\preceq[/ilmath] such that [ilmath]\preceq\subseteq X\times X[/ilmath], then [ilmath]\preceq[/ilmath] is also a partial order if:
- [ilmath]\forall x,y\in X[((x,y)\in\preceq\wedge(y,x)\in\preceq)\implies (x=y)][/ilmath] or equivalently
- [ilmath]\forall x,y\in X[(x\preceq y\wedge y\preceq x)\implies(x=y)][/ilmath]
Terminology
A tuple consisting of a set [ilmath]X[/ilmath] and a partial order [ilmath]\sqsubseteq[/ilmath] in [ilmath]X[/ilmath] is called a poset[4], then we may say that:
- [ilmath](X,\sqsubseteq)[/ilmath] is a poset.
Notation
Be careful, as [ilmath]\preceq[/ilmath], [ilmath]\le[/ilmath] and [ilmath]\sqsubseteq[/ilmath] are all used to denote both partial and preorders, so always be clear which one you mean at the point of definition. That is to say write:
- Let [ilmath](X,\preceq)[/ilmath] be a partial ordering in [ilmath]X[/ilmath]. Or
- Given any [ilmath]\preceq[/ilmath] that is a partial order of [ilmath]X[/ilmath]
So forth
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]
- 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.
- See Overview of partial orders for more information
See also
- Poset - the term a tuple consisting of a set equipped with a partial order
- Preorder - like a partial order except it need not be anti-symmetric (AKA identitive)
- Preset (is to preorder as poset is to partial order) - a tuple consisting of a set and a pre-order on it.
- Strict partial order - which induces and is induced by the same partial order, thus an equivalent statement to a partial order
Notes
- ↑ 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
- ↑ 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
- ↑ Analysis - Part 1: Elements - Krzysztof Maurin
- ↑ Set Theory - Thomas Jech - Third millennium edition, revised and expanded
- ↑ Real and Abstract Analysis - Edwin Hewitt & Karl Stromberg
- ↑ 4.0 4.1 An Introduction to Category Theory - Harold Simmons - 1st September 2010 edition
| ||||||||
