# Why isn't Axiom of Choice a trivial result? Is it needed to prove existence of this recursive function?

I mean, if we have the collection of sets $\mathcal{A}$ and we choose the set $B$ to contain only one element from each set in $\mathcal{A}$, then is quite trivial that $B\subseteq \bigcup_{A\in\mathcal{A}}A$. And this holds even if the sets in $\mathcal{A}$ are not pairwaise disjoint. Then it wouldn't be needed to assume it as an axiom. What is the error of this reasoning?
In the other side, in Munkres' Topology 2nd Ed, he introduces this axiom when needs to proove the existence of an injection $f: \mathbb{Z}^{+} \rightarrow A$, for the infinite set $A$. So, let $a_1$ be an arbitrary element in $A$; when defining $f$ through induction as following $$\begin{array}{l} f(1) = a_1 \\ f(n) = \textrm{arbitrary element of } A-f(\{1,2,...,n-1\}) \quad \textrm{; for }n>1 \end{array}$$ we can see there are infinite possible choices of the images $a_i$ that meets the above formula, then there exists at least one function $f$, which is injective because of its definition. Munkres uses the axiom of choice to satisfy the hyphotheses for the principle of recursive definition, so he can ensure such function (one which he defines with help of the function of choice) is unique. Although I cannot ensure this, I would say what I did is enough to prove the impication. Is this a valid argument, or is there any lack of rigor in it?
Thanks in advance!

• "... and we choose the set $B$ to ....". What guarantees the existence of an object that you can choose? – Lee Mosher Aug 1 '16 at 1:59
• Of course many people think AC is obvious. But when Zermelo (then Frenkel) wrote down axioms for set theory, this didn't follow from them. So it was added as an additional axiom. – GEdgar Aug 1 '16 at 2:04
• You are (implicitly) using the axiom of choice to argue that the axiom of choice is a theorem rather than an axiom. Seems like a circular way of arguing. – John Coleman Aug 1 '16 at 2:07
• Furthermore, what you wrote about "even if the sets in $\mathcal A$ are not pairwise disjoint" has an easy counterexample. Suppose $\mathcal A=\{\{1,2\},\{1,3\},\{2,3\}\}$. No set contains exactly one element from each of the sets in $\mathcal A$. – Andreas Blass Aug 1 '16 at 5:10
• When you take an arbitrary subset with some properties, what you really do is first prove such a subset exists, then you use existential instantiation to give a name to such subset. This is not the axiom of choice that is being used, it is the rules of logic, but you first prove that there are subsets with the desired property to begin with. – Asaf Karagila Aug 12 '16 at 5:25

## 3 Answers

The key issue is that you're saying we "choose" the set $B$ to contain one element from each member of $\mathcal{A}$, but you're not specifying which elements these are. For a finite collection $\mathcal{A}$, this is no problem - there's always a finite list of instructions that could be specified, if one cared to take the time.

But for an infinite collection $\mathcal{A}$, it's not a consequence of ZF that you can make these choices - the way I think of it is that there's no way to finitely describe a process that selects one element from each set. Since ZF is in a language that can only finitely define things, ZF can't be sure that the sequence of choices can happen.

Now, many people would say that despite this the Axiom of Choice is still obviously true, which is why ZFC includes it as an axiom - Pairing is similarly trivial, for example. The weird thing is that the Axiom of Choice has weird consequences, like the Banach-Tarski Paradox, which made people suspect it might be false.

• Regarding the last paragraph, an old math joke (which Wikipedia attributes to Jerry Bona) is perhaps relevant: "The Axiom of Choice is obviously true, the well-ordering principle obviously false, and who can tell about Zorn's lemma?" – Semiclassical Aug 1 '16 at 2:51

The axiom of choice makes sense in the context of an axiomatic system describing a form of the notion of sets. You say

if we have the collection of sets A and we choose the set B to contain only one element from each set in A ...

but in the context of a fixed axiomatic system, like ZF, you can only do what the axioms let you do. The problem is, the axioms of ZF do not, directly or indiectly, let you do this choosing that you are planning to do. Zermelo and friends suspected this, so that is why they added AC to the list of axioms, but later it was actually proved that AC does not follow from ZF.

Yes, this is an error in reasoning. And also lack of rigor.

First of all, if $B\subseteq A$ for some $A\in\cal A$, then $B\subseteq\bigcup\cal A$, rather than $B\in\bigcup\cal A$. Secondly, unless each $A$ was already a singleton, you don't have an obvious choice for $B$. Moreover, even if for each $A$ there is an obvious choice, it does not mean that there is a uniform way for defining this obvious choice.

So when you say for each $A$ let $B$ be some singleton such that $B\subseteq A$, you already appealed to the axiom of choice in its full power.

• I realised I wrote $B\in\bigcup_{A\in\mathcal{A}}A$. I wanted to say $B\subseteq \bigcup_{A\in\mathcal{A}}A$. Thanks for making me notice it.What do you mean when you say there is no obvious choice for B if each $A$ is a singleton? Wouldn't $B=\bigcup A$ be the only option? – Carlens Aug 1 '16 at 14:12
• Unless means "except for the case". – Asaf Karagila Aug 1 '16 at 15:10