I'm currently working through some set theory texts, and I am having some trouble with using the transfinite recursion theorem to create functions in the language of set theory. I am trying to sort out the use of the process where we write some formula of the form $$\phi = \text{'$f$ is a function' }\land \text{'dom($f$)}=\alpha\space\land\text{}...$$

to define a function. I'd like to get more practice with problems like this, so I would really appreciate if someone could point me in the direction of where to find examples or perhaps give an example. I appreciate any help.


These are examples in $\sf ZFC$, and they utilize a choice function.

You can use transfinite recursion to prove there is a bijection between $X$ and an ordinal. Fix a choice function from non-empty subsets of $X$ and use it for the recursive definition.

You can use transfinite recursion to prove that every vector space has a basis.

You can use transfinite recursion to prove that given a partial order, there is a maximal element, or an unbounded chain which is well-ordered.

You can use transfinite recursion to prove that every countable ordinal can be embedded into the rational numbers (this can be done without transfinite recursion, in a simpler way, but this is an example).

You can use transfinite recursion to define ordinal addition, multiplication and exponentiation (for bonus points: use transfinite induction to prove associativity, and other properties).

  • $\begingroup$ Do you know where I can find examples of how to construct a formula, like $\phi$ above, that defines the function? That is what I am having trouble with. $\endgroup$
    – Newman
    Mar 28 '17 at 20:47
  • 1
    $\begingroup$ Well, that formula has to have some parameters, and it's really something which is just tedious. Write the property of being an ordered pair; then write the property of being a set of ordered pairs; then write the property of being a set of ordered pairs with the additional functional property (i.e. a function); then write the property that $x$ is a domain of a function; then write that $x$ is an ordinal; then write that $f(x)=y$ for some $x$ in the domain of $f$... these are all just horrible exercises. I thought you were looking for exercises for transfinite recursion. $\endgroup$
    – Asaf Karagila
    Mar 28 '17 at 20:51
  • $\begingroup$ Right, I mean to write the formula more in the style of Kunen in his intro to independence proofs book. He doesn't actually write out the formula for the statements like '$f$ is a formula', he just abbreviates it. I was just curious to see some specific examples of how this is done. I think I am just after the 'form' these formulas take when defining a function. $\endgroup$
    – Newman
    Mar 28 '17 at 20:59
  • $\begingroup$ I think that Suppes' book, Axiomatic Set Theory, is a good place to look at this. $\endgroup$ Mar 29 '17 at 1:45

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.