2

I searched related topics but did not find any clear elucidation of this distinction. Ordinary induction can only be used to show that a property holds for every finite object, say every natural number. However, in order to show that a property holds also for the limit ordinal $\omega$ (an infinite object) you will need transfinite induction. Does that sound right?

Motorhead
  • 281

1 Answers1

3

Showing that something is true for finite ordinals and also for $\omega$ does not require transfinite induction; it only requires finite induction and a proof for $\omega$. Transfinite induction is usually used to show that a statement holds for every ordinal, but I believe it may also be used to show that it holds for every ordinal less than some given one.

dfeuer
  • 9,069
  • Ah but how do you show something holds for $\omega$? Isn't $\omega$ a limit ordinal. I thought the point of t.i. is that it allows you to conclude that the property holds for $\omega$ by showing that $P(\alpha) \rightarrow P(\omega)$ for all $\alpha<\omega$ – Motorhead Dec 03 '13 at 23:20
  • @user1721431, you wrote that statement out all wrong, but let's put that aside. Transfinite induction is not a magic bullet. Transfinite induction has the same relationship to the fact that the class of all ordinals is (strongly) well-ordered as finite induction does to the fact that the natural numbers are well-ordered. Yes, most proofs by transfinite induction divide the ordinals into successor ordinals and limit ordinals (and $0$), but your proof "burden" remains the same: you must show that (cont) – dfeuer Dec 03 '13 at 23:34
  • (cont) whenever a proposition holds for all ordinals less than $\alpha$, then it holds for $\alpha$. – dfeuer Dec 03 '13 at 23:36
  • Transfinite induction is really only going to be stronger than finite induction if you want to prove something for infinitely many limit ordinals; otherwise you just have finitely many finite induction proofs and finitely many proofs for (finitely many) limit ordinals. – dfeuer Dec 03 '13 at 23:38
  • Perhaps i should have clarified, i was talking about the limit case and not the base and inductive cases which are no different from ordinary induction. Showing that along with the base and inductive cases then allows you to conclude (along with the property holding for other ordinals) that $P(\omega)$. But you still haven't explained how you can prove it just for the $\omega$ case, given that $\omega$ is a limit ordinal. – Motorhead Dec 07 '13 at 23:29
  • @user1721431, I don't really understand what you're not understanding. You do have to do extra work to show $P(\omega)$. That extra work is not called transfinite induction, unless you're doing enough extra work to prove the proposition more generally. If you prove, for example, that whenever $\lambda < \omega_3$, $\bigl((\forall \alpha < \lambda) P(\alpha))\implies P(\lambda)$, then you know that $P(\beta)$ holds for all $\beta < \omega_3$, and that is called transfinite induction. More commonly, I believe, there is no upper bound, so you're actually proving $P(\beta)$ for all $\beta$ – dfeuer Dec 07 '13 at 23:41
  • When you're only dealing with one limit ordinal, $\omega$, you're not really doing any induction beyond the finite induction you used to prove the proposition for all the natural numbers. – dfeuer Dec 07 '13 at 23:43
  • "I don't really understand what you're not understanding". you wrote "You do have to do extra work to show P(ω). That extra work is not called transfinite induction". My question is: how do you prove it for $\omega$ except by using transfinite induction? You keep repeating that the result holds for all ordinals but its really irrelevant to my question – Motorhead Dec 10 '13 at 03:42
  • @user1721431: Consider the following situation: Suppose I know something is true for all reals in $[0,1)$. Then your question is analogous to me asking "How do I prove it for $1$ except by proving it for all positive reals?" The answer is: I prove it for 1! There's a lot of reals that are not 1, and if I only care about the truth in $[0,1]$, then I don't care about all the others. – Eric Stucky Dec 10 '13 at 04:15
  • Your OP question is "Do I need transfinite induction to prove something true for $\mathbb{N}\cup{\omega}$?" And the answer is no; transfinite induction is dramatic overkill, for precisely the same reason that proving something true for $[0,\infty)$ is dramatic overkill to show it is true for $[0,1]$. – Eric Stucky Dec 10 '13 at 04:16
  • @EricStucky, the only subtlety is that in a few cases (a recent answer by Brian M. Scott regarding pairs of points on lines comes to mind) the transfinite induction may be strictly bounded by some limit ordinal (in that particular case, the least ordinal of cardinality $\mathfrak c$). – dfeuer Dec 10 '13 at 04:20
  • @EricStucky: The analogy with [0,1) vs. [0,inf) is not a good one because 1 is a real so i can presumably use whatever technique i used with the other reals < 1. Here $\omega$ is not a nat. I'm asking dfeur for a technique other than t.i. that allows him to show a property holds for $\omega$. Perhaps a better though not ideal analogy is with a sequence of numbers that approaches some limit. eg 1/2, 1/4, 1/8,.. and you're easily able to show that every number in this sequence has some property (eg is > 0) but showing that the property holds (or not) of the limit requires a special technique. – Motorhead Dec 12 '13 at 00:57
  • @user1721431: I agree my analogy is not ideal on practical grounds (although perhaps there is a good radius/interval of convergence example that could salvage it). But analogies aside, it sounds like you now understand the point dfeuer is making, which is that "a special technique" (which yes, is almost always needed for $\omega$) need not be transfinite induction, which is usually much more powerful. – Eric Stucky Dec 12 '13 at 03:04
  • @user1721431, there don't seem to be a lot of natural examples of situations where you'd want to prove such a thing using induction of any sort. Can you give an example of a proposition you'd like to prove for natural numbers and als $\omega$? – dfeuer Dec 12 '13 at 03:16
  • @EricStucky: Its not that I've ever missed dfeuer's point that he is saying there is some special technique for handling $\omega$. I just haven't been able to convince him to reveal what that might look like! – Motorhead Dec 15 '13 at 01:47
  • @dfeuer: My question was a general one, as I'm currently trying to get my head around what t.i. is useful for what its not. I am not sure i have a concrete example. Perhaps your point is that anything interesting that applies to omega applies to all the ordinals? – Motorhead Dec 15 '13 at 01:56
  • @user1721431, I suggest you check out the mathematics chat here. It may be a better place to discuss these things. – dfeuer Dec 15 '13 at 03:43