wellfounded

Wellfounded describes a property of a binary relation R on a set X. R is well-founded if every nonempty subset S of X contains an R-minimal element, meaning an element m in S for which there is no s in S with s R m. Equivalently, there is no infinite sequence x0 R x1 R x2 R … of elements of X. This notion captures the idea of no infinite descent with respect to R.

Common examples help illustrate the concept. The natural numbers with the usual order < are well-founded: every nonempty subset has a least element. By contrast, the relation > on natural numbers is not well-founded, since the whole set N has no minimal element under >. In set theory, the membership relation ∈ on the universe is well-founded by the Axiom of Foundation, which forbids infinite ∈-descending chains.

Well-foundedness underpins several fundamental principles. Well-founded induction and well-founded recursion allow proofs and definitions by assuming a property or definition for all “smaller” elements with respect to R. Transfinite induction, a generalization of ordinary induction, extends these ideas to well-founded relations that may be longer than finite. In computer science, well-founded orders are used to prove termination of recursive definitions and algorithms. In set theory, many constructions rely on a well-founded ∈ relation, including the cumulative hierarchy and the rank function, which organize sets by their construction stages.

In summary, wellfoundedness characterizes when descent along a relation cannot proceed indefinitely, enabling robust forms of induction, recursion, and foundational constructions in mathematics.