display | more...
(Ho hum. Can anything mathematical be a thing? L. E. J. Brouwer didn't think so.)

A partial order is a mathematical relation that is transitive, antisymmetric, therefore antireflexive, but it is not necessarily total.

That is, if x is before y, y cannot be before x, but many x and y may not be ordered at all.

More precisely, → is a partial order iff:

Examples of partial orders include "x divides y and has smaller absolute value" and "x is an ancestor of y".

Any partial order has a(t least one) total order which is consistent with it (i.e. extends it). See topological sort for how to find this (efficiently!) in the finite case. Use the compactness property of first order logic to get this in the infinite case (the Axiom of Choice or Zorn's lemma also do the job, naturally).

To clarify: This definition of "partial order" matches our intuitions of "something like < except we can't necessarily compare any two elements". It is also common to define "partial order" to match our intuition of "something like except we can't necessarily compare any two elements". In that case, the first property (irreflexivity) turns into reflexivity.

I choose to work with sharp orders (see total order, which also defines "<-like" orders, as I find them somewhat more natural.

Log in or register to write something here or to contact authors.