Thread: Question regarding a Lemma on axiom of choice

Hello all,

I am currently reading a book on set theory "Joy of Sets" by Keith Delvin. In page 58 he proves a lemma which is stepping stone for proving that axiom of choice(AC) and 'Every set can be well ordered' (WO) are equivalent. The lemma goes something like this

(AC') Every set of nonempty sets has a choice function
Assume AC'. Let A by any set. Then there is a function f: P(A) -> A U {A} such that
1. f(A) = A
2. f(X) belongs to A-X, whenever X is subset of A

(P(A) means power set of A, and symbol U means union)
Proof: Let
B = {A-X| X is subset of A}

By AC', let g be a choice function for B. Thus g:B -> U B and g(Y) belongs to Y for all Y belongs to B. Define
f: P(A) -> A U {A}
by
f(A) = A,
f(X) = g(A-X), if X is subset of A.
Clearly, f is as required

Now, I took an example of A = {x,y,z}, now
AU{A} is {x,y,x,{x,y,z}}
and P(A) is {{},{x},{y},{y},{z},{x,y},{y,z},{z,x},{x,y,z}}

I understand f(X) can be a result from choice function g(A-X), but I dont understand how f(A) = A.
Also, is the methodology applied to prove the lemma is correct?

Note that in the proof

Originally Posted by skanur

Let B = {A-X| X is subset of A}

the set B should be {A - X | X is proper subset of A}. Otherwise, B includes the empty set (in fact, B = P(A)) and AC' is not applicable to B.

Originally Posted by skanur

I understand f(X) can be a result from choice function g(A-X), but I dont understand how f(A) = A.

We can define f to be what we want on A. On proper subsets, f returns an element from the complement. On A itself, it may return some special flag indicating that g is not applicable to A. (Since everything is a set, the flag has to be a set as well.) In this case, one chose the flag to be A itself.

Yes, X is indeed a proper set of A. Now I have major understanding conflict between various definitions in sets with regard to this lemma. Kindly clarify them
1. In the definition of B, it does not say 'for all X'. So X is a single random occurrence and using my previous example B could be "any one" of these sets
{x};{y};{z};{x,y};{y,z};{x,y,z}
2. U B is now union of all the possible occurences of B, which is P(A)-{} i.e {{x},{y},{z},{x,y},{y,z},{x,y,z}}
3. What does A U {A} mean? Does it mean successor of A (or something like that). What is the significance of choosing AU{A} for proof of this lemma?
4. Assuming lemma is correct, if I apply function to a set {x} in P(A), then f({x}) should be {x,y} which is clearly not present in AU {A}, even though choice function g(A-X) is true.

So what is going on? Where are the flaws in my understanding?

Originally Posted by skanur

1. In the definition of B, it does not say 'for all X'. So X is a single random occurrence and using my previous example B could be "any one" of these sets
{x};{y};{z};{x,y};{y,z};{x,y,z}

The set builder notation {x | Φ(x} denotes "the set of all individuals in the universe of discourse satisfying the formula Φ(x), that is, the set whose members are every individual x such that Φ(x) is true." Therefore, in your example B = {{x}, {y}, {z}, {x,y}, {y,z}, {x,y,z}}, i.e., . ( is another notation for {}.)

Originally Posted by skanur

2. U B is now union of all the possible occurences of B, which is P(A)-{} i.e {{x},{y},{z},{x,y},{y,z},{x,y,z}}

No, is the union of the elements of B, i.e., {x} ∪ {y} ∪ {z} ∪ {x,y} ∪ {y,z} ∪ {x,y,z} = {x,y,z}.

Originally Posted by skanur

3. What does A U {A} mean?

It's the union of two sets: A and a set with a single element A, i.e., it's the result of adding A itself to A. Think about a drawer containing pencils. Then take a bigger drawer, put the same pencils in it and then put in the first drawer.

Sets containing sets containing sets, etc. is one of the confusing aspects of set theory. Fortunately, in the standard set theory, the chain of containments ∈ is always finite.

Originally Posted by skanur

Does it mean successor of A (or something like that).

Yes, this is the standard definition of successor on natural numbers and, more generally, on von Neumann ordinals. However, there are other definitions of natural numbers in set theory. In any case, this does not seem to be relevant to the OP.

Originally Posted by skanur

What is the significance of choosing AU{A} for proof of this lemma?

Originally Posted by emakarov

We can define f to be what we want on A. On proper subsets, f returns an element from the complement. On A itself, it may return some special flag indicating that g is not applicable to A. (Since everything is a set, the flag has to be a set as well.) In this case, one chose the flag to be A itself.

Maybe the fact that f(A) = A is important in the rest of the proof of the equivalence of different forms of AC, but not in this lemma.

Originally Posted by skanur

4. Assuming lemma is correct, if I apply function to a set {x} in P(A), then f({x}) should be {x,y} which is clearly not present in AU {A}, even though choice function g(A-X) is true.

First, a set, e.g., a choice function, cannot be true or false, only propositions like A = B can be. Second, g({y,z}) by definition returns y or z (since g returns an element of its argument). So f({x}) = g(A - {x}) also equals y or z. We have y ∈ A U {A} and z ∈ A U {A}.

Thanks a million!

It solved various basic questions, especially about set builder notation.