View source for Partial ordering

:: '''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 reader should have been familiar with from a young age (and thus can taint initial study)
__TOC__
==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}}{{rSTTJ}}{{rRAAAHS}} if:
* The relation {{M|\sqsubseteq}} is all 3 of the following:
{| class="wikitable" border="1"
|-
!
! Name
! Definition
|-
! 1
| [[Relation#Types_of_relation|Reflexive]]
| {{M|1=\forall x\in X[(x,x)\in\sqsubseteq]}} or equivalently<br/>{{M|1=\forall x\in X[x\sqsubseteq x]}}
|-
! 2
| [[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\sqsubseteq y\wedge y\sqsubseteq x)\implies(x=y)]}}
|-
! 3
| [[Relation#Types_of_relation|Transitive]]
| {{M|1=\forall x,y,z\in X[((x,y)\in\sqsubseteq\wedge(y,z)\in\sqsubseteq)\implies(x,z)\in\sqsubseteq]}} or equivalently<br/>
{{M|1=\forall x,y,z\in X[(x\sqsubseteq y\wedge y\sqsubseteq z)\implies(x\sqsubseteq z)]}}
|}
* '''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}}
===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]]==
Here, let {{M|\preceq}} be a ''partial ordering'' as defined above, then the relation, {{M|\prec}} defined by:
* {{M|(x,y)\in\prec\iff[x\ne y\wedge x\preceq y]}}
is a [[strict partial ordering]]
* '''Note: ''' every [[strict partial ordering]] induces a partial ordering, given a strict partial ordering, {{M|<}}, we can define a relation {{M|\le}} as:
** {{M|1=x\le y\iff[x=y\vee x<y]}} or equivalently (in relational form): {{M|1=(x,y)\in\le\iff[x=y\vee (x,y)\in<]}}
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==
<references group="Note"/>
==Warnings==
<references group="Warning"/>
==References==
<references/>
{{Order theory navbox}}
{{Definition|Set Theory|Abstract Algebra|Order Theory}}