Wellfoundedness

Wellfoundedness is a property of a binary relation that ensures there are no infinite descending sequences and that every nonempty subset contains a minimal element with respect to the relation.

Formally, a relation R on a set A is well-founded if every nonempty subset S of A has an R-minimal element. An element x in S is R-minimal if there is no y in S with y R x. Equivalently, R is well-founded on A if there is no infinite sequence x0, x1, x2, ... of elements of A such that x_{n+1} R x_n for every n.

Wellfoundedness has important connections to set theory and recursion. In Zermelo-Fraenkel set theory, the axiom of foundation (or regularity) states that the membership relation ∈ is well-founded on the universe of sets, preventing infinite ∈-descending chains. This underpins many arguments about the existence and construction of sets.

In addition, wellfoundedness enables principles of induction and recursion. Transfinite induction and transfinite recursion can be formulated along any well-founded relation, allowing definitions and proofs by progressing along well-ordered or more general well-founded structures.

Common examples include the natural numbers with the usual order less than being well-founded, since every nonempty subset has a least element. By contrast, the integers with the usual order are not well-founded, as there exist infinite descending sequences like 0 > -1 > -2 > ...

Overall, wellfoundedness provides a robust framework for controlling infinite descent and supporting constructive definitions in mathematics.