Informally, a PartialOrder on a set is a way of saying that some things are "bigger than" others, without committing to every pair of items being comparable. For example, given some sets we might say that **A** is clearly "bigger than" **B** if **A** entirely contains **B**, but that doesn't then say anything about disjoint sets, regardless of their size.
See OrderingDateRanges for a place where knowledge of PartialOrders would be useful.
This material does appear on WikiPedia (http://en.wikipedia.org/wiki/Partial_order) and MathWorld (http://mathworld.wolfram.com/PartialOrder.html), but it is here specifically because so much nonsense was being written about date ranges that it seemed worth having this notion flagged up for reference. Once here, it may as well be precise and specific. This sort of basic, fundamental math is of real use in the programming I do, and from other discussions on this wiki seems sadly lacking. A few pages might well be worth it.
The remainder of this page must be ReadLikeMath ...

Abstractly, a strict partial order is a collection of objects,**X**, with a relationship **R** (thought of as "<", "strictly less than") that has the following properties:

Say we run a program with three threads, one prints ABCDE, one prints ZYXWV and one prints MNOPQ. Then it's correct for that program to print AZBCMNOYXDPQWEV or ZABCMNOYXDPQWEV, but a bug if it prints BAZCMNOYXDPQWEV. The correct output of the program is defined by a partial order (and a particularly easy one at that, since it is defined by 3 disjoint total orders). -- JohnFarrell

Given a finite set*S* with a PartialOrder, the PartialOrder can be embedded in a TotalOrder. Call the PartialOrder **R** as above. Then you can construct a TotalOrder (*S*, <) such that a**R**b implies a<b. However, this will only be unique if **R** is already a total order. Also, a<b won't necessarily imply a**R**b. For many purposes, the non-uniqueness doesn't matter. Suppose you have a set of tasks with dependencies: perhaps *make* or *ant* targets. You want to schedule them, and you can't do anything in parallel. It's always possible to do so, and the scheduling provides a TotalOrder. You don't care that there are alternative orderings.
For the subsets of {a,b,c,d,e,f} two (of the potentially many) total orders are:
*man 1 tsort* on any UN*X system.

See LatticeStructure CategoryMath

Abstractly, a strict partial order is a collection of objects,

- a
**R**b and b**R**c => a**R**c for all a,b,c in X (transitivity) - not a
**R**a for all a in**X**(non-reflexivity)

- not (a
**R**b and b**R**a) (non-symmetry) [Proof left as an exercise for the TheInterestedReader]

- set {x}, {y}, {x,y}, {x,y,z}, {y,z} where a
**R**b if and only if**a**is non-trivially contained in**b**.- {x}
**R**{x,y}, {x,y}**R**{x,y,z}, {x}**R**{x,y,z}, {y,z}**R**{x,y,z} - not {x}
**R**{x} (trivial containment) - not {x}
**R**{y} (no containment at all) - not {x,z}
**R**{x,y,z} ({x,z} not in our collection of elements)

- {x}
- intervals on the reals with [u,v]
**R**[x,y] iff v<x- [1,2]
**R**[3,5] - [-e,e^pi]
**R**[100,100.000001] - not [1,pi]
**R**[3,7] - not [1,1]
**R**[0,2^10]

- [1,2]
- keys on your keyboard with "height"
- x
**R**y, v**R**h, f**R**6 - not f
**R**g, not e**R**y

- x
- letters of the alphabet with ASCII ordering
- note that this is a
**also**a total order; all total orders are also partial orders

- note that this is a

**Theorem**- For every partial order there is an isomorphic partial order whose elements are sets and where the relationship is non-trivial containment.
**Theorem**- Every partial order can be extended to a total or linear ordering. If the partial order is not already totally ordered then there will be more than one linear extension of it.
**Proofs**- Left as an exercise for the TheInterestedReader

Say we run a program with three threads, one prints ABCDE, one prints ZYXWV and one prints MNOPQ. Then it's correct for that program to print AZBCMNOYXDPQWEV or ZABCMNOYXDPQWEV, but a bug if it prints BAZCMNOYXDPQWEV. The correct output of the program is defined by a partial order (and a particularly easy one at that, since it is defined by 3 disjoint total orders). -- JohnFarrell

Given a finite set

Empty set < {a] < {b} < {c} < ... < {f} < {a,b} < {a, c} < ... < {e, f} < {a, b, c} < ... < {d, e, f} < ... 0-element 1-element 2-element 3-element etc.and

Empty < {a} < {b} < {a, b} < {c} < {a, c} < {b, c} < {a, b, c} < ... Think binary.The usual and efficient algorithm is called the TopologicalSort?. Look up Section 2.2.3 of TheArtOfComputerProgramming. Hey, everybody has to resort to Knuth sometime. Or try

See LatticeStructure CategoryMath

EditText of this page (last edited October 25, 2005) or FindPage with title or text search