1. ## Transfinite Recursion

Hi, I am doing a project on axiomatic set theory and i'm having a lot of trouble with transfinite recursion. It's not that the proof itself is particularly difficult to follow, only that the statement of the theorem itself is very hard to conceptualize. I have been trying to apply the theorem to show that some simple recursively defined sets - e.g. the fibbonacci sequence - exist, and I have been unable to do this. Of course, I realise that one would normally simply use recursion to show this, but my problem is that I need to understand transfinite recursion in order to, for instance, apply it in proving the equivalence of the axiom of choice and the well-ordering principle. So basically what i am looking for is examples of concrete applications of the transfinite recursion theorem. Any help is appreciated!

2. (1) Though some proofs of the equivalence of the axiom of choice and well ordering use transfinite recursion, there are proofs of that equivalence that don't use transfinite recursion. More generally, transfinite recursion depends on the axiom schema of replacement, i.e., ZF. But the equivalence of the axiom of choice and well ordering is provable in Z alone.

(2) Examples of transfinite recursion include such things as recursion on the ordinals, such as the alephs, the beths, the cumulative hierarchy, etc. Also there are applications of transfinite recursion that are not just on the ordinals, but the applications on the ordinals might be the easiest to visualize.

(3) As to the statement of the theorem itself, remember that it is a theorem SCHEMA. It is stated in the meta-language for the object language of set theory. It is a statement that specifies that a certain set of sentences in set theory are all theorems.

What textbooks are you using?

3. 1) Thank you, I didn't realise that it could be proved without transfinite recursion. Could you refer me to any texts that do this?

Unfortunately, my final plan is to show that AC implies WO implies Zorns Lemma implies Hausdorff's Maximal Principle implies AC. Is it possible that I will not need transfinite recursion at all?

(2) Thanks, I'll look into some of the applications and see if it helps.

(3) Does this mean I will need some kind of corollary before I can use the Theorem directly?

The text book I have used to show AC implies WO is Set Theory An Introduction (2nd Ed.) by Vaught, R. I also referred to Introduction to Set Theory (2nd Ed.) by Jeck, T. and Hrbacek, K. I have taken the statement of the Transfinite Recursion Theorem from Set Theory (3rd Ed.) by Jeck, T. The proof attached that AC implies WO below - which does require transfinite recursion - is based on that given in Set Theory An Introduction.

4. Correction: In my previous post I said 'axiom schema' where I meant 'theorem schema'.

(1) Stoll's 'Set Theory And Logic'. Lipschutz's 'Set Theory And Related Topics' (Schaum's Outline series).

AC, WO, Zorn's, Hausdorff, etc. are all equivalent in Z-R set theory alone (i.e., don't have to have axiom schema of replacement or transfinite recursion; nor axiom of regularity).

(3) Well, there are several variations of the transfinite recursion theorem schemata, some corollaries depending on the approach. But my point is just that you should understand that it is not itself a theorem but rather a theorem schema. It's a meta-statement about set theory; it's a meta-statement that says that a certain set of sentences are theorems of set theory.

You already have a proof of AC -> WO, but the converse is trivial, so you're done as far as AC <-> WO.

Those are good books (the Vaught book though I'd have to refresh my memory on how good it is), but for understanding transfinite recursion, I've found Enderton's 'Elements Of Set Theory' to be the best.

5. I have started looking at Enderton's 'Elements Of Set Theory'. Although it will take me a while to get familar with the notation, it appears to be just what I was looking for - it provides explanations of exactly how the theorem is applied to the examples. Also, it is useful to know that, if I fail to come to a better understanding of the Transfinite Recursion Theorem, there is another way. Thank you so much!

6. Enderton's notation is about as standard as it gets. It's not very different from Jech, so you'll be fine.

Jech is a great book, but very hard for beginners. It's meant for grad students who've already done a book like Enderton or Jech/Hrbacek.

Anyway, you'll enjoy Enderton's book; he really breaks it down step by step.