# The axiom of choice - when and why to use it

I am a bit confused because I don't fully understand when the axiom of choice can be used and when it cannot. Here is the definition of AC that interests me - it relies purely on sets (and importantly for me, it does not use the concept of functions):

For every family $$S$$ of non-empty disjoint sets, there exists a set $$V$$ (a so-called "selector"), which contains exactly one element from each of the sets belonging to the family $$S$$..

Formally: $$\forall_{S} \Big\{\big[\forall_{X \in\, S} X \ne \varnothing\big]\! \land\! \big[\forall_{X, Y \in\, S}\, (X \ne Y \Rightarrow X \cap Y = \varnothing)\big] \Rightarrow \exists_V \forall_{X \in\, S}\, \exists_x \big(X \cap V = \{x\}\big)\Big\}$$

### Notation:

$$(a,b) = \{a, \{a,b\}\}$$ - Kuratowski short ordered pair for elements

$$(a;b)$$ - Open interval in $$\mathbb R$$

(i.e., , denotes a pair, and ; denotes an interval)

$$[a;b]$$ - Closed interval in $$\mathbb R$$

$$(a_i)_{i=1}^{n}=(a_1,a_2,...,a_n) = \{ (1,a_1), (2,a_2), (3,a_3),..., (n,a_n)\}$$ , for $$n>2$$ - Finite sequence

$$(a_i)_{i=1}^{\infty}=(a_1,a_2,...) = \{ (1,a_1), (2,a_2), (3,a_3),...\}$$ , for $$n>2$$ - Infinite sequence

$$\mathbb Z'$$ is a certain subset of $$\mathbb Z$$, $$\mathbb R'$$ is a certain subset of $$\mathbb R$$

### Description

Now let me cite the following examples of families of sets:

\begin{align} A &= \{ \{a\}: a \in \mathbb{Z}' \} \\ B &= \{ \{a,b\}: a,b \in \mathbb{Z}' \} \\ C_n &= \{ \{a_1, a_2,..., a_n\}: a_i \in \mathbb{Z}' \} \\ C &= \{ \{a_1, a_2,..., a_n\}: a_i \in \mathbb{Z}', n\in\mathbb{N} \} \\ D &= \{ \{a_1, a_2,...\}: a_i \in \mathbb{Z}', \} \\ \\ E &= \{ (a,b): a,b \in \mathbb{Z}' \} \\ F_n &= \{ (a_1,a_2,...,a_n): a_i \in \mathbb{Z}' \} \\ F &= \{ (a_1,a_2,...,a_n): a_i \in \mathbb{Z}', n\in\mathbb{N} \} \\ G &= \{ (a_1,a_2,...): a_i \in \mathbb{Z}' \} \\ \\ H &= \{ \{a\} : a\in\mathbb{R}' \} \\ I &= \{ (a;b) : a,b\in\mathbb{R}', a

For simplicity, we assume that from all these sets we remove elements that have a common part with other elements of this set (so as to use the definition of AC referring to disjoint sets)

Based on each of the above-defined sets (which contain information about a specific subset of $$\mathbb{Z}'$$ or $$\mathbb{R}'$$), I would like to generate a set $$X$$ containing exactly one element from each subset of the given set, e.g. $$X_A = \{ a: \exists b \in A, a\in b \}$$, or exactly one element from the pair/sequence, e.g., the first element from each pair in $$E$$ i.e. $$X_E = \{ a: \exists b \in E, a\in b \}$$

### Question

For the generation/creation of which sets $$X_A,X_B,X_C,X_D,X_E,X_F,X_G,X_H,X_I,X_J, X_K,X_L$$ will I need to use the axiom of choice and why?

Update:

What if $$\mathbb {Z}'$$ is special set where you cannot compare elements (and find minimal or center element) ? (we exclude cases H-L)

• See Axiom of Choice: "It is to be noted that AC for finite collections of sets are both provable (by induction) in the usual set theories. But in the case of an infinite collection, even when each of its members is finite, the question of the existence of a choice function is problematic. For example it is easy to come up with a choice function for the collection of pairs of real numbers (simply choose the smaller element of each pair). 1/2 Commented Jul 16 at 8:49
• But it is by no means obvious how to produce a choice function for the collection of pairs of arbitrary sets of real numbers." 2/2 Commented Jul 16 at 8:50
• I always saw the axiom of choice as being another one of these pseudo- big deals, like Russell's paradox and Godel incompleteness. You have a handful of paper labels and you walk past a bunch of barrels. They're all full of set elements. You stick one label on one object in each barrel. You can pick the blue ones, you can pick the even numbers, or you can close your eyes and play "pin the tail on the element." There's your choice. You can make it. I can't see how you could ever rationally disallow the axiom of choice. Commented Jul 16 at 19:27
• There are already many questions on this site and others on the merits of constructive mathematics and reasons for rejecting choice; this is a technical question about using the axiom of choice, so this is somewhat off-topic here. Commented Jul 16 at 19:31

Assuming excluded middle:

None of $$A$$, $$B$$, $$C_n$$, $$C$$, require choice since all of their members have a (unique) minimal element.

$$D$$ doesn't require choice either, as you can always pick the minimal element in absolute value (and if both $$a \in S$$ and $$-a \in S$$, pick the positive one).

Similarly, none of $$E$$, $$F_n$$, $$F$$, $$G$$ require choice since all of their members have a first component.

Similarly, none of $$H$$, $$I$$, $$J$$, $$K$$, $$L$$ require choice since all of their members have a "middle element", in the sense of $$S \mapsto \frac{\mathrm{inf}(S) + \mathrm{sup}(S)}{2}$$.

• I am not using AC, so your definition is irrelevant here. I am building a selector set directly. (Or rather, I am showing that AC holds for the specific instances of $S$ in your question.) You said $\mathbb{Z}' \subseteq \mathbb{Z}$ and $\mathbb{R}' \subseteq \mathbb{R}$, so their elements can be compared using the respective orders from $\mathbb{Z}$ and $\mathbb{R}$. Commented Jul 16 at 9:12
• You just pick the minimal element from every set and it gives you a selector set/choice function. This is sometimes called unique choice, non-choice or function comprehension; it's really nothing fancy. Commented Jul 16 at 9:21
• The only partial order you can meaningfully equip an arbitrary set X with without choice is the discrete partial order (equality), in which case X has a minimal element iff X has a unique element, so you've gained nothing. In case you're thinking of a well-order, then "every set is well-ordered" is equivalent to AC. Commented Jul 16 at 9:48
• Well, I just told you which order to use. I'm the one making the choice here! It's not a particularly far-fetched choice either, as it's just the restriction of the order on $\mathbb{Z}$ to $\mathbb{Z}'$. Commented Jul 16 at 10:14
• You could pick a different order if you like, and maybe choose the maximal element instead of minimal. The point is that you can write down a definite element of every subset. Commented Jul 16 at 10:19

Essentially, this answer is same as answer by Naïm Favier, but more technical.

Axiom of choice can be stated in terms of choice function:

$$\forall S\ \left(\emptyset\notin S\implies (\exists f\colon S\to \bigcup S)(\forall X\in S)\ f(X)\in X\right),$$ which sends each $$X\in S$$ to one of its elements.

Whether you need axiom of choice to prove existance of a choice function is simply a question whether you can explicitly write formula for at least one choice function or you can't. If you can, then you don't need the axiom, you already have choice function, but if you can't, you can invoke AC to state it's existence even if you have no idea what the function actually is.

To avoid problems with your sets not necessarily having pairwise-disjoint elements, let's simply write a choice function for each of those sets. To get set that you want, take the image of the choice function.

1. sets $$A,B,C_n,C,D$$

Let's first prove a lemma:

Let $$A$$ be a well-ordered set and $$S\subseteq \mathcal P(A)\setminus\emptyset$$, i.e. $$S$$ is a subset of power-set of $$A$$ not containing empty set. Then we can write a choice function $$f\colon S\to \bigcup S$$ by formula $$f(X) = \min X$$.

Proof. This is perhaps more obscure to write down then to prove. Any $$X\in S$$ is also element of $$\mathcal P(A)\setminus \emptyset$$, i.e. $$X$$ is a nonempty subset of well-ordered set $$A$$, and therefore there exists $$\min X\in X.\quad\square$$

Now, I will claim that $$\mathbb Z'$$ can be well-ordered and therefore we can write choice function for all $$A,B,C_n,C,D$$.

First, let's write down bijection $$a\colon\mathbb N\to\mathbb Z$$ $$a_n = \begin{cases} -\frac n2,& n\text{ even}\\ \frac{n+1}2,& n\text{ odd} \end{cases}$$ which realizes $$\mathbb Z = \{a_0,a_1,a_2,\ldots\} = \{0,1,-1,2,-2,\ldots\}$$, so define a well-ordering $$\preceq$$ on $$\mathbb Z$$ by $$a_n\preceq a_m \iff n\leq m.$$

This gives us a well-ordering of nonempty $$\mathbb Z'\subseteq\mathbb Z$$ simply by inheritance.

2. sets $$E,F_n,F,G$$

Under your definitions for tuples, define \begin{align} f_E((a,b)) &= a\in (a,b),\\ f_{F_n}((a_1,a_2,\ldots,a_n)) &= (1,a_1)\in (a_1,a_2,\ldots,a_n) \end{align} and same for others.

3. sets $$H,I,J,K,L$$

For $$I$$ and $$J$$, take $$f(\langle a,b\rangle) = \frac{a+b}2\in \langle a;b\rangle$$, where $$\langle,\rangle$$ is either $$(;)$$ or $$[;]$$ and the same formula will work for all others as well: for $$H$$ take $$b=a$$, for $$K,L$$ take $$b = a+1$$.

If $$\mathbb Z'$$ is arbitrary infinite set, we can't write down explicit choice function for $$B$$ to $$D$$ in general, but we can for $$E$$ to $$G$$, in the same way as we did above.

There is a famous parallel about choosing shoes and socks from infinitely many pairs. If you have infinitely many pairs of shoes, you can define a choice function by choosing left shoe each time, so we don't need axiom of choice in this case. If you have infinitely many pairs of socks, there is no clear way to distinguish one from another, so we need axiom of choice in this case.

If $$\mathbb Z'$$ is finite, then you can define well-ordering on $$\mathbb Z'$$ simply by exausting all of its elements one by one. Axiom of choice is just extension of this reasoning to infinite sets. When it comes to infinity, we can't derive existence of infinite sets from existence of finite ones, so we need axiom of infinity. Similarly, we can well-order finite sets easily, but we can't use that to well-order infinite sets, so we need axiom of choice (which is equivalent to well-ordering theorem).

Let $$X$$ be a two element set. In particular it is not empty, so $$\exists x\,(x\in X)$$ is true. By existential instantiation we can introduce a constant symbol $$a_X$$ for which we know $$a_X\in X$$ is true. In simpler terms, we know that there is at least one element in $$X$$, so we can name an element of $$X$$ with $$a_X$$. Now, let $$\{X_1,\ldots,X_n\}$$ be a finite set of two element sets $$X_i$$. In finite number of steps we can use existential instantiation to produce elements $$a_1,\ldots,a_n$$ such that $$a_i\in X_i$$. In that way we produced a choice function $$X_i\mapsto a_i\colon \{X_1,\ldots,X_n\}\to \bigcup_{i=1}^nX_i$$. The problem arises if we have infinite collection $$\{X_i\}_{i\in I}$$ because we can only produce finitely many elements $$a_i\in X_i$$ with the above procedure, so we can't produce choice function since our procedure never terminates. That doesn't mean that there isn't such a function, we just can't prove or disprove it using ZF alone (assuming it is consistant), just like using ZF without axiom of infinity we can't prove or disprove existence of set of natural numbers.
Going back to socks. Finite collection $$\{X_1,\ldots,X_n\}$$ is now all pair of socks in your drawer. Each day you take one pair out of drawer and you choose one to put it on your left foot and after the day ends, you throw it into dirty clothes bin. After $$n$$ days, you used up all of your pair of socks and now have to wash it. What you did is produce a choice function that picks a sock to put on your left foot out of all of your pair of socks. However, if you lived in a magical land where you had infinitely many pair of socks, you'd never have to wash any, and you'd never finish producing a choice function that picks a sock to put on your left foot for all of your infinitely many pairs.
Contrast this with arbitrary collection $$\{X_i\}_{i\in I}$$ where $$X_i$$ are again two element sets, but this time totally ordered. Now, you can simply define $$f\colon \{X_i\}_{i\in I} \to \bigcup_{i\in I} X_i$$ by formula $$f(X_i) = \min X_i$$.