Confused about Axiom of Choice

(1) I understand that if I have a non-empty set $A$, choosing an element $\alpha$ from $A$ does not require the Axiom of Choice.

(2) I also understand that if I have a finite collection of non-empty sets, I can iteratively apply the fact that I can choose an element from each non-empty set to construct a choice function.

But then, what bothers me is the following line of thought:

All I used in (1) and (2) above is the non-emptiness of the sets to show that I can pick an arbitrary element from the set. I do not care which element I am picking from the set; as long as the set is non-empty, I can always pick any element out of it. Then, why can't I say the same thing even if I have an inifinite collection of sets? 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.

Please help me out :)!

Solution 1:

Let's see why you can choose from finite sets. The proof is by induction on $n$.

If $X$ is a family of $0$ non-empty sets, then $X$ is the empty set, and it admits a choice function $\varnothing$ (which is a function from $X$ to $\bigcup X$ satisfying the requirements of a choice function).

Suppose that we can choose from families of size $n$, and let $X$ be a family of $n+1$ non-empty sets. Choose $A\in X$ and consider $X\setminus\{A\}$, this is a family of size $n$ so it admits a choice function $g$; and since $A$ is non-empty, if $a\in A$ is any element then $f=g\cup\{\langle A,a\rangle\}$ is a choice function on $X$.

Since in $\sf ZF$ it is true that if $\varphi$ is true for $0$, and if $\varphi$ is true for $n$ then it is true for $n+1$, then $\varphi$ is true for every natural number. So we can choose from every finite collection of sets. $\quad \square$

Let's analyze this proof. The case of $n=0$ is uninteresting, moving on. In the case of $n+1$ we had to choose $A\in X$, a choice function $g$ and an element $a\in A$. That's three choices (note that each choice is from a different set, by the way). But all these choices didn't happen in the universe of set theory, they occurred as instantiation of existential quantifiers in the meta theory.

What about the induction? How does induction work? Induction work when in the proof of the step we can make the set noticeably smaller. This means smaller cardinality, or smaller order type or so on. And then, we can apply the hypothesis on one of the smaller parts, and manually take care of the remainder.

So this argument cannot possibly proceed to infinite sets, because we are not interested in any structure, just cardinality, suppose that $X$ is a countably infinite set, by removing any finite part (not just one element) you still have a countably infinite set (so you cannot apply the hypothesis); and by removing enough to stay with a finite set, your remainder becomes countably infinite (so you cannot deal with it manually).

Similarly, if you can prove it all countable sets, what happens when you consider uncountable cardinals? By removing a countable set away you're usually going to have the same cardinality as the original set, so the same problem from above ensues.

So you can't prove it for infinite sets by induction. And perhaps you're thinking, "well, just glue the choices you make until you have an infinite set", but the above proof doesn't guarantee that is possible either. In each case we "essentially" begin the induction from $0$ and climb up. In order to glue the steps into an infinite sequence you need a weak choice principle called Dependent Choice (which in turn implies countable choice, by the way). And of course, even then you are only able to glue countably many choices together. If you want to be able to glue even more, out of any infinite set, this essentially means using the Teichmuller-Tukey Lemma which is equivalent to the axiom of choice.

Solution 2:

You need to keep in mind the set-theoretic definition of a function. A function $f$ from $X$ to $Y$ is a subset of $X\times Y$ such that $\forall x\in X \,\exists !y\in Y \left[(x,y)\in f\right]$. Instead of writing $(x,y)\in f$, we usually write $f(x)=y$ which lends itself to be more intuitive.

The Principle of Finite Choice (which is the second principle you state) follows from the fact the other axioms of set theory are 'finite-friendly'. What I mean is that if you already have a choice function $f$ for a finite set $C$ and want one for $C\cup\{A\}$ (with $A$ non-empty), you take an arbitrary element $x\in A$ and consider the set $g=f\cup\{(A,x)\}$ (which you can build from the other axioms). This $g$ is a choice function for your second set. Thus the Principle of Finite Choice follows from induction and the fact that every singleton of a non-empty set has a choice function AND the fact that every unordered pair of non-empty sets has a choice function (which we know to exist by the other axioms).

Now a problem creeps in when our collection $C$ is infinite. We cannot apply finite induction to conclude that $C$ has a choice function. The Principle of Finite Choice can be extended to say that every finite subset of every collection of non-empty sets has a choice function. This can be seen as building a choice-function for $C$ piece-meal. While this works when $C$ is a finite set it doesn't for an infinite one. So we can't say whether $C$ itself has a choice function. We need another axiom to allow us to postulate that.