What is the Axiom of choice Proof that Axiom of choice zorns

What is the Axiom of choice?

Proof that:

Axiom of choice= zorn\'s Lemma

I have read some proofs, but I didn\'t understand.

Solution

solution

Assume the axiom of choice. Let (P,)(P,) a partially ordered set that every chain has an upper bound. Let ff to be a choice function from all non-empty subsets of PP, and let Pa={xPa<x}Pa={xPa<x} then Pa=Pa= if and only if aa is a maximal element.

We define by using transfinite induction:

Let a0a0 be an element of PP, if it is maximal then we have finished. Otherwise P0={xPa0<x}P0={xPa0<x} is non-empty, let a1=f(P0)a1=f(P0).

Suppose aa was defined, if it is maximal then we are done, otherwise P={xPa<x}P={xPa<x} is non-empty and a+1=f(P)a+1=f(P).

If is a limit ordinal, and for all << we have chosen aa, then {a<}{a<} is a chain without a maximal element in PP, and therefore bounded with an upper bound above all the elements of the chain, thus <P<P, and let a=f(<P)a=f(<P).

We argue that this must stop at some point, otherwise we have an injection from the proper class of the ordinals into the set PP. Why did the process stop? It can only stop if we have reached a maximal element at some aa, as wanted.

Assume Zorn\'s lemma, and let XX be a non-empty collection of non-empty sets. Let (C,)(C,) be the set of all choice functions from some elements of XX.

This is a non-empty set, since we can always choose from finitely many sets. Given a chain of choice functions, the union is indeed a function. So the condition of Zorn\'s lemma is satisfied. We have a maximal element ff.

If ff is not a choice function from all the members of XX then we can extend it to one more element, which contradicts the maximality.