Talk:Transfinite induction

From Wikipedia, the free encyclopedia

A needless redundancy may be here. Suppose we show that for any ordinal b, for all ordinals a < b, P(a) is true. Then it is not necessary to prove separately that P(the first ordinal) is true, because a special case of the induction step is that if P(a) is true for all ordinals a less than the smallest ordinal, then P(the smallest ordinal) is true. And it is vacuously true that P(a) is true for all ordinals a less than the smallest ordinal! Michael Hardy 00:41 Mar 3, 2003 (UTC)

So it now reads "If P(a) follows from the truth of P(b) for all a < b, then it is simply a special case to say that P(0) is true, since it is vacuously true that P(b) holds for all b < 0."... Don't we mean to say "b < a" in the first part of the sentence? A5 20:45 8 Jun 2003 (UTC)

I've now reversed the order of a and b, so that it says "If P(b) follows from the truth of P(a) for all a < b, then it is simply a special case to say that P(0) is true, since it is vacuously true that P(b) holds for all b < 0." Michael Hardy 21:34 8 Jun 2003 (UTC)

This is not the case. Suppose you have the sequence {1, 0, 0, 0, ...} and the proposition P(n) that the series sum after n is S(n) = 0. Assuming S(k)=0 gives S(k+1)=0, but S(0) = 1 so P(0) is false. This is still a valid example if you correct the S(k) and S(k+1) terms for transfinite scenarios.

The redunancy you're seeing is that the induction step assumes P(0) is true as well as all other b < a. You still have to prove it to be so.

As such I've deleted the paragraph. Mark Hurd 20:11, 3 Nov 2004 (UTC)

Sorry.Michael has correctly reverted my edit, because I was reading this explanation as P(0) is proved by assuming P(b) for all b < 0. IOW I saw it saying P(0) was vacuously true. Mark Hurd 10:03, 4 Nov 2004 (UTC)

This may seem silly to others, but upon reading, I noticed in the proof that the indexing set is integers. Perhaps this condition on α,β should be stated earlier. Based on the name of the page, I was complacent assuming that those were elements of an arbitrary indexing set, but if so, P(β+1) is useless. ub3rm4th 00:37, 3 May 2006 (UTC)

Not quite; see Ordinal arithmetic. The article does say "ordinal" all over the place; do you think it should be emphasized? Melchoir 00:42, 3 May 2006 (UTC)

"Suppose whenever for all α < β, P (α) is true, then P (β) is also true." Should this instead read "Suppose that for all ordinals α and β satisfying α < β, then P (α) is true implies P (β) is also true." ? It's standard to note where variables are taken from before their first use, not after.

Well, fit it! Melchoir 05:26, 7 May 2006 (UTC)

[edit] proof

We should add a proof for the transfinite induction principle here. indirect proof: Suppose we have proved the crucial step P(m<n [meaning for all m smaller than n])=> P(n) as well an P(x) for all minimal elements (for ordinals it would be 1). Now suppose there existed an N for which P(N) does not hold. Since we have proved P(m<N)=>P(N) there must exist an M<N for which P does not hold. The same argument can be applied to M and so on; we have an infinite descending chain (it is infinite because it never reaches the minimal elements- P is true for them [P(0) for the ordinals]). And that contradicts our well-founding.

[edit] Transfinite recursion

Currently, transfinite recursion is a redirect here. That's not necessarily bad. But if it's to stay that way, then the page really ought to say something about transfinite recursion (a method of definition, not of proof). --Trovatore 01:51, 16 July 2005 (UTC)

First cut in place. Could use an example or two, and possibly some a more rigorous treatment in addition to (not instead of) the informal descriptions given. --Trovatore 07:03, 16 July 2005 (UTC)