A partial order (A, ≤) is well-founded if every nonempty subset B⊆A has at least one minimal element. (Recall that a element x∈B is minimal if (y∈B and y≤x)⇒x=y). On the other hand, unlike a well-ordered set we allow it to have several (incomparable) minimal elements.

Examples of well-founded orders include: any finite partial order, the natural numbers under the usual order, natural numbers under the division order, ordered pairs of elements from any well-founded order when ordered lexicographically or coordinate-wise.

Well-foundedness is the natural generalisation of well-ordering for orders that are not total. The reason well-foundedness is interesting is that it abstracts precisely the property of the natural numbers that makes induction work. This leads to a generalised induction principle for well-founded sets: well-founded induction.

A standard characterisation that is sometimes used as definition is: A partial order order (A, ≤) is well-founded iff there is no infinite non-constant descending chain x0≥x1≥x2... such that xi∈A and xi≠xi+1 for all i. The "only if" direction needs the axiom of choise.

Note that this does not imply that one can find a bound for the length of chains starting from some element x0. Here is a counterexample (provided by AxelBoldt on wikipedia): For each positive integer n, let Xn be a totally ordered set of size n, and let X be the disjoint union of all Xn together with a new element x which is bigger than all other elements. Then X is a well-founded order, and there are arbitrarily long (but finite) descending chains starting at x.

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