Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have some kind of "homework" question. I have the following theorem:

Theorem (Transfinite Recursion over the class of of ordinals $\mathbf{ON}$: Let $\mathbf{V}$ be the class of all sets. If $\mathbf{F} : \mathbf{V} \to \mathbf{V}$ then there exists a unique $\mathbf{G} : \mathbf{ON} \to \mathbf{V}$ such that for all $\alpha$ $\mathbf{G}(\alpha) = \mathbf{F}(\mathbf{G}|_{\alpha}))$.

Now I want to show that if $\hat{x} = \{y : y < x\}$ and if $\mathbf{F} : \mathbf{V} \to \mathbf{V}$ and $(X, <)$ is a well-ordering then there exists a function $f$ with domain $X$ such that $f(x) = \mathbf{F}(f|_{\hat{x}}$.

So I let $0 = \text{min}(X)$, and then I note that I want $f(0) = \mathbf{F(\emptyset})$. I continue like this and I note that $f(1) = \mathbf{F}(f(0))$ and so on. Is this correct? If so, can someone give me a hint how I apply the above theorem to say that this construction works?

share|cite|improve this question
Ordinals are not that elementary... – Asaf Karagila Dec 7 '10 at 4:25
up vote 3 down vote accepted

If you can use the transfinite recursion theorem you stated, why not simply apply it to $F$, and then use an isomorphism between $X$ and some ordinal to transfer the function $G$ from $ON$ to $X$? It seems like you are trying to reprove the transfinite recursion theorem rather than just applying it.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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