2
$\begingroup$

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.

$\endgroup$

3 Answers 3

5
$\begingroup$

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.

$\endgroup$
4
  • 2
    $\begingroup$ That depends entirely on the form of the proposition that one is proving. In many cases it is entirely possible to show that if $P(\xi)$ holds for all $\xi<\eta$, then $P(\eta)$ also holds. In such cases the induction can often be cast in the following form: suppose that $\eta$ is the least ordinal for which $P(\eta)$ fails, and get a contradiction. In such cases there is no need to deal separately with successor and limit ordinals. For other propositions, of course, such a separation is necessary. $\endgroup$ Commented Dec 6, 2014 at 21:40
  • $\begingroup$ "...it is entirely possible to show that if $P(\xi)$ holds for all $\xi<\eta$, then $P(\eta)$ also holds" - this is exactly showing that limit case of transfinite induction holds. I'm not denying that it can be shown as theorem, I'm just showing how limited we would be if we did not have (e.g. we didn't prove) limit case. $\endgroup$
    – Wojowu
    Commented Dec 6, 2014 at 21:50
  • 2
    $\begingroup$ I think that you’re missing my point: in many transfinite inductions there is no need to split the induction step into successor and limit cases. Part of the OP’s confusion appears to stem from the fact that sometimes the split is made, and sometimes it is not. $\endgroup$ Commented Dec 6, 2014 at 21:55
  • $\begingroup$ Thanks for the clarifications. And yes my original confusion was about the necessity of the split. It seems that some proofs requiring transfinite induction merely require more-or-less the steps carried out in another induction(so long as were messing with ordinal numbers), but for the most part a split is probably needed to complete the proof. $\endgroup$
    – Enigma
    Commented Dec 6, 2014 at 22:28
2
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ I don't think you need transfinite induction or anything like it to prove that $B$ spans $V$. Given any vector in $V$, it is $v_\beta$ for some $\beta$. Either it's a linear combination of earlier elements of $B$, in which case it's a linear combination of $B$, or it's an element of $B$, in which case it's again (trivially) a linear combination of $B$. $\endgroup$ Commented Dec 6, 2014 at 23:13
  • $\begingroup$ @Andreas: It’s trivial, but technically you need an induction to establish that either-or. What you actually know from the definition of $B$ is that either it’s an element of $B$, or it’s a linear combination of earlier elements of $V$ (not $B$). $\endgroup$ Commented Dec 6, 2014 at 23:16
  • $\begingroup$ In the definition of $B$, the phrase "linear span of their predecessors" is ambiguous. I took it to refer to predecessors in $B$, in which case the definition of $B$ uses transfinite induction but the proof that it spans does not. You (apparently) took it to mean predecessors in $V$, in which case the definition of $B$ doesn't need induction but the proof that it spans does. $\endgroup$ Commented Dec 7, 2014 at 19:10
  • $\begingroup$ @Andreas: Agreed. I chose that interpretation because the proof was said to have been presented as an example of transfinite induction, so I wanted to explain it on that basis. (I also consider induction slightly simpler than recursion.) $\endgroup$ Commented Dec 7, 2014 at 20:02
2
$\begingroup$

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$!

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .