# 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 |