proof of the well-founded induction principle

This proof is very similar to the proof of the transfinite induction theorem. Suppose $\mathrm{\Phi }$ is defined for a well-founded set $(S,R)$, and suppose $\mathrm{\Phi }$ is not true for every $a\in S$. Assume further that $\mathrm{\Phi }$ satisfies requirements 1 and 2 of the statement. Since $R$ is a well-founded relation, the set $\{a\in S:\mathrm{\neg }\mathrm{\Phi }(a)\}$ has an $R$ minimal element $r$. This element is either an $R$ minimal element of $S$ itself, in which case condition 1 is violated, or it has $R$ predessors. In this case, we have by minimality $\mathrm{\Phi }(s)$ for every $s$ such that $sRr$, and by condition 2, $\mathrm{\Phi }(r)$ is true, contradiction.

Title	proof of the well-founded induction principle
Canonical name	ProofOfTheWellfoundedInductionPrinciple
Date of creation	2013-03-22 12:42:20
Last modified on	2013-03-22 12:42:20
Owner	jihemme (316)
Last modified by	jihemme (316)
Numerical id	7
Author	jihemme (316)
Entry type	Proof
Classification	msc 03B10