Partial ordering

From Maths
Revision as of 09:40, 20 February 2016 by Alec (Talk | contribs)

Jump to: navigation, search
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.

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 X, so a such that ⪯⊆X×X, then is also a partial order if:
  • x,yX[((x,y)∈⪯(y,x)∈⪯)(x=y)] or equivalently
    • x,yX[(xyyx)(x=y)]

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.

See also

  • Preorder - like a partial order except it need not be anti-symmetric (AKA identitive)
  • Strict partial order - which induces and is induced by the same partial order, thus an equivalent statement to a partial order

Notes

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

Warnings

  1. <cite_references_link_accessibility_label> 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. <cite_references_link_accessibility_label> Analysis - Part 1: Elements - Krzysztof Maurin
  2. <cite_references_link_accessibility_label> Set Theory - Thomas Jech - Third millennium edition, revised and expanded
  3. <cite_references_link_accessibility_label> Real and Abstract Analysis - Edwin Hewitt & Karl Stromberg
  4. <cite_references_link_accessibility_label> An Introduction to Category Theory - Harold Simmons - 1st September 2010 edition