Confused about transfinite induction

Question

QUESTION: I seem to be confused about how transfinite induction is carried out. I have looked at several examples and they seem to follow a procedure consisting of grounding the induction, proving the succession case and then proving the limit case. But I still don't quite understand the point of proving the limit case, and to add to my confusion some authors seem to just prove problems requiring transfinite induction with a base case and an inductive step, completely ignoring the limit case. Could someone please provide some clarifications as well as a step by step example of the proper way of implementing transfinite induction. Thanks.

EDIT: I now see the reasoning for setting up the induction, but take a look at this proof of showing that every vector space has a basis.

Proof: Let V be a vector space. By the well-ordering theorem, there is a well-ordering of the elements of V. Therefore, there is an ordinal $\alpha$ such that the elements of $V$ can be put into one-to-one correspondence with $\alpha.$ For each $\beta<\alpha$, let us write $v_\beta$ for the element of $V$ that corresponds to $\beta.$ Now let $B$ be the set of all $v_\beta$ that do not belong to the linear span of their predecessors. It is clear that $B$ is linearly independent. It also spans, since every $v_\beta$ either belongs to $B$ or is a linear combination of earlier elements of $B$, and every element of $V$ is $v_\beta$ for some $\beta.$

Question 2:I don't see any of the distinct steps of transfinite induction in here, yet it is considered a proof by transfinite induction. Can anyone please explain why this is still considered fine, and can you indicate the limit step.

EDIT 2: It seems that Brian's response has answered both of my questions.

Answer 1

I would assume you are familiar with concept of ordinal numbers.

Fix some hypothesis $P(\alpha)$ you want to show true for all ordinals $\alpha$. Let's see how far you can get without limit case: Induction is grounded, so we know $P(0)$. By successor case, this implies $P(1)$, which implies $P(2)$, which implies $P(3)$, which... so for all finite $n$ we know $P(n)$. But the problem appears when we try to show $P(\omega)$ - it's obviously not the grounding case, and $\omega$ is not a successor ordinal. This means that we cannot show $P(\omega)$ just from knowing $P(n)$ for $n<\omega$, unless we have some rule which tells us that it suffices, i.e. if $P(\beta)$ holds for $\beta<\alpha$, then $P(\alpha)$. But this is precisely the limit case we want to use.

TL;DR: without limit case we can't show propositions for limit ordinals.

Answer 2

I’ll address your vector space example. We have $V=\{v_\beta:\beta<\alpha\}$, and we’ve defined

$$B=\big\{v_\beta\in V:v_\beta\notin\operatorname{span}\{v_\gamma:\gamma<\beta\}\big\}\;;$$

the result that we’re actually proving is that $B$ is a basis for $V$.

The first step is to show that $B$ is linearly independent. If not, there are a finite subset $\{v_{\beta_1},\ldots,v_{\beta_n}\}$ of $B$ and non-zero scalars $c_1,\ldots,c_n$ such that

$$c_1v_{\beta_1}+\ldots+c_nv_{\beta_n}=0\;.\tag{1}$$

Without loss of generality we may assume that $\beta_1<\ldots<\beta_n$. We can solve $(1)$ for $v_{\beta_n}$:

$$v_{\beta_n}=\frac{c_1}{c_n}v_{\beta_1}+\ldots+\frac{c_{n-1}}{c_n}v_{\beta_{n-1}}\;.$$

But then

$$v_{\beta_n}\in\operatorname{span}\{v_{\beta_1},\ldots,v_{\beta_{n-1}}\}\subseteq\operatorname{span}\{v_\gamma\in V:\gamma<\beta_n\}\;,$$

contradicting the definition of $B$. Thus, every finite subset of $B$ is linearly independent, and hence (by definition) so is $B$. Note that to this point we have not used induction at all.

Now we want to show that $\operatorname{span}B=V$; this is where we’ll use induction. It won’t be necessary to split the successor and limit cases, however, because the argument is exactly the same for both.

Let $\beta<\alpha$, and suppose as induction hypothesis that $v_\gamma\in\operatorname{span}B$ for every $\gamma<\beta$. If $v_\beta\in B$, then of course $v_\beta\in\operatorname{span}B$. Otherwise, $v_\beta\in\operatorname{span}\{v_\gamma\in V:\gamma<\beta\}$ by the definition of $B$. By the induction hypothesis $v_\gamma\in\operatorname{span}B$ for each $\gamma<\beta$, so

$$v_\beta\in\operatorname{span}\{v_\gamma\in V:\gamma<\beta\}\subseteq\operatorname{span}(\operatorname{span}B)=\operatorname{span}B\;.$$

In both cases we find that $v_\beta\in\operatorname{span}B$. This completes the induction step, and it follows by induction that $v_\beta\in\operatorname{span}B$ for all $\beta<\alpha$, i.e., that $\operatorname{span}B=V$.

Note that there was no need to prove base case separately: the argument that I gave already takes care of $v_0$, since it vacuously satisfies the induction hypothesis: it has no predecessors, so vacuously all of its predecessors are in the span of $B$. There was also no need to split successor and limit cases, because the same argument handles both. This is analogous to the so-called strong version of ordinary induction.

I would actually phrase this argument a little differently, in terms of least counterexample. If $\operatorname{span}B\ne V$, $\{\beta<\alpha:v_\beta\notin\operatorname{span}B\}\ne\varnothing$, so it has a least element, say $\beta$. Then $v_\gamma\in\operatorname{span}B$ for all $\gamma<\beta$, and we proceed as above to get a contradiction. Thus, $\{\beta<\alpha:v_\beta\notin\operatorname{span}B\}=\varnothing$ and therefore $\operatorname{span}B=V$.

Answer 3

Essentially, the issue is that when dealing with ordinals, you can't "reach" every ordinal using only successors. Thus the idea is: Reach all the ordinals you can with successor, then get to the next level with the limit case (ie the union case). Since, for example, $\aleph_1$ cannot be reached by starting at $0$ and just taking successors, just doing the base case and successor step of an induction argument will never tell you anything about $\aleph_1$!