Well-founded set¶
A binary relation on a set or class for which every nonempty subset has a minimal element, equivalently under suitable choice principles one admitting no infinite descending chain.
Core Idea¶
A binary relation is well-founded on a set when every nonempty subset contains a minimal element: some member with no predecessor from that subset under the relation. Minimality is local to the chosen subset and need not supply one least or unique element. The orientation must be explicit because reversing a familiar order changes the descent direction. Under the axiom of dependent choice, the minimal-element condition is equivalent to saying there is no infinite sequence descending step after step.
Scope of Application¶
Use well-founded relation with carrier, relation orientation, subset or subclass quantifier, foundational axioms, set-like convention, minimal-element proof or descending-chain argument, and intended induction stated. Use well-founded relation with carrier, relation orientation, subset or subclass quantifier, foundational axioms, set-like convention, minimal-element proof or descending-chain argument, and intended induction stated.
- Set theory. Analyzes membership and ranks.
- Order theory. Studies well-orders and partial orders.
- Logic. Supports induction.
- Computer science. Proves termination.
- Recursive definitions. Defines values by predecessors.
Clarity¶
A global minimum does not suffice: another subset may omit it and lack any minimal member. The definition deliberately quantifies over every nonempty subset. The closest near miss sets the boundary: Acyclicity is closest: finite acyclic relations are well-founded, but an infinite acyclic relation can still contain an endless descending chain.
Manages Complexity¶
No infinite descending chain is intuitive but its equivalence can use choice. Formal statements should identify which characterization and foundational assumptions are active. The central minimal-element definition–chain intuition tradeoff is this: Equivalent formulations aid proof while choice assumptions can matter. A second termination proof–operational execution tension matters because Mathematical descent ensures recursion while an implementation may have independent resource failures.
Abstract Reasoning¶
Use three linked moves: fix carrier and downward relation; take an arbitrary nonempty subset; produce a predecessor-free member within it. As a collapse test, the case exits when some nonempty subset lacks a minimal element or, under the appropriate assumptions, an infinite descending sequence exists. A fourth check is to alternatively derive contradiction from an assumed descending chain under stated choice.
Knowledge Transfer¶
Termination by minimal predecessor structure transfers across proofs and programs, but binary-relation orientation and foundational quantification delimit well-foundedness. The nearest stopping boundary is explicit: Acyclicity is closest: finite acyclic relations are well-founded, but an infinite acyclic relation can still contain an endless descending chain. The inclusion test remains: A relation is well-founded when every nonempty relevant subset has at least one element with no predecessor in that subset. The structure no longer applies when the case exits when some nonempty subset lacks a minimal element or, under the appropriate assumptions, an infinite descending sequence exists. No canonical parent prime is currently asserted; broader structural comparisons remain related-prime analogies until separately adjudicated in the DAG. It adds total ordering and least elements.
Neighborhood in Abstraction Space¶
Well-founded set sits in a crowded region of the domain-specific corpus (31st percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.
Family — Formal Models & Logical Foundations (33 abstractions)
Nearest neighbors
- Constructional System — 0.90
- Set Cover Problem — 0.89
- Filtration (algebra) — 0.89
- Supertransitive class — 0.88
- 3SUM — 0.88
Computed from structural-signature embeddings · 2026-10-08