Difference between revisions of "Partial ordering"

From Maths
Jump to: navigation, search
(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]] or [[Relation#Types_of_relation|Antisymmetric]]
+
| [[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 xX[(x,x)∈⊑] or equivalently
xX[xx]
2 Identitive (AKA: antisymmetric) x,yX[((x,y)∈⊑(y,x)∈⊑)(x=y)] or equivalently

x,yX[(xyyx)(x=y)]

3 Transitive x,y,zX[((x,y)∈⊑(y,z)∈⊑)(x,z)∈⊑] or equivalently

x,y,zX[(xyyz)(xz)]

  • Note: , or [Warning 1] are all commonly used for partial relations too.

Induced strict partial ordering

Here, let be a partial ordering as defined above, then the relation, defined by:

  • (x,y)∈≺[xyxy]

is a strict partial ordering

  • Note: every strict partial ordering induces a partial ordering, given a strict partial ordering, <, we can define a relation as:
    • xy[x=yx<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.

Notes

  1. Jump up Here is the name of the relation, so (x,y)∈⊑ means xy - as usual for relations

Warnings

  1. 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

References

  1. Jump up Analysis - Part 1: Elements - Krzysztof Maurin
  2. Jump up Set Theory - Thomas Jech - Third millennium edition, revised and expanded
  3. Jump up Real and Abstract Analysis - Edwin Hewitt & Karl Stromberg