# proof of the well-founded induction principle

This proof is very similar to the proof of the transfinite induction theorem. Suppose $\Phi$ is defined for a well-founded set $(S,R)$, and suppose $\Phi$ is not true for every $a\in S$. Assume further that $\Phi$ satisfies requirements 1 and 2 of the statement. Since $R$ is a well-founded relation, the set $\{a\in S:\neg\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 $\Phi(s)$ for every $s$ such that $sRr$, and by condition 2, $\Phi(r)$ is true, contradiction.

Title proof of the well-founded induction principle ProofOfTheWellfoundedInductionPrinciple 2013-03-22 12:42:20 2013-03-22 12:42:20 jihemme (316) jihemme (316) 7 jihemme (316) Proof msc 03B10