Principle of Transfinite Induction

Question

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!

Answer 1

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

Answer 2

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

Answer 3

A well-ordered set is a set that is linearly ordered in such a way that every non-empty subset has a smallest member.

An ordinal is essentially an order type of such a set, i.e. two such sets have the same ordinal number if and only if there is an order isomorphism between them, i.e. a one-to-one correspondence that preserves the order.

The most familiar example is the set of finite cardinal numbers: $$ 0,1,2,3,4,5,\ldots $$ Next consider this: $$ 1,2,3,4,5,\ldots,\omega, \omega+1,\omega+2,\omega+3,\ldots $$ Every member of $0,1,2,3,4,\ldots$ is less than every member of $\omega+1,\omega+2,\omega+3,\ldots\,{}$. It's not hard to see that this set is well ordered. Next $$ 1,2,3,4,5,\ldots,\omega, \omega+1,\omega+2,\omega+3,\ldots,\omega2,\omega2+1,\omega2+2,\omega2+3,\ldots $$ It is conventional to write $\omega2$ rather than $2\omega$ for reasons that you will see if you learn what is called "ordinal arithmetic".

One can continue that "forever" and then after that get $\omega^2$, then $\omega^2+1$, etc.

All of these are "ordinals" or "ordinal numbers".

And the set of all finite or countably infinite ordinals is itself an ordinal. It is well ordered.

The set of all finite or countably infinite ordinals can be shown to be uncountably infinite. It is the smallest uncountably infinite well ordered set. Its cardinality is called (by Georg Cantor and everyone following him) $\aleph_1$. The celebrated "continuum hypothesis" says no cardinality is between $\aleph_0$ and $2^{\aleph_0}$. That no cardinality is between $\aleph_0$ and $\aleph_1$, on the other hand, is provable. If the continuum hypothesis is true, that is the same as $2^{\aleph_0} = \aleph_1$. (If the axiom of choice is false and the continuum hypothesis is true, then $\aleph_1$ and $2^{\aleph_0}$ can be incomparable, i.e. unequal cardinal numbers of which neither is greater than the other.)

Answer 4

Let's ignore ordinals for a moment and remember, that a well-order is a total order $\preceq$ on some set $A$ such that every nonempty subset $B \subseteq A$ has a minimal element with respect to $\preceq$.

The principle of induction may now be formulated as follows:

Let $P(a)$ be a property that is defined for all $a \in A$. If $P(a)$ fails for some $a \in A$, then there is a $\preceq$-minimal element $a_0 \in A$ s.t. $P(a_0)$ is false, i.e.

• $P(a_0)$ is false
• for all $b \prec a_0 \colon \ P(b)$ is true

If we can show that whenever $P(b)$ is true for all $b \prec a$ it is also true for $P(a)$ (note that this implies that $P(a)$ holds for the minimum of $A$), then the above shows that there cannot be an $a \in A$ such that $P(a)$ fails. So that $P(a)$ must be true for all $a \in A$.

Michael and Clive have already written a bit about ordinals, but so far one important property hasn't been mentioned: For every well-order $(A, \preceq)$ there is a unique ordinal $\alpha$ such that $(A, \preceq)$ and $(\alpha, \subseteq)$ are order-isomorphic. Thus ordinals may be thought of as "standard representatives of well-orders".

(I suppressed that fact that the collection of all ordinals is not a set, but a proper class. In fact, the principle of induction also works in this case for pretty much the same reason...)

Answer 5

I'm adding a second answer becaue the following point is quite inteesting:

In this kind of induction, there is no need for a base case. Suppose you can prove that if $P$ is true of all predecessor of $\alpha$, then $P$ is true of $\alpha$. Then you can conclude that $P$ is true of all ordinals $\alpha$.

The reason you don't need a base case is that it's vacuously true that $P$ holds for all ordinals $<0$. You've proved that if $P$ is true of all ordinals less than $0$ then $P$ is true of $0$, simply as one special case of the induction step.

Answer 6

When these guys were inventing these formal systems, they modeled order on hierarchy. They pictured order like Russian dolls. The littlest doll is the 'smallest.' "The Ordinals" are a supposed construct which are meant to stand in for a primordial universal sense of "less than" or "greater than," and it could be posited in any type of formal theory, not just that of sets with 'inclusion' as the order symbol. The idea in this particular version is that you fall back on a ZF axiom ('there's a set that contains whatever we wish') to classify sets as having an order based on the amount of nesting they host. The definition is simply recursive: "If you are a set, your order is one greater than that of the highest order sets you contain." This is only coherent with the other ZF axiom, 'Foundation' (every chain of set membership terminates at a set which contains nothing). So the ordinals are, symmetrically, 'built' recursively - you start with the empty set and start succeeding it repeatedly. [By succession I mean you apply a set operator S(x) = {x,{x}}.. it's fun to see how this works to give both cardinality and ordinality] Hopefully you can see that the particular formalism of 'sets' is not necessary for induction, whether finite or beyond; it is the basic notion of order that is essential, of one coming after another. They are only considered 'standard' by tradition, and recent one at that. Actual orders in the universe are far more intriguing.

A weird technical point is that even though cardinality and ordinality are said to be identical for finite sets (relying on the notion that any finite set can be well-ordered 'by hand'), the theorists decided that you could still stick infinite sets in sets, so that the successor set of the naturals, for example, has an order higher than the naturals (from the above definition) yet its cardinality is identical with that of the naturals. I don't agree with them exactly, but they say this is mathematics, not philosophy. (I've never been positive of that.) For that reason, the idea that makes transfinite induction special is that it can 'break past' the border of countable cardinality (which circularly must "stop" a natural-number based induction, if we base cardinality off of bijection and take heed of what Galileo discovered about infinite correspondences). Hence 'trans.' Any "Principle" of transfinite induction can only be simply a statement of an extension of the standard 'one good turn deserves another' principle, a re-iteration of Cantor's belief in infinite transfinite cardinalities (also embodied in a ZF axiom due to Cantor and a theorem of his). Perhaps it could be stated as "all good turns deserve another." It's all a little too metaphysical for me. One should remember that Cantor believed in an absolute highest infinity, inaccessible to human minds, which he identified with the Catholic God. So the ZF axioms, from Cantor's metaphysical point of view, would actually not be absolutely true (Since there'd be no order above God's). Funny point. I can personally make no use of such a principle, but if anyone actually can, that's great. There seems to be an implicit notion that there is infinity beyond infinity, but you couldn't know, because that's the thing about infinity: you never get there. How can you go from somewhere you can't get to? The finite universe is quite enough to satisfy me. I will say that it's an interesting chapter of abstract mechanics, however.