# Defining Formulas with Transfinite Recursion.

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

• 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. – Newman Mar 28 '17 at 20:47
• 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. – Asaf Karagila Mar 28 '17 at 20:51
• 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. – Newman Mar 28 '17 at 20:59
• I think that Suppes' book, Axiomatic Set Theory, is a good place to look at this. – Edgar Almeida Mar 29 '17 at 1:45