Editing Well-founded relation (section)

==Induction and recursion==

An important reason that well-founded relations are interesting is because a version of [[transfinite induction]] can be used on them: if ({{math|''X'', ''R''}}) is a well-founded relation, {{math|''P''(''x'')}} is some property of elements of {{mvar|X}}, and we want to show that

:{{math|''P''(''x'')}} holds for all elements {{mvar|x}} of {{mvar|X}},

it suffices to show that:

: If {{mvar|x}} is an element of {{mvar|X}} and {{math|''P''(''y'')}} is true for all {{mvar|y}} such that {{math|''y'' ''R'' ''x''}}, then {{math|''P''(''x'')}} must also be true.

That is,
<math display=block>(\forall x \in X)\;[(\forall y \in X)\;[y\mathrel{R}x \implies P(y)] \implies P(x)]\quad\text{implies}\quad(\forall x \in X)\,P(x).</math>

Well-founded induction is sometimes called Noetherian induction,<ref>[[Nicolas Bourbaki|Bourbaki, N.]] (1972) ''Elements of mathematics. Commutative algebra'', Addison-Wesley.</ref> after [[Emmy Noether]].

On par with induction, well-founded relations also support construction of objects by [[transfinite recursion]]. Let {{math|(''X'', ''R'')}} be a [[binary relation#Relations over a set|set-like]] well-founded relation and {{mvar|F}} a function that assigns an object {{math|''F''(''x'', ''g'')}} to each pair of an element {{math|''x'' ∈ ''X''}} and a function {{mvar|g}} on the [[initial segment]] {{math|{{(}}''y'': ''y'' ''R'' ''x''{{)}}}} of {{mvar|X}}. Then there is a unique function {{mvar|G}} such that for every {{math|''x'' ∈ ''X''}},
<math display=block>G(x) = F\left(x, G\vert_{\left\{y:\, y\mathrel{R}x\right\}}\right).</math>

That is, if we want to construct a function {{mvar|G}} on {{mvar|X}}, we may define {{math|''G''(''x'')}} using the values of {{math|''G''(''y'')}} for {{math|''y'' ''R'' ''x''}}.

As an example, consider the well-founded relation {{math|('''N''', ''S'')}}, where {{math|'''N'''}} is the set of all [[natural numbers]], and {{mvar|S}} is the graph of the successor function {{math|''x'' ↦ ''x''+1}}. Then induction on {{mvar|S}} is the usual [[mathematical induction]], and recursion on {{mvar|S}} gives [[primitive recursive functions|primitive recursion]]. If we consider the order relation {{math|('''N''', <)}}, we obtain [[complete induction]], and [[course-of-values recursion]]. The statement that {{math|('''N''', <)}} is well-founded is also known as the [[well-ordering principle]].

There are other interesting special cases of well-founded induction. When the well-founded relation is the usual ordering on the class of all [[ordinal numbers]], the technique is called [[transfinite induction]]. When the well-founded set is a set of recursively-defined data structures, the technique is called [[structural induction]]. When the well-founded relation is set membership on the universal class, the technique is known as [[∈-induction]]. See those articles for more details.