ProofOfPrincipleOfTransfiniteInduction 2002-02-25 19:32:24 2002-06-01 14:55:32 Proof transfinite induction well ordered set % this is the default PlanetMath preamble. as your knowledge % of TeX increases, you will probably want to edit this, but % it should be fine as is for beginners. % almost certainly you want these \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsfonts} % used for TeXing text within eps files %\usepackage{psfrag} % need this for including graphics (\includegraphics) %\usepackage{graphicx} % for neatly defining theorems and propositions %\usepackage{amsthm} % making logically defined graphics %\usepackage{xypic} % there are many more packages, add them here as you need them % define commands here \newcommand{\Implies}{\Rightarrow} To prove the transfinite induction theorem, we note that the class of ordinals is well-ordered by $\in$. So suppose for some $\Phi$, there are ordinals $\alpha$ such that $\Phi(\alpha)$ is not true. Suppose further that $\Phi$ satisfies the hypothesis, i.e. $\forall\alpha(\forall\beta<\alpha(\Phi(\beta))\Rightarrow\Phi(\alpha))$. We will reach a contradiction. The class $C=\{\alpha:\neg\Phi(\alpha)\}$ is not empty. Note that it may be a proper class, but this is not important. Let $\gamma=\min(C)$ be the $\in$-minimal element of $C$. Then by assumption, for every $\lambda<\gamma$, $\Phi(\lambda)$ is true. Thus, by hypothesis, $\Phi(\gamma)$ is true, contradiction.