Talk:Transfinite induction

From Wikipedia, the free encyclopedia

Mathematics Portal This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating:	Start Class	High Priority	Field: Foundations, logic, and set theory
Please update this rating as the article progresses, or if the rating is inaccurate. Click to show/hide comments. Please add to or update the comments to suggest improvements to the article. Geometry guy 22:25, 17 June 2007 (UTC)

Contents 1 Redundancy? 2 Proof 3 Transfinite recursion 4 Successor Case vs Limit Case 5 Sets of ordinals??? 6 " <rα | α<c >"

[edit] Redundancy?

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 redundancy 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. —Preceding unsigned comment added by 217.232.29.149 (talk • contribs)

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

[edit] Successor Case vs Limit Case

The page says "Notice that the second and third cases are identical except for the type of ordinal considered (...)", talking about the Successor Case and Limit Case of Transfinite induction. This doesn't seem right; the cases are different because in the Limit case, the limit ordinal is not in the form β+1. I think this comment is misleading (at best), and should be removed. Any objections? --RRM 16:39, 4 April 2007 (UTC)

The similarity lies in the fact that one is allowed, in both cases, to use the property for all previous ordinals in showing it for the current ordinal. So a common proof is often possible. JRSpriggs 07:47, 5 April 2007 (UTC)

[edit] Sets of ordinals???

Ordinals form class, not set. —The preceding unsigned comment was added by 83.5.233.94 (talk) 11:05, 14 April 2007 (UTC).

The class of all ordinals is not a set. That doesn't mean there's no such thing as a set of ordinals. --Trovatore 18:33, 15 April 2007 (UTC)

[edit] " <r_α | α<c >"

What?--68.161.161.206 (talk) 11:52, 18 April 2008 (UTC)

The first and last order signs should actually be angle brackets, meaning the sequence of elements r_α indexed by α < c. — EJ (talk) 12:25, 18 April 2008 (UTC)