Principle of Transfinite Induction
I am well familiar with the principle of mathematical induction. But while reading a paper by Roggenkamp, I encountered the Principle of Transfinite Induction (PTI). I do not know the theory of cardinals, and never had a formal introduction to Set theory or Cardinals theory. The concept of PTI was amusing to me so I looked it up.
I googled and open Wikipedia which states it as "Let $P(\alpha)$ be a property defined for all ordinals $\alpha$. Suppose that whenever $P(\beta)$ is true for all $\beta < \alpha$, then $P(\alpha)$ is also true (including the case that $P(0)$ is true given the vacuously true statement that $P(\alpha)$ is true for all $\alpha\in\emptyset$). Then transfinite induction tells us that $P$ is true for all ordinals."
To understand it, I definitely had to read what an ordinal is. So another link on Wikipedia says: "A set S is an ordinal if and only if S is strictly well-ordered with respect to set membership and every element of S is also a subset of S." (due to von Neumann)
Now these definitions do not make it clear to me what PTI means. I know every set can be well ordered, i.e. given any set $S$, we can find a well ordered set $A$ such that $S$ can be written as $$S=\{s_\alpha: \alpha\in A\}$$ which I understand has been used in it.
Can some explain what PTI says, along with explaining what an ordinal is (which is comprehensible to a non-set theorist) and how it can be used by using some beginner cases to illustrate it.
Thanks!
The ordinals are what you get when you iterate the operations of 'successor' and 'supremum' indefinitely, much like the natural numbers are what you get when you iterate the sole operator 'successor' indefinitely.
- Start with $0$. Iterating successors we get the natural numbers, which are the finite ordinals: $$0, 1, 2, 3, \dots $$
- Now take the supremum. We call this ordinal $\omega$. Iterating successors we get a longer sequence: $$0, 1, 2, \dots, \omega, \omega+1, \omega+2, \dots$$
- The supremum of this sequence is the ordinal $\omega + \omega$. We can then take even more successors: $$0, 1, \dots, \omega, \omega+1, \dots, \omega + \omega, \omega + \omega + 1, \dots$$ The supremum of this sequence is the ordinal $\omega + \omega + \omega$.
Continuing in this way gives rise to the following ordinals: $$\omega,\ \omega+\omega,\ \omega+\omega+\omega,\ \omega + \omega + \omega + \omega, \dots$$ So we can take another supremum to obtain the ordinal $\omega \cdot \omega$. Likewise we obtain $\omega \cdot \omega \cdot \omega$, and so on, the supremum of all of which is $\omega^{\omega}$. Then we obtain $\omega^{\omega^{\omega}}$ and so on, the supremum of all of which is called $\varepsilon_0$... and so on.
Continuing even further rise to the countable ordinals. But that itself is a set of ordinals, so it has a supremum, called $\omega_1$. Then we can take its successors $\omega_1+1$ and so on.
The ordinals are precisely the things which can be obtained by iterating the successor operation and taking suprema of sets of ordinals.
More formally, the (von Neumann) ordinals are the elements of the class $\mathrm{Ord}$, which is the closure of $\varnothing$ under the successor operation $x \mapsto x \cup \{ x \}$ and under taking arbitrary unions.
The principle of transfinite induction essentially says that, for a given formula $P(x)$, if $P(0)$ is true, and the truth of $P(\alpha)$ is preserved by taking successors and suprema, then $P(\alpha)$ must be true of all ordinals $\alpha$. (We can omit the $P(0)$ case because $0 = \sup (\varnothing$).)
I believe the best way to understand the principle of transfinite induction without reference to ordinals is as follows (based on the discussion in Folland, 1999, Section 0.4):
Let $(X,\succsim)$ be a non-empty, well-ordered set. For each $x\in X$, define $$S_x\equiv\{y\in X\mid y\prec x\}$$ to be the set of (strict) predecessors of $x$. Now suppose that a subset $Y\subseteq X$ satisfies the following property: $$S_x\subseteq Y\Longrightarrow x\in Y\quad\text{for any $x\in X$}.$$ The principle of transfinite induction claims that in this case, one has $Y=X$.
In words, suppose that if $Y$ contains all predecessors of $x$, then $Y$ contains $x$ itself as well. This means that the property defining the subset $Y$ gets “inherited upwards,” which is the intuitive idea behind induction. The claim is that if such a property is inherited inductively, then this property must be true for all of $X$. This is the principle of transfinite induction.
A short proof: Suppose that the premise holds—one wishes to show that $Y=X$. For the sake of contradiction, assume that $Y\neq X$. Then, the set $X\setminus Y$ is not empty, so it has a least element $x_0$ according to the well-order $\succsim$. Since $x_0$ is minimal, one has that if $y\prec x_0$, then $y\notin X\setminus Y$, or $y\in Y$. Therefore, $S_{x_0}\subseteq Y$. By virtue of the premise, this implies that $x_0\in Y$. But $x_0\in X\setminus Y$. Contradiction.
Note that “ordinary” induction is a special case, in which $X=\mathbb N$ and $\succsim$ is the usual ordering of the naturals. If you wish to prove property $P$ for all naturals numbers, then you can set $$Y\equiv\{n\in\mathbb N\mid\text{property $P$ is true for $n$}\}$$ and check whether $S_x\subseteq Y$ implies $x\in Y$ for all $x\in X$ to conclude that $Y=X$ (that is, that property $P$ holds for all natural numbers).
(You may wonder where checking that $1\in Y$, which is usually the first step in ordinary mathematical induction, enters the picture. This is a bit subtle, but there. Note that $S_1=\varnothing\subseteq Y$, so if the premise of the principle of transfinite induction were to be true, one must have $1\in Y$.)