Set Theory – Principle of Transfinite Induction

inductionordinalsset-theorytransfinite-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!

Best Answer

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$).)

Related Question