Why does the axiom of choice become necessary for countably many sets?

[abiyo]

So if we have a finite collection of disjoint non-empty sets, one can show using ZF only(with no need of AC) there is a choice function. I understand the reason for this. My confusion is when one goes to non-finite collection of sets. For example if the index set is the Natural numbers, why
do we need AC? Why will this case be different from the finite case?

 

[disregardthat]

In ZF (and ZFC) we have different rules to construct the objects we say exist. It is simply a matter of fact that we cannot use the rules given in ZF to construct a choice function for a general family of sets. Read the axioms of ZFC to see what these rules consist of. To be able to say that a choice function exist, we just have to posit this rule as another axiom.

To construct a choice function for a finite family of sets we can iteratively use the fact that from a non-empty set we can choose one single element. This iteration fails for the infinite case, since we cannot at any point say we actually have constructed the function.

Note that in many cases we can find a choice function from an infinite family of sets. If we have a method of "picking" from the sets which doesn't involve a decision (a decision is to simply the use of the fact that there exists an element 'x' in a non-empty set S), then we can define the choice-function properly.

E.g. if our family of sets consists of the family of different modulo-classes of integers, we can simply pick the integer n from the modulo class of n. This is our method: From the modulo class of n, pick "n". This is an infinite family of sets, but since we have a rule to pick an element from each set in the family (and must not decide), our function is well-defined. The reason that this works when we have a method and not when we don't has to do with the way we can use the axioms of ZF (it can be implemented by using the axioms, so to say).

 

[Hurkyl]

...I understand the reason for this. ... Why will this case be different from the finite case?

Just to clarify -- do you understand why the argument that a choice function exists for finite collections simply does not work for infinite collections?

 

[micromass]

You can try to read my blog entries which try to answer such questions in a non-complicated manner. Certainly my first blog gives an analogue to AC which explains the problem...

 

[abiyo]

Thanks Jarle for the explanation and micromass I will take a look at your blog. Hurkyl, here is my understanding.

From Jarle's explanation, I know that for the infinite case we won't be able to say at any point explicitly what the choice function is. What is bothering me this line of thought.
Even with the finite case, all we used was the non-emptiness of the sets to show that we can pick some arbitrary element in the set.(and then use induction to construct a choice function). We didn't care what element we were picking from the set. So long as the set is non-empty, we could assign some arbitrary element to it. When we go to the infinite case couldn't we say the same thing? i.e define my choice function as an ordered pair where the first pair is the set and the second pair is some arbitrary element in the set. At the infinite case, we still don't have an explicit choice function at any point in time but wouldn't the arbitrary picking in the finite case apply to the infinite case as well (At least when it is indexed by the natural numbers)

 

[Hurkyl]

but wouldn't the arbitrary picking in the finite case apply to the infinite case as well (At least when it is indexed by the natural numbers)

Yes! Even the ability to do something so simple as to write down a formula that picks one element from a non-empty set is enough to construct a choice function for arbitrary sets of non-empty sets.

What you're missing is:

I know that for the infinite case we won't be able to say at any point explicitly what the choice function is.

It may surprise you to learn that we cannot even explicitly write down a choice function even from a single two-element set, unless we are given additional information allowing us to make a choice! The only reason we can say there exists a choice function in such a case is purely existentially -- can you see how to prove a choice function exists on a collection of one non-empty set?


As an aside, there are, of course, special two-element sets we can pick an element from. For example, we can explicitly pick an element from X knowing only "X is a set of 2 natural numbers" -- one explicit choice is "the smallest element of X". In fact, I believe you cannot explicitly write down a set upon which you cannot also explicitly write down a choice function, but I'm a little fuzzy on that detail.

 

[abiyo]

If I get what you said above, the choice function exists since the set is non-empty and a non-empty set, by definition, contains an element. So in the finite case the condition the sets are non-empty is equivalent to the existence of a choice function. I think this is making sense slowly. Thanks a lot Hurkyl.

 

[Hurkyl]

Now, can you extend the argument to show that a set of two non-empty sets has a choice function? Three non-empty sets?

 

[Chairman Lmao]

I am so glad I found this thread- the same question has been bothering me as well. Could someone please tell me what's wrong with this "derivation" of Axiom of choice?

Let {X_i} be a non-empty family of non-empty sets. Since for all i, X_i is non-empty, for all i, there exist x_i such that x_i is in X_i. So define using axiom of specification
$$f = \{ (i,x) \in I \times \bigcup_{i}X_{i} | x=x_{i} \}$$

Now for all i, $$(i,x_{i}) \in f$$ so that $$domf = I$$. Also, if $$(i,x) \in f and (i,y) \in f \Rightarrow x=y=x_{i}$$, so that f is a function.

The only possible problem I can see is that I am assuming the existence of arbitrarily many x_i's(but NOT that x is a function or even that the x_i's form a set) . Is it that you can assume the existence of only object at a time, or if you are assuming more than one, the individual statements MUST be sepeated by "and" ( as in for some a(a belons to X) and for some b(b belongs to X))?

PS: Sorry for the bad formatting. I am a novice in LaTeX

 

[micromass]

i[/SUB] is non-empty, for all i, there exist x_i such that x_i is in X_i.

This is a clever disguise of the axiom of choice. Of course, it is always true that for every X_i, there exists an element $x\in X_i$. This does not require the axiom of choice at all.
However, you wrote something different, you said that for every X_i, there exists an [itex]x_i\in X_i[/tex], that is, you already enumerated the elements of X_i. This means that you didn't take just an element of X_i, but you took elements from <b>each</b> X_i. This requires the axiom of choice.[/itex]

 

[Chairman Lmao]

double post

 

[Chairman Lmao]

I think I understand now..Thanks a lot for the reply!