Partial Order

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:

1. aRb and bRc => aRc for all a,b,c in X (transitivity)
2. not aRa for all a in X (non-reflexivity)

Note that these together imply

• not (aRb and bRa) (non-symmetry) [Proof left as an exercise for the TheInterestedReader]

Note also that not every pair of elements need be related.

Examples:

1. set {x}, {y}, {x,y}, {x,y,z}, {y,z} where aRb 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)
2. 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]
3. keys on your keyboard with "height"
   • xRy, vRh, fR6
   • not fRg, not eRy
4. letters of the alphabet with ASCII ordering
   • note that this is a also a total order; all total orders are also partial orders

Examples can be given concerning types and subtypes, but the exact usage varies between authors. Such examples have been omitted to avoid being side-tracked by such issues.

Some formulations of partial orders use the equivalent idea of "<=" rather than "<", but that requires three axioms, not just the two. Such a partial order is called a weak (reflexive) partial order, and is what is usually mean by the term "Partial Order" when used without qualification.

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

PartialOrders turn up all over the place in computing, and recognising them for what they are can save huge amounts of time and effort.

---

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 aRb implies a<b. However, this will only be unique if R is already a total order. Also, a<b won't necessarily imply aRb. 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:

  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 man 1 tsort on any UN*X system.

---

See LatticeStructure

CategoryMath