I am trying to understand transfinite recursion. So far I have encountered two different definitions of this theorem (not completely sure whether they describe the same Principle of Transfinite Recursion). The first one:

If I have a map $I:X^{<\alpha}\rightarrow X$ (for $\alpha$ some ordinal - here "$X^{<\alpha}$" denotes the set of maps from $\beta$ to $X$, for any $\beta<\alpha$), then there is a unique function $f: \alpha\rightarrow X$ such that for all $\beta<\alpha$, $f(\beta)=I(f\upharpoonright\beta)$.

And the second:

Let G be an operation (In the context of Set theory). Does this mean that for some fixed parameters $u$, if there are any, $\forall x\exists!y\phi(u,x,y) \wedge G(x)=y $). Then there exists a unique operation (this time it was called operational formula or something like that) $F$ so that for all $Ord(\alpha), F(\alpha)=G(F\restriction \alpha)$.

How do these two theorems interact with each other? Some simple additional intuition about the difference between recursion and transfinite recursion will not be waste of time.

Also the professor said that the transfinite recursion principle is a meta-theorem schema. What does it logically mean?


The second implies the first, but in "everyday mathematics" we rarely appeal to the second case.

The first case merely states that if you have a well-ordered set, and some function that tells you "how to extend" a function defined on some initial segment of the well-order, then you can keep extending the function through the entire well-ordering.

Namely, if $\alpha$ is an ordinal, and $I$ is a rule that tells you that if you happened to have a function defined on $\beta<\alpha$, then you can extend this function to $\beta+1$, then there is a unique function defined on $\alpha$ such that every successor step is defined using $I$ "again and again and again".

The second theorem talks about the same thing, but with the proper class of all the ordinals. This implies the first instance, since we can always hit a fixed value and then keep returning the same value for the rest of the "run" of the function. But dealing with proper classes is always delicate, since they are not sets. Which is why your professor said this is a meta-theorem, rather than a theorem.

Since classes are not objects of the universe of set theory, but rather objects of the meta-universe of the meta-language, it follows that any class-function (namely a function whose domain is a proper class) is not an object in the universe, but rather an object of the meta-universe. So formally transfinite recursion is a schema that states that whenever $\varphi$ is a function which defines such and such class, then we can write a formula $\psi$ such that $\psi$ defines a class-function on the ordinals where $\varphi$ is used to step through successor steps.

  • $\begingroup$ Thank you for the answer. Just one thing before marking it. Could you please make parallel between the two? You have described it well but it is hard for me to see which object from the first case is the meta-case in the second one. And one additional question: Do you use $\alpha = <\alpha )$ and the fact that every well-ordered set is isomorphic to unique ordinal when you are describing the first case? $\endgroup$ – Blake Jan 4 '17 at 10:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.