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

Quote:

(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?

Re: Question regarding a Lemma on axiom of choice

Note that in the proof

Quote:

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.

Quote:

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.

Re: Question regarding a Lemma on axiom of choice

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?

Re: Question regarding a Lemma on axiom of choice

Quote:

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

Quote:

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

Quote:

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

Quote:

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.

Quote:

Originally Posted by

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

Quote:

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.

Quote:

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

Re: Question regarding a Lemma on axiom of choice

Thanks a million! (Bow)

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