Let $f\colon\alpha\to\beta$ be a function between ordinals $\alpha,\beta$.

I want to define a function $g\colon\alpha\to\gamma$ for some ordinal $\gamma$ so that

$(\forall \eta < \alpha)(g(\eta) = \max\{f(\eta),\bigcup_{\xi < \eta} (g(\xi)+1)\})$

This construction appears in a book by Krzysztof Ciesielski called "Set Theory for the working mathematician". The author doesn't specify the process of obtaining such a function from $f$, simply saying that is it defined by "transfinite induction".

My thoughts on the matter:

From what I can see, we need the following transfinite recursion theorem:

Transfinite Recursion. Let $G$ be a class function from the class of all sets into the class of all sets. Then there is a class function $F$ from the class of ordinals to the class of all sets so that for any ordinal $\eta$ we have

$$F(\eta) = G(F{\restriction}_{\eta}).$$

For instance, one could start like this: consider a class function $G$ so that for any set $x$, $G(x) = \bigcup\mathrm{ran}(x)$ if $x$ is a relation and $G(x) = \varnothing$ otherwise.

Then there is a class function $F$ so that for any ordinal $\alpha$, $F(\eta) = G(F{\restriction}_{\eta}) = \bigcup\mathrm{ran}(F{\restriction}_{\eta}) = \bigcup_{\xi < \eta} F(\xi)$.

But then we would need a way to obtain a set $\bigcup_{\xi < \eta} (F(\xi) + 1)$ from a set $\bigcup_{\xi < \eta} F(\xi)$ for every ordinal $\alpha$, and I currently don't see it. Perhaps, it was a wrong strategy to begin with.

Moreover, even if we had a a class function $F$ sending each ordinal $\eta$ to $\bigcup_{\xi < \eta} F(\xi)$, we would still need to somehow obtain a class function $H$ sending each ordinal $\eta$ to $\max\{f(\eta),\bigcup_{\xi < \eta} F(\xi) \}$.

Of course, any such class function $H$ could to restricted to $\alpha$ to obtain a desired function $g$.

  • 1
    $\begingroup$ By even writing an expression like $\bigcup_{\xi < \eta} (f(\xi)+1)$, you are implicitly asserting that this can be expressed by a formula in the language of set theory (otherwise it would be meaningless to write). So your question really doesn't have anything specifically to do with transfinite recursion, it's about how that expression even makes any sense at all. $\endgroup$ Sep 20, 2018 at 16:44
  • 1
    $\begingroup$ Also, is the formula for $g(\eta)$ supposed to instead be $\max\{f(\eta),\bigcup_{\xi < \eta} (g(\xi)+1)\}$? As you wrote it, there is no reason to use transfinite recursion at all, since the definition does not involve any previous values of $g$. $\endgroup$ Sep 20, 2018 at 16:49
  • $\begingroup$ @EricWofsey Yes, I meant to write $\max\{f(\eta), \bigcup_{\xi < \eta} (g(\xi) + 1) \}$. $\endgroup$
    – Jxt921
    Sep 20, 2018 at 18:40
  • $\begingroup$ @EricWofsey I'm not sure I understand how your first comment relates to my question. Of course $\bigcup_{\xi < \eta} (g(\xi) + 1)$ makes sense in the language of set theory, it was never in question. The problem is obtaining the desired class function. What I meant is I see no way to obtain a class function $F$ so that $\forall \eta, F(\eta) = \bigcup_{\xi < \eta) (F(\xi) + 1)$. But it's not that important since I even having such class function doesn't imply having the desired class function. $\endgroup$
    – Jxt921
    Sep 20, 2018 at 18:45

1 Answer 1


Just define $$G(x)=\max\{f(\operatorname{dom}(x)),\bigcup\{a+1:a\in\operatorname{ran}(x)\}\}.$$ More generally, if you're constructing something by recursion, you almost never want to do it "piecemeal" the way you did with the $G$ you proposed. The whole point is that you define $G$ to be the function that takes the sequence you have so far to the next term of the sequence.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .