Understanding Transfinite Recursion and Zorn's Lemma

[disregardthat]

I am trying to understand the proof of Zorn's lemma from the axiom of choice, but I do not entirely understand the step where we create a increasing sequence (a_i) of sets in a partially ordered set S indexed by ordinals. It is defined through transfinite recursion, but how does that work?

We assume that Zorn's lemma is false for a partially ordered set S. So for any element we have a larger one. One starts with defining the function b on the set of chains of S to S by letting b(T) be an element of S such that b(T) is larger than any element of the chain. T has an upper bound, so such an element exists, and by the axiom of choice this function is well-defined. Then one picks an element a_0 in S, and then for each ordinal w>0 one defines $$a_w = b(\{ a_v | v<w\})$$ by transfinite recursion. Could someone explain this step?

The proof continues by saying that this sequence exhausts S. What does that mean? My guess would be that we can identify an ordinal W with a cardinality strictly larger than that of S (e.g. the cardinality of P(S)), so that we have an surjection from S into the set $$\{ a_v | v \leq W\}$$ which has cardinality W. But I don't know if we have ordinals corresponding to cardinals.

By the way, I would prefer that the explanation does not rely on the well-ordering theorem. This brings up the question: does the existence and properties of the ordinals needed for this proof rely on the well-ordering theorem?

 

[micromass]

I'm quite satisfied to see someone who's interested in the axiom of choice. It has always been my preferred subject of mathematics...

From what I see, your proof does not rely on the well-ordering theorem. Not even the construction of b uses the well-ordering theorem (and that's the moment were one would typically need it)

I am trying to understand the proof of Zorn's lemma from the axiom of choice, but I do not entirely understand the step where we create a increasing sequence (a_i) of sets in a partially ordered set S indexed by ordinals. It is defined through transfinite recursion, but how does that work?

We assume that Zorn's lemma is false for a partially ordered set S. So for any element we have a larger one. One starts with defining the function b on the set of chains of S to S by letting b(T) be an element of S such that b(T) is larger than any element of the chain. T has an upper bound, so such an element exists, and by the axiom of choice this function is well-defined. Then one picks an element a_0 in S, and then for each ordinal w>0 one defines $$a_w = b(\{ a_v | v<w\})$$ by transfinite recursion. Could someone explain this step?

I will explain this naively, if it still doesn't work out, tell me. We begin by picking an element a_0. This is a chain, so by assumption, there exists a bigger element which we call a_1. Then {a_0,a_1} is a chain, so by assumption, there is a bigger element which we call a_2. Then {a_0,a_1,a_2} is a chain, so bla bla bla. So eventually we will obtain a sequence {a_0,a_1,a_2,...,a_n,...}, so for every finite ordinal we have a point. Now this is a chain which has a larger element, we call it a_omega. And then you go on to define a_omega+1,...

Now you can easily formalize this proof. The larger element is just called b(T). And the transfinite recursion is also easily satisfied.

The proof continues by saying that this sequence exhausts S. What does that mean? My guess would be that we can identify an ordinal W with a cardinality strictly larger than that of S (e.g. the cardinality of P(S)), so that we have an surjection from S into the set $$\{ a_v | v \leq W\}$$ which has cardinality W. But I don't know if we have ordinals corresponding to cardinals.

Saying that the sequence exhausts S, just means that there is an ordinal $$\beta$$ such that $$\{a_0,a_1,...,a_\beta\}$$. To prove this, it is best not to work with cardinals, since it will involve wellorderening the set S and this will use choice...
It is best to argue by contradiction. Say that for every ordinal $$\beta$$ we have that $$\{a_0,a_1,...,a_\beta\}\subset S$$, so for every ordinal we can associate an element of S. Let ORD by the class of all ordinals, then we can find a "surjection" S--> ORD. But by the axiom of replacement (or substitution), this means that ORD is a set. This is in contradiction with Burali-Forti (which simply states that ORD cannot be a set).

 

[disregardthat]

Thank you for your reply.

Now you can easily formalize this proof. The larger element is just called b(T). And the transfinite recursion is also easily satisfied.

Could you explain what transfinite recursion is? I understand the general idea, but I am not familiar with the formalism behind it. I would like to know the necessary steps to perform a transitive recursion. I am not so familiar with ordinals. Could you give the general definition of the ordinals as well, or a good reference to where I could read about the construction of the ordinals? I guess transfinite recursion is just the way of defining a class function from the class of ordinals to some domain. Or maybe a well-ordered set as well.

I understand the rest of the proof.

Is it true that each set there is a unique ordinal W such that there is a order-preserving bijection between a well-ordering of the set and the set of all ordinals less and equal to W? Thus similar to cardinals, only that the bijections need to be order-preserving.

 

[micromass]

Transfinite recursion can be used to define a "function" f with domain ORD which satisfies what you want.

You'll need the following:
- you'll have to f(0)
- you'll have to desribe f(a+1) with ordinal a.
- for any limit ordinal a, you'll need to describe f(a) with ordinals <a

For example, we can use recursion to define a function which multiplies by 2.
- f(0)=0 (indeed, we want that 2.0=0)
- f(a+1)=f(a)+2
- if a is a limit, then $$f(a)=\max\{f(\beta)~\vert~\beta<a\}$$

Now, you'll need to know ordinals well for this. To learn about ordinals, I suggest reading "introduction to set theory" from Hrbacek and Jech. I feel that this is the easiest book...

 

[disregardthat]

I borrowed the book Sets, Logic and Categories of the Springer publications from the university library, and I know the theory up to ordinal induction. It does not mention transfinite recursion however, and I don't really feel confident in the explanation on wikipedia. I would appreciate if you could explain it in terms of transfinite induction.

 

[micromass]

Hmmm, it is impossible to state this with transfinite induction alone. Transfinite induction can only be used to prove things of the form "for every ordinal holds...". Transfinite recursion is something completely else. It is used to construct certain functions. And, unlike induction, recursion relies heavily on the axiom of replacement (substitution).

If you really want to know about recursion, I would suggest that you read a set theory book like Hrbacek and Jech. Also online lecture notes like http://www.cis.upenn.edu/~byorgey/settheory/ could come in handy to...