When to use transfinite induction?

Question

How do we know when we are allowed to use transfinite induction in a proof?

Edit: considering the replies, I should say the following:

Consider an infinite sum of fractions.

By induction we can show that for any finite step of this sum we get another fraction. However the infinite sum (step at $\infty$) might be irrational.

So we cannot use induction till $\omega$ / $\aleph_0$ / infinity.

Similarly I ask when we are allowed (or not allowed such as in the example above) to use transfinite induction.

I appreciate the answers and they are not 'wrong' but I don't think they address this, hence the edit. My apologies for not being clear enough.

Answer 1

If you are assuming that you have the axiom of choice, then you're always allowed to use it.

You would want to use it whenever you are trying to establish that a property $P$ holds for all ordinals $\alpha$, in analogy with the ordinary induction case.

The difference is that for ordinary induction, it only works up to the ordinal number $\omega$ and no further. Transfinite induction can be applied to higher ordinals.

I remember using a lot in topology, where we would sometimes be working with large sets of sets indexed by ordinals. Transfinite induction was used to show that all the sets of the construction had a certain property.

Answer 2

You can use it whenever you have a set with a well-ordering that's well-behaved enough to do something. By well-behaved I mean that the well-ordering is related to the structure of the problem in some way.

For example, if you want to prove something about Borel sets, you may notice that they naturally consist of the classes $\Sigma^0_\alpha,\Pi^0_\alpha$, $\alpha<\omega_1$, so you can prove many a theorem about Borel sets inductively, using this structure.

On the other hand, assuming axiom of choice, you can find a well-ordering of any set, but a priori this well-ordering might be very badly behaved, so it may not be prudent to use it in a proof. In other cases, it might be, for example when showing the existence of a Bernstein set of real numbers.

Answer 3

You are always allowed to use transfinite induction in your proofs.

There is a problem, however, that sometimes the limit stages require the axiom of choice to hold.

The transfinite induction argument simply says something like induction, only general: suppose that you walked over all ordinals until $\alpha$, how do you plan on stepping through $\alpha$?

In the "usual" induction we usually just define the next step, or show that our idea is well-defined. It is commonly just as simple for successor ordinal steps in transfinite induction. However it is often the case that there is no well-defined solution for the limit ordinal. When something like this happens we must use the axiom of choice to help us show that there exists a well-defined solution for this problem.

Regardless to that, however, we may use transfinite induction whenever we would like. The question should have been phrased when can we use it, and the answer to that is whenever you are able to show a well-defined step for every ordinal. Sometimes it is constructive and other times it requires the axiom of choice. To such a general question there is no particularly pinpointed answer.

---

To the edit:

I think that you want to ask when in regular mathematics (i.e. not set theory) the induction follows to the limit case, that is "to the infinite step". The answer is, again, in its general form "when it can".

Sometimes it is possible and sometimes it is not possible. However distinguishing between those two cases requires a lot of training and usually a deep understanding of how the mathematical objects in question behave.

Again, if you wish to present a particular case then it can be explained further why and when it is possible to go beyond the finite steps; however just asking for a general explanation won't work.

Mathematics is not a bunch of algorithm and rules, it is a sea of definitions in which we swim constantly, and to wade between those definitions one has to have insights.

Answer 4

The idea of induction is to prove something by exhausting all the elements.

So let $P$ be some property. For regular induction on $\omega$, showing for $0$ and proving that if it holds for $n$ is capable of exhausting the entire set $\omega$ since it has no "limiting element".

Transfinite induction is using this sort proof idea on arbitrary sets. You want to list all the element of an arbitrary set in a way so that you can prove a property holds for the whole set by going through them one by one, just like for induction on $\omega$.

To make this all work out property, this sort of listing out is to give the arbitrary set a well-ordering. Now suppose that $(X, <)$ is a well ordering of $X$. Let $0$ denote the least element of $X$. If $P$ is a property, then transfinite induction states that if

1. $P(0)$ holds

2. $(\forall x)(\forall a \leq x)(P(a) \Rightarrow P(x))$

Here 2. means for all $x$, if $P$ holds for all $a$ less than $x$, then $P$ holds on $x$ as well.

You can try to prove a property holds for an arbitrary set by transfinite induction as long as you have a well-ordering of $X$. Every set has a well-ordering is equivalent to the axiom of choice. So if you foundation of mathematics has the axiom of choice then you can try to prove something by transfinite induction. Of course, whether this type of proof will work is contingent on you being able to verify 1. and 2. The axiom of choice gives you an arbitrary well ordering which may not reflect any the original structure of the set. For example, the well-ordering of $\mathbb{R}$ may not have any relation to the natural linearly ordering on $\mathbb{R}$. Hence proving a property $P$ holds using transfinite induction may not be easy.

Answer 5

Whenever you want to prove something about all ordinals, I suggest that transfinite induction is not only allowed but likely the method of choice. If you try with some other set that has a natural well-ordering, then it will work there too (as it is essentially also just a proof with ordinals).

Others have suggested that the Axiom of Choice guarantees the existence of a well-ordering of any given set and hence induction could be used anywhere, but this bears problems: If the theorem to be proved is valid also in the absence of AC, then induction is likely not simpler than a direct proof and the induction step is in fact almost a direct proof. If on the other hand the theorem is no longer valid if one drops AC, then one of the "usual suspect" like Zorn's lemma is likely a much better tool than transfinite induction (actually, it is wrapped up in Zorn's lemma). In summar, if there is no natural well-order, you should leave transfinite induction in your toolbox. (Then again: you are of course allowed to use it).