# When to use transfinite induction?

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 that for any finite step of this sum we get another fraction. However the infinite sum ( step at oo ) might be irrational.

So we cannot use induction till ordinal w / cardinal aleph_0 / infinity.

Similarly i ask when we are allowed ( or not allowed such as the exemple above ) to use transfinite induction.

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

-
Um... if you refer to the use of Zorn's Lemma, you can use it if you assume the axiom of choice. If you refer to "when can I use it so that it works?", well, no one can tell you precisely when the axiom of choice can prove something or not... do you have a more precise question in mind? –  Patrick Da Silva Sep 14 '12 at 17:01
Your edit makes even less sense. –  Asaf Karagila Sep 16 '12 at 16:22
Concerning your edit, it seems you are misunderstanding the definition of a series. Adding an infinite number of rationals is not well defined; what you are doing is finding the limit of a summation process. And of course, a limit of rational numbers can be irrational - otherwise the rationals would form a complete metric space. –  M Turgeon Sep 16 '12 at 16:29
This is why you are led to think that induction does not work in this case. All induction allows you to do here is to show that at the $n$-th stage (for $n$ finite) you have a rational number. Nothing else. –  M Turgeon Sep 16 '12 at 16:31

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.

-
Im not going to argue about if math is a bunch of algoritms or not , but i understand my question might be too general. So perhaps a few simple examples of when it is allowed and when not might be the insight that i need. Would you provide such examples please ? –  mick Sep 16 '12 at 19:43
@mick: Sure. However the next time I will have an access to a keyboard is tomorrow. So you will have to wait 12 hours or so... –  Asaf Karagila Sep 16 '12 at 19:57

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.

-
You are always allowed to use transfinite induction. It just might not work. –  Asaf Karagila Sep 14 '12 at 17:48
@AsafKaragila Yeah that's probably worth noting. I was just using AC as a safety blanket :) –  rschwieb Sep 14 '12 at 18:16

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.

-
Note the distinction between can and allowed. –  Asaf Karagila Sep 14 '12 at 17:49

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.

-

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

-