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 PartialOrder''''''s 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 a'''R'''b and b'''R'''c => a'''R'''c  for all a,b,c in X (transitivity)
	1 not a'''R'''a for all a in '''X''' (non-reflexivity)
Note that these together imply
	* not (a'''R'''b and b'''R'''a)  (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 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)
	1 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 keys on your keyboard with "height"
		* x'''R'''y, v'''R'''h, f'''R'''6
		* not f'''R'''g, not e'''R'''y
	1 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

PartialOrder''''''s 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 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:

  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