The principle that if a relation R on a set is well-founded (there are no infinite descending R-chains), and whenever an element x has the property provided all R-smaller elements do, then every element has that property; it generalizes ordinary induction on the naturals to arbitrary well-founded orders.

Principle

Induction on a well-founded relation: to prove P(x) for all x it suffices to prove that for arbitrary x, if P(y) holds for all y with y R x (or y < x), then P(x) holds. Well-foundedness ensures no minimal-counterexample paradox occurs.

Demonstration

To prove termination of a rewrite system, define a well-founded measure assigning ordinals or natural numbers to terms and prove that each reduction strictly decreases the measure; by well-founded induction on the measure, no infinite descent is possible and thus all reduction sequences terminate.

Misapplication

Applying well-founded induction to relations that are not well-founded (for example the integers under the usual order), or assuming structural induction on syntax automatically implies well-founded induction without verifying the well-foundedness of the chosen relation.

Consequence

Provides a uniform method to prove properties and termination across diverse domains (ordinals, term rewriting, program termination); it enables proofs by minimal counterexample and justifies recursive definitions indexed by well-founded measures.

Reversal

If the relation is not well-founded, induction can fail: there may exist elements with no minimal counterexample argument, and properties intended to hold by descent arguments can be false due to infinite descending chains.

Boundary

Requires the relation to be well-founded on the domain in question; it does not apply to arbitrary partial orders with infinite descending sequences and does not by itself provide a constructive witness unless the relation and induction hypotheses are effective.

Semantic Tension

Tension with structural induction and ordinary mathematical induction: structural induction is a special case when the structure induces a well-founded relation, while well-founded induction applies more broadly but may require non-trivial well-founded measures or ordinals to be exhibited.

Synthesis

Well-founded induction abstracts the core of induction: by replacing the natural-number predecessor relation with any well-founded order, it reduces global assertions to local descent checks—if each element follows from all smaller ones under a well-founded relation, then the property holds universally, enabling termination proofs and reasoning by minimal counterexample.