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

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.

• What if I have an indexed collection of sets $A_j$, where j is a member of infnite set J, and each $A_j$ = set of real numbers? Then, I can associate a real number with each index j, so I would still have an infinite number of elements. In this case would I need the axiom of choice even though my collection consists of only a single set $R$? – David May 6 '14 at 7:29
• How can you associate a real number with each $A_j$? How can you be sure that you haven't associated a real number with two different $A_j$'s? – Asaf Karagila May 6 '14 at 7:30
• I think it is okay to associate a real number with two different $A_j$'s because my choice function needs not be injective. isn't it? – David May 6 '14 at 7:33
• I'm confused. You assume that all your sets are the same set? Sure, that doesn't require the axiom of choice to choose from. If $A_j=\Bbb R$ for all $j$, then $f(j)=0$ is a choice function. Sure. Huzzah, we can choose from an infinite family of the same set. – Asaf Karagila May 6 '14 at 7:54
• All that shows is you can pick an element from $\mathbb{R}$, not any arbitrary family of sets, which is what Choice gives you. – Malice Vidrine May 6 '14 at 7:56

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.

• If I have an indexed collection of sets $A_j$, where $j$ is a member of infinite set $J$, and each $A_j$ = $R$, set of real numbers, would I need to have the Axiom of Choce to define a choice function in this case? On one hand, I have a sinlge set in my collection whereas on the other hand, my index set is infinite, so I am not sure... – David May 6 '14 at 5:53
• Most likely yes. Sometimes you won't have to, like when your index set is $\Bbb N$. Then you can define your choice function to be pick out $n$ for the $n$th copy of $\Bbb R$ you're in. You also don't need to worry when your index set is finite. Keep in mind that being able to choose a random element from one set does not automatically mean you can choose an infinite number of random elements, each one from a different set. Being able to choose infinitely many doesn't follow from being able to choose freely. – user123641 May 6 '14 at 16:15
• Bryan: You might want to read the comments under my answer (and under bof's answer too). – Asaf Karagila May 6 '14 at 18:19

There is nothing to stop you from picking all of those elements. But how do you know that there is a set containing the elements you picked and only those? If you pick two elements $a,b$ the existence of the set $\{a,b\}$ is guaranteed by the Axiom of Pairing; for three elements $a,b,c$ the existence of the set $\{a,b,c\}$ follows from the Axiom of Pairing and the Axiom of Union. But that only works for finite sets; there is no axiom saying that an arbitrary multitude of elements $a,b,c,\dots$ can be collected into a set $\{a,b,c,\dots\}$. Intuitively, that set ought to exist, and that is the intuitive justification for the Axiom of Choice.

• What if I have an indexed collection of sets $A_j$, where $j$ is a member of infnite set $J$, and each $A_j$ = set of real numbers? Then, I can associate a real number with each index $j$, so I would still have an infinite number of elements, so in this case are saying that I need the axiom of choice even though my collection consists of only a single set $R$? – David May 6 '14 at 4:54
• When you say each $A_j=$ "set of real numbers" do you mean "a set of real numbers" or "the set of all real numbers"? If the $A_j$ are all the same nonempty set, you don't need the Axiom of Choice; just pick one element from that set and define a constant function on $J$. E.g., if each $A_j$ is the set of all real numbers, just pick $\pi$ every time. On the other hand, if the $A_j$ are "random" nonempty sets of real numbers, then you need the Axiom of Choice. No reason to avoid it, use it whenever you need it, just like the other axioms of set theory. – bof May 6 '14 at 7:39
• @bof: You may want to read the comments under my answer. – Asaf Karagila May 6 '14 at 8:46