Talk:Transfinite induction

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)

Isn't there some redundancy in the first two paragraphs of Transfinite Induction? The same thing being said ie. chimpionspeak 02:26, 9 March 2010

To chimpionspeak: Yes, the redundancy is clearly indicated by the use of "That is,". It is intentional. The concept is hard to render in English and we felt that expressing it in two different ways would give the reader a better chance of understanding it. JRSpriggs (talk) 08:34, 10 March 2010 (UTC)

Okay. I thought that it didn't add anything because the first sentence of the second paragraph and the second sentence of the first paragraph are the same. chimpionspeak 00:23, 12 March 2010

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)

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)

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)

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)

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

Regarding Relationship to the axiom of choice

I think I understand the section. However, I have two questions.

1.) Does one need ordinals at all to define transfinite recursion/induction in ZF? Well-ordering should be enough. Iv'e seen it done without ordinals. (Yes, in that horrible Halmos book since you ask;) Is that enough to make the article belong to the Set Theory category as well. Perhaps not, looks like double work unless ordinals are allowed in Set Theory Category?

2.) If one lives completely i ZF (and ZF only) suddenly want the luxory of having transfinite recursion/induction available for ALL sets, the one would have to add to ZF AC making it ZFC so that within ZFC (only) AC actually is required if transfinite recursion/induction available for all sets? I. e. one must have those magic words "Well-order!"? YohanN7 (talk) 20:24, 16 July 2009 (UTC)

1) One needs neither ordinals nor well-ordering; well-founded relations are enough, as described in that article. You seem to misunderstand how Wikipedia categories work. Since Category:Ordinal numbers is a subcategory of Category:Set theory, any article in the former is implicitly also in the latter. An article should not be explicitly included simultaneously in a category and one of its ancestors. I have no idea what do you mean by "looks like double work unless ordinals are allowed in Set Theory Category".

2) I have no idea what do you mean by "transfinite recursion/induction available for all sets" either. Transfinite induction has nothing to do with the axiom of choice, whether you do it for ordinals or for well-founded relations. For example, ∈-induction applies to all sets, and it does not need the axiom of choice, only the axiom of foundation. You cannot do induction (in the form discussed here) for anything other than well-founded relations, as transfinite induction over a relation R implies that R is well-founded. — Emil J. 10:28, 17 July 2009 (UTC)

Transfinite induction has nothing to do, formally speaking, with the axiom of choice. In practice, though, the arguments for which you want to use transfinite induction, will generally require AC. In particular, one frequently wants to exhaust all the elements of some set, one at a time, in an inductive process. I think that's what Yohan was getting at with the "available for all sets" phrase. --Trovatore (talk) 21:34, 17 July 2009 (UTC)

Thanks for the replies. They were accurate albiet Emils was a bit ironic in places. Both the present article and well-founded relation do however seem to reserve the phrase transfinite induction for induction on well-ordered sets, in particular ordinals or some set indexed by ordinals. In fact, the present article states in the very first scentence that Transfinite induction is an extension of mathematical induction to well-ordered sets.... YohanN7 (talk) 06:18, 19 July 2009 (UTC)

Umm, right, that's a point. Emil is certainly correct that you can do induction on any wellfounded relation, and you're correct that it isn't described as transfinite induction in this article.

The question is, should it be? This is a point of usage rather than mathematics. My linguistic intuition here is that induction on a wellfounded relation other than a linear order is not standardly described as transfinite induction. --Trovatore (talk) 07:39, 19 July 2009 (UTC)

I did a quick "Google" on transfinite induction. It seems that either ordinals or well-ordering IS assumed. Of course it's technically correct that a well-founded relation is sufficient to do induction as Emil and you pointed out. In well-founded relation the name noetherian induction is mentioned for the general case of a well-founded relation. This seems to be the case when I search the net as well. Best thing might be to create a new page called Noetherian Induction and move the induction/recursion material from well-founded relation to the new page. At any rate, if one does not know (like I didn't) that induction/recursion works if [and only if?] one has a well-founded relation then that page isn't the most natural place to search for an answer. YohanN7 (talk) 08:06, 19 July 2009 (UTC)

What I meant is that the concept of transfinite induction generalizes to well-founded relations. The name does not, "transfinite induction" is indeed only used for ordinals. The general concept is known as "well-founded induction", see e.g. [1]. Note that we already have well-founded induction as a redirect to well-founded relation; I do not see any need to create a separate article, it's adequately covered there. Some folk call well-founded relations "Noetherian", but a quick search confirms that "Noetherian induction" is by an order of magnitude less common than "well-founded induction", and I frankly despise the name. Anyway, Noetherian induction also redirects to well-founded relation. For good measure, I created redirects well-founded recursion and Noetherian recursion, too. — Emil J. 10:27, 20 July 2009 (UTC)

How about this for a start: The passage

"... More generally, one can define objects by transfinite recursion on any well-founded relation R. (R need not even be a set; it can be a proper class, provided it is a set-like relation; that is, for any x, the collection of all y such that y R x must be a set.)

Relationship to the axiom of choice

There is a popular misconception that transfinite induction, or transfinite recursion, or both, require the axiom of choice (AC). This is incorrect. Transfinite induction can be applied to any wellordered set. However, frequently proofs or constructions using transfinite induction also use the axiom of choice to wellorder a set. ..."

is changed to

"... Relationship to the axiom of choice

There is a popular misconception that induction, or recursion, or both, require the axiom of choice (AC). This is incorrect. One can use induction to prove things and one can define objects by recursion on any well-founded relation R. (R need not even be a set; it can be a proper class, provided it is a set-like relation; that is, for any x, the collection of all y such that y R x must be a set.) However, frequently proofs or constructions using induction and recursion also use the axiom of choice to wellorder a set in order to be able to use the simple prescriptions given in this article. ..."

That puts the spotlight a bit more on what the issue is. Also, the question of what the standard terminology is is temporarily avoided. YohanN7 (talk) 11:05, 19 July 2009 (UTC)

Now wait a minute. I may be halfway off the wall. Take the case of recursion. Why the heck shouldn't definition by transfinite recursion - as described in the article - yield a perfectly valid function f:O->X where O is (a subset of) the ordinals - the point being that O has a well-founded relation (the wellorder in this case) and X is quite arbitrary. An example is the standard definition of the Borel sets which yield an ordinal sequence into the powerset of the reals. Proof by induction seems to be a different matter since there we must exhaust the set X in a one-to-one manner. That cannot be done with the prescription in the article unless one in fact wellorders X - or X is wellordered as comes. I need to sleep. YohanN7 (talk) 15:31, 19 July 2009 (UTC)

OkOk redirects are fine with me, though not perfect. I STILL argue that the present article is misleading. —Preceding unsigned comment added by YohanN7 (talk • contribs) 21:01, 21 July 2009 (UTC)

The tone of that section of the article is not very good anyway, which may be why you see it as "misleading". I will replace it with part of your text. — Carl (CBM · talk) 04:01, 22 July 2009 (UTC)

How about minimal element?

Let P(α) be a property defined for all ordinals α. Suppose that whenever P(β) is true for all β < α, then P(α) is also true. Then transfinite induction tells us that P is true for all ordinals. That is, if P(α) is true whenever P(β) is true for all β < α, then P(α) is true for all α. Or, more practically: in order to prove a property P for all ordinals α, one can assume that it is already known for all smaller β < α.

But induction is valid only if the property P(α) is true for minimal element: α=0. I quess it should be mentioned. Eugepros (talk) 06:58, 10 August 2010 (UTC)

If there are no smaller elements, then they all satisfy P vacuously. Thus you get P(0) from nothing and the induction begins. JRSpriggs (talk) 07:20, 10 August 2010 (UTC)

Cases

All of the three cases—the zero case, the successor case, and the limit case—are cases of proving that if something is true of every ordinal in some initial segment of the ordered class of ordinals, then it is true of the smallest strict upper bound of the set.

I see an anonymous editor saying the zero case is a special case of the limit case. If the limit case is regarded as the case where the smallest strict upper bound is the same as the smallest (weak) upper bound, then the anonymous editor is right. (Of course, there may still be practical reasons why the zero case must be treated separately from other limit cases in particular proofs.) Michael Hardy (talk) 19:05, 15 January 2011 (UTC)

OK, so first of all, in the state in which the anon left the article, it claimed that the induction could be done at limit ordinals only. That was clearly nonsense. It's possible that it was an editing mistake.

If we take the view that it was an editing mistake, then what we have is someone who has noticed that we can formally state transfinite induction in the form, if

$\forall \alpha (\forall \beta <\alpha P(\beta ))\implies P(\alpha )$

then

$\forall \alpha P(\alpha )$

This is true, formally, we can indeed state it like that. But it's not the way proofs by transfinite induction actually go, basically ever. In virtually all nontrivial cases we end up distinguishing at least the three cases mentioned (base, successor ordinal, limit ordinal). Many times those break up into further cases (a common one is to need to distinguish between limit ordinals of cofinality ω and all other limit ordinals). --Trovatore (talk) 20:45, 15 January 2011 (UTC)

I think maybe some serious concrete examples would help. Michael Hardy (talk) 05:08, 16 January 2011 (UTC)

Yes, I have one in mind. It'll take a bit of energy to write it up though. I'll see if I can get motivated. --Trovatore (talk) 05:12, 16 January 2011 (UTC)

Maybe the article should explicitly comment on the form seemingly suggested by the bare statement that if

$\forall \alpha (\forall \beta <\alpha P(\beta ))\implies P(\alpha )$

then

$\forall \alpha P(\alpha )$

and the form of proofs in actual practice. Michael Hardy (talk) 19:24, 16 January 2011 (UTC)

I think that the better placement of the parentheses is

$\forall \alpha (\forall \beta <\alpha \,P(\beta )\implies P(\alpha ))$

because it makes clear that the quantifier over alpha should be applied to the whole implication, not just its hypothesis. That the quantifier over beta is limited to the hypothesis I would assume due to unary operators (negation and quantifiers) taking priority over binary operators (implication, conjunction, disjunction, and equivalence). JRSpriggs (talk) 21:50, 16 January 2011 (UTC)

The difficulty of translating verbal statements of Transfinite Induction into symbolic logic indicates how readers can easily be confused by versions of Transfinite Induction that do not treat the $P(0)$ case separately. I take that in above discussion the expression $\forall \beta <\alpha P(\beta )$ is regarded as being equivalent to $\forall \beta ((\beta <\alpha )\implies P(\beta ))$. For the sake if the general reader, it would be useful to explain that a statement of Transfinite Induction that does not include the $P(0)$ case explcitly intends the "induction hypothesis" be ::$\forall \beta ((\beta <\alpha \implies P(\beta ))\implies P(\alpha )$.

216.223.227.93 (talk) 17:30, 26 April 2013 (UTC)

(I edited my above comment) Tashiro (talk) 17:50, 26 April 2013 (UTC)

well-ordered vs. ordinals

The lead section talks about well-ordered sets, the rest of the article about ordinals. That is not nice. — Preceding unsigned comment added by 24.85.86.45 (talk) 04:55, 23 October 2011 (UTC)

Ordinals are the archetypical well-ordered sets. Every well-ordered set is order-isomorphic to an ordinal, and ordinals are well-ordered sets. So there should be no problem. JRSpriggs (talk) 10:23, 23 October 2011 (UTC)

0 is a limit ordinal

Trovatore: This is a true statement, and it's something people might want to know. You also agreed with my claim that 0 can almost always be treated the same way as limit ordinals in proofs. So why did you remove from the page? Thehotelambush (talk) 00:39, 8 December 2011 (UTC)

0 is not a limit ordinal. JRSpriggs (talk) 00:48, 8 December 2011 (UTC)

A limit ordinal is an ordinal such that it is the supremum of all ordinals preceding it. The article on limit ordinals mentions that this definition is sometimes used, and this is the more elegant definition. Anyways, I really don't care if you disagree; my point was only to mention that 0 can usually be treated exactly the same way as limit ordinals in proofs using transfinite induction (which incidentally demonstrates why this definition is more elegant). You agreed with this. So why did you remove it? Thehotelambush (talk) 00:58, 8 December 2011 (UTC)

Whether 0 is or is not a limit ordinal (like whether 0 is a natural number or whether finite sets are countable) is one of these points of terminology that people tend to get very exercised about, but on which there is no general agreement.

It is true that, formally, you can always treat 0 with the limit ordinals, and for that matter you can always treat all the ordinals together. That's kind of trivial, because all it really means is that, when you have a finite number of fixed cases, you can always combine them into a single function or predicate. Instead of saying I start with X_0, apply f to X_alpha to get X_{alpha+1}, and apply g to the sequence of all X's below lambda when lambda is limit to get X_lambda, I can always say you apply h to the sequence of all X's below X_alpha to get X_alpha, where h of the empty sequence is X_0, h of a sequence with a last element is f of the last element, and h of a sequence without a last element is g of that sequence.

But this is usually a fairly silly thing to do, which is why in practice no one ever does it, for nontrivial arguments. It's misleading to plop it in neutrally as though it were a reasonable thing to do, which it almost never is. --Trovatore (talk) 00:58, 8 December 2011 (UTC)

It is not silly, it makes proofs more concise and more elegant, and is almost always a reasonable thing to do. So much so that I can't even recall whether any proofs have necessitated treating it separately. Some readers may be interested in the benefits of this approach, even if you are not.

"for that matter you can always treat all the ordinals together." Now you're just being pedantic, you understand perfectly well what I'm getting at. Thehotelambush (talk) 01:10, 8 December 2011 (UTC)

Let's take a concrete example. Probably the simplest nontrivial proof that goes by transfinite induction is the proof of the Cantor–Bendixson theorem. You have a closed set of reals X, and you want to show that it's the disjoint union of a perfect set and a countable set.

In the inductive proof, you iteratively apply the operation of removing all isolated points. So X₀ is X, X₁ is X₀ with all isolated points deleted, and so on. At limit ordinals you take intersections.

You argue that this process must terminate at some countable ordinal, and then recover the countable set as the union of the points deleted along the way.

Now, can you unify the treatment of 0 with the treatment of the limit ordinals? Sure. Instead of "take intersections", you say "take the intersection of everything that has gone before, and intersect that with X".

But this is artificial. Why intersect with X? The only reason is to make the base case look formally like the limit step. But the base case is different from the limit step, as anyone can see. --Trovatore (talk) 01:17, 8 December 2011 (UTC)

"as anyone can see" -- weasel words that I don't agree with. I don't care whether you think it's artificial, the point of WP:NPOV is to represent all viewpoints fairly, not to force one particular one on readers. I don't ask that you accept my POV, only that it is represented in the article and not simply removed because someone dislikes it. (And by the way, the concept of empty intersection is a clear, natural, and necessary one when taken from the point of view of limits in category theory.) Thehotelambush (talk) 01:27, 8 December 2011 (UTC)

I'm not arguing with the concept of empty intersection. The artificialness comes in intersecting with X. Why would you do that? There is no reason, except to make the cases look formally the same.

It is simply not correct to say that it is "usually not necessary" to treat 0 differently, unless you mean in the trivial sense I alluded to earlier, which is already dealt with in the text. --Trovatore (talk) 01:31, 8 December 2011 (UTC)

It is not arbitrary; X is the ambient space and one is considering subobjects (subsets) of X. Intersection is a limit in the powerset of X.

2nd point - Since that's a statement that can't really be cited in either direction, how about we say instead "0 is sometimes considered a limit ordinal and is then treated in proofs similarly as limit ordinals when possible". And, I would be VERY interested to see a proof where it cannot be treated the same way as a limit ordinal (in a suitable elegant way, by using empty intersections or whatnot). Thehotelambush (talk) 01:46, 8 December 2011 (UTC)

Please see Wikipedia talk:WikiProject Mathematics/Archive/2011/Sep#What is a limit ordinal?. JRSpriggs (talk) 02:01, 8 December 2011 (UTC)

Given that the other article at least mentions the alternative definition, I will add the more neutral sentence into the article. Thehotelambush (talk) 02:13, 8 December 2011 (UTC)

I object strongly to the assertion that 0 is "treated similarly when possible". No one strains to treat 0 the same as nonzero limit ordinals in actual practice, and there is no good reason to. I think you're trying to impose a normative aesthetic that you would like to see followed, but where actual workers in the field simply don't agree with you. --Trovatore (talk) 03:06, 8 December 2011 (UTC)

YOU are imposing a normative aesthetic when you say "no one" does this, and when you claim that your way is the only way worth describing in the article. If one treats zero as a limit ordinal (as many do), then there is no reason to treat it differently, as I have demonstrated above. I do not claim that this is even common practice, but it's ridiculous to exclude it simply because it's a minority viewpoint. Thehotelambush (talk) 04:12, 8 December 2011 (UTC)

I am not trying to add to the article a claim that no one does it in practice, although it is the truth in nontrivial cases. You have demonstrated no such thing. What you have done is make an ad-hoc argument that, in retrospect, you can fit the form of the proof into your Procrustean mold. But this proof is still pretty trivial. I'd like to see what you'd do to, say, the proof of the comparison lemma, where your base step starts with two mice.

In practice, most arguments start with some arbitrary, complicated object as the base case. It's a given thing, coming from the hypotheses assumed for the theorem. It's usually only in the base step that it's useful to mention it, not in nonzero limit steps, and this makes the base step different. --Trovatore (talk) 04:21, 8 December 2011 (UTC)

I'm not familiar with the comparison lemma, if you can provide a proof for it I will gladly examine it. "I am not trying to add to the article a claim that no one does it in practice, although it is the truth in nontrivial cases." ok, so you admit your argument is based on a false claim (while dismissing mathematicians with whom you are unfamiliar, such as myself, as "trivial".). I am not making an ad hoc argument as, in my experience, virtually all proofs by transfinite induction/recursion are simpler and more concise given this treatment, but clearly your experience is different (given a limited understanding of empty intersections). Thehotelambush (talk) 04:39, 8 December 2011 (UTC)

What "limited experience of empty intersections"? I never objected to empty intersections.

The text you added was, Zero is sometimes considered a limit ordinal and is then treated in proofs in the same case as limit ordinals when possible.. The first part of that is true; zero is indeed sometimes considered a limit ordinal. The second part is just false. Yes, some arguments are presented this way, but it is not the usual treatment, even when "possible". --Trovatore (talk) 04:50, 8 December 2011 (UTC)

I've changed the wording to be more neutral. Thehotelambush (talk) 04:57, 8 December 2011 (UTC)

OK, that's acceptable. --Trovatore (talk) 05:06, 8 December 2011 (UTC)

Thanks, I'm glad we worked this out. Thehotelambush (talk) 05:10, 8 December 2011 (UTC)

Unlike all limit ordinals, zero belongs to an open set, namely {0}, which contains no other ordinal. JRSpriggs (talk) 14:18, 8 December 2011 (UTC)

Vitali set example problematic?

The example states that choice is only used to well-order the reals. But the actual "construction" doesn't seem a real "construction". Specifically, the claim to be able to just "countinue; at each step" to chose uncountably often does not seem well-defined at all. Of course it is possible to clearly state this process in a formally correct way, but then it won't demonstrate what is meant to be demonstrated here. 217.84.235.60 (talk) 22:50, 11 January 2012 (UTC)

I am not sure I understand the objection. As far as I can tell, once the original wellorder is chosen, after that everything is completely well-specified and constructive; at each step you choose the least possible element of the equivalence class, "least" being understood in the sense of the chosen wellorder. Are you claiming that the iteration as stated can proceed in two different ways, even given the same wellorder? I think that that is not true. --Trovatore (talk) 23:28, 11 January 2012 (UTC)

To clarify a bit: The reason this example is in the article about transfinite induction is, presumably, to demonstrate it in use. But precisely this use is totally obscured in "chose at each step". For the reader who is not clear on what transfinite induction is, its use in that example is not at all obvious. More dangerously, these matters need very precise attention especially when in a learning stage. But looking anywhere in the article, nowhere is "chose something" uncountably often mentioned - instead, either a restriction of a class function (no strict classes mentioned here), or a version with precise steps to follow regarding the treatment of successor and limit ordinals. Neither of those appear anywhere either. I would think that any example on this page should take great care to be exact and rigorous in its use of mathematical terms, and this section is anything but.217.84.235.60 (talk) 05:03, 12 January 2012 (UTC)

I still don't follow you. Is your objection that what happens at each step is not actually "choosing", because it's pre-determined by the chosen wellorder? Would you be happier if the word choose were replaced by take or some such? As for proper classes, there are none in sight, so I don't see the point of mentioning them. --Trovatore (talk) 05:11, 12 January 2012 (UTC)

Maybe what you're really looking for is some sort of explanation as to how to turn the argument into a formal deduction from ZFC or something? In that case I completely disagree. The important thing to get across here is what's really going on, "naively" or "Platonistically" if you will, and what's really going on is an uncountable sequence of discrete steps. There is nothing ill-specified about it; it's completely canonical. The details of how to create a formal ZFC argument are less canonical, and also less interesting. --Trovatore (talk) 06:30, 12 January 2012 (UTC)

This last bit is a bit closer, but not fully. I don't mean a formal deduction from ZFC - that'd certainly be far over the top. But a somewhat more formal deduction from the principles actually laid out in the paragraph above is what I'd expect to see, or at least hinting at it. The transition from having functions G as used in the above explanation to "doing something in steps" is what is needed to really "understand" transfinite induction, yet it is - for the most likely reader of this page, i.e. someone not yet familiar with how these things work - not trivial. Adding something like "so we have G defined as ... and then we apply the principles outlayed above" would help. To be clear: I'm not disputing the correctness of the statements there. I just don't think the example is particularly serving its purpose of showing where AoC is used and where the transfinite induction happens (and that AoC is not used there any more).217.84.242.179 (talk) 16:10, 12 January 2012 (UTC)

Actually, a fine example of what I'd expect to be explained is here: http://en.wikipedia.org/wiki/Ordinal_number#Transfinite_induction - that the main page has a less clear description of what's going on in the only example given is what I was trying to point out. — Preceding unsigned comment added by 217.84.234.165 (talk) 21:53, 14 January 2012 (UTC)

Too {{technical}}: missing prerequisites in section on transfinite recursion

This section is not self-contained. I'm marking it as {{technical}}.

• What's a class function? I don't guess it's class function, since the latter has to do with group theory (though of course one never knows).
• What's $\upharpoonright$? From https://en.wikipedia.org/wiki/Transfinite_sequence#Successor_and_limit_ordinals, I'd guess it's some limit operation. However, V is not restricted to be ordered. (In http://planetmath.org/transfiniterecursion, V is the class of all sets, but then this article should mention it as well). From http://www.proofwiki.org/wiki/Transfinite_Recursion/Theorem_1, I see it's a restriction.
• I can guess what's "transfinite sequence", but the link points to the following definition:

If α is a limit ordinal and X is a set, an α-indexed sequence of elements of X is a function from α to X. This concept, a transfinite sequence or ordinal-indexed sequence, is a generalization of the concept of a sequence. An ordinary sequence corresponds to the case α = ω.

But this definition can't be used here (I think), since the index set is the whole Ord.

(BTW, this seems to overlap with https://en.wikipedia.org/wiki/Transfinite_sequence#Transfinite_induction, which has a better discussion of the concepts apparently, though it fails to provide enough definitions). --Blaisorblade (talk) 13:20, 16 October 2013 (UTC)

As in most parts of mathematics, there are certain things you have to know before you start. If you do not know them, then you will not be able to understand the subject at all.

• Usually, a function is assumed to have a domain which is a set. A class function is something which is defined like a function but may have a class for its domain. So every function is a class function, but some class functions are not functions because their domains are proper classes.
• In this context, the harpoon $\upharpoonright$ means that the domain of the function on the left of the harpoon is restricted to the class to the right of the harpoon. That is

$F\upharpoonright C=\{\langle x,y\rangle \,\vert \,\langle x,y\rangle \in F\land x\in C\}\,.$

• In this case the function may actually be a class function.

If you think you can explain things better, then please be my guest and edit the article. But please make small localized changes and wait for a few days to see whether others make corrections or reversion before continuing. JRSpriggs (talk) 15:19, 16 October 2013 (UTC)

This seems not true. The symbol $\upharpoonright$ is not the sole standard denotation for the restriction of functions (cf. http://en.wikipedia.org/wiki/Restriction_%28mathematics%29 ), so its meaning should be precised. Moreover, the type of G is wrong. Without fixing it V stands for any class. Thus the type V → V says that G may be even an empty function, what is surely wrong. Shouldn't V be, for example, the class of all sets? — K. 2014-02-25 — Preceding unsigned comment added by 79.184.244.27 (talk) 13:14, 25 February 2014 (UTC)

That some people use other symbols for restriction of a function does not change the fact that the harpoon is used for that purpose in this article (and in many papers on set theory).

"V" is used for the class of all sets here. There are no types in ZFC set theory, so I do not understand what you mean when you say "the type of G is wrong". JRSpriggs (talk) 08:25, 26 February 2014 (UTC)

Where is written that "V" is used for the class of all sets here? If you do not write this, the standard convention says that V is quantified universally. In other words the standard semantics of "Given a class function G: V → V" is "Let V be any class and G by any class function of the type V → V".

Going back to the harpoon. You probably haven't written science papers, so let me explain. If you write a paper, you do it for others, not for your self. So you should care about making it understandable for all readers. In a situation when you are using some notation that is not a total standard, it is in good taste to give a note about what this notation means. (cf. Theorem 1 at this page http://planetmath.org/transfiniterecursion ) K. 2014-02-27 — Preceding unsigned comment added by 79.186.221.235 (talk) 09:45, 27 February 2014 (UTC)

This is not a paper by me. It is the result of contributions by dozens of people. If you see something wrong, YOU should fix it. Do not tell me to fix it. JRSpriggs (talk) 10:50, 27 February 2014 (UTC)

I defined V and the harpoon. Even though it's apparently becoming more common, I'd never seen the harpoon. And being explicitly told that G is a function on sets (by defining V) would've saved me some puzzlement.

173.25.54.191 (talk) 06:00, 5 March 2014 (UTC)

Thank you for preventing some other people from experiencing the same puzzlement. JRSpriggs (talk) 07:53, 5 March 2014 (UTC)

As a fresh eye on this, it is definitely awkward, to read this section. The term class function appears out of the blue without having it defined anywhere on the page. There is no link, no reference, nothing. What to do about this? Another question is, how important is this bit of technical information to the overall point of the article? The article is titled "Transfinite Induction" and this section isn't even about that. So now we've detoured into a related subject, and we're expecting the reader to know jargon that he apparently didn't have to know in order to understand the main topic. All of this, and it's not even the topic that brought him here... In addition to making it more accessible, perhaps we also need to better justify this section.

I am trying to think of the audience and I'm trying to be reasonable about what technical terms we should allow or not... I'm not sure the general public even thinks of functions as sets anyway... So from that perspective it seems as tho we're muddying up the article for the sake of pedantic accuracy. On the one hand, I think the topic is technical enough, that it is reasonable to expect the reader to have some interest in set theory. And they may appreciate the precision of our language later, once our meaning is clear. On the other hand, even the highly motivated and interested reader who isn't already accustomed to the jargon is going to find this presentation jarring.

Consider whether this section should be moved to its own page, which can then be linked to in the "See also" section. It would be less jarring i think in that fashion. 24.110.50.184 (talk) 07:18, 6 May 2014 (UTC)

Problems (2015)

I'm not happy with the footnotes. The second one is not entirely bad, but the first one assumes ZF set theory. In NBG or MK set theories (among others), a "class function" is just a function which is not necessarily a "set". Also, transfinite recursion doesn't quite work in ZF. You can correct the conclusion as follows:

1. (Traditional) for any ordinal λ there is a function F: λ → V such that for all α < λ, ....
2. (Advanced) There is a "class function" F: Ord → V such that ....

This article needs specific references. I don't have a copy of Suppes's book. I do have a copy of my late mother's book, Set Theory for the Mathematician, which has most of the relevant theorems, but uses NBG or MK as the underlying set theory. (I also have Kelley's book, General Topology, but I don't think it actual uses transfinite induction. It also uses, of course, Morse-Kelley set theory, rather than ZF.) — Arthur Rubin (talk) 07:50, 23 August 2015 (UTC)

Sections "Transfinite induction" and "Transfinite recursion"

I just noticed that some time ago a section header titled "Transfinite induction" was removed by a bot, effectively moving the contents of the first section into the lede section, see diff. I think the reason for changes like this is that the section title was equal to the page's title, leading to conflicting <h1> and <h2> IDs, see MOS:HEAD: "Section and subsection headings should preferably be unique within a page; otherwise section links may lead to the wrong place, and automatic edit summaries can be ambiguous." Anyway, I think I actually prefer the flow of the page before this change, with two sections "Transfinite induction" and "Transfinite recursion", see old version. What do the other wikipedians say? Should something like the section title be reinstated? – Tobias Bergemann (talk) 10:37, 8 October 2015 (UTC)

The final inference: that P(all ordinals) is true. Verdana♥Bold 15:25, 24 August 2020 (UTC)

question about P

It says that if P(alpha) is true, then P(all ordinals) is true.

The set of new ordinals that are inferred to be true after transfinite induction: is that set the compliment of alpha? Verdana♥Bold 15:25, 24 August 2020 (UTC)

You are misinterpreting the line "Let $P(\alpha )$ be a property defined for all ordinals $\alpha$. Suppose that whenever $P(\beta )$ is true for all $\beta <\alpha$, then $P(\alpha )$ is also true. Then transfinite induction tells us that $P$ is true for all ordinals.".

The conclusion is $\forall \alpha P(\alpha )$. JRSpriggs (talk) 19:18, 24 August 2020 (UTC)