8.1 Axiom of Choice

The axiom of choice is an additional principle of set theory which says that, given any family of nonempty sets, it is possible to choose one element from each set in the family. The statement sounds simple, but it has deep consequences because it applies even when the family is infinite and no explicit rule for making the choices is given.

In ordinary finite mathematics, choosing one element from each of several nonempty sets causes no difficulty, because the choices can be made one after another. The axiom of choice becomes important when there may be infinitely many sets and no definable procedure is available for selecting the elements.

Indexed Families

Before stating the axiom, we fix the language used to describe a family of sets.

Definition 8.1 (Indexed Family)

An indexed family of sets is a function:

A : I \to V

where $I$ is a set, and for each $i \in I$ , the value $A(i)$ is a set.

We usually write:

A_i

instead of $A(i)$ , and we write the family as:

(A_i)_{i \in I}

The set $I$ is called the index set, and each $A_i$ is called a member of the family.

The family is nonempty pointwise if:

A_i \ne \varnothing

for every $i \in I$ .

This means that every set in the family contains at least one element, although the elements may be different for different indices.

Definition 8.2 (Choice Function)

Let $(A_i)_{i \in I}$ be an indexed family of nonempty sets. A choice function for this family is a function:

f : I \to \bigcup_{i \in I} A_i

such that:

f(i) \in A_i

for every $i \in I$ .

Thus a choice function selects one element from each set $A_i$ .

The condition $f(i) \in A_i$ is the essential part of the definition. It says that the chosen value at index $i$ must actually come from the set indexed by $i$ .

Axiom 8.3 (Axiom of Choice)

For every indexed family $(A_i)_{i \in I}$ of nonempty sets, there exists a choice function:

f : I \to \bigcup_{i \in I} A_i

such that:

f(i) \in A_i

for every $i \in I$ .

Equivalently, if every $A_i$ is nonempty, then one can choose an element:

a_i \in A_i

for every $i \in I$ .

The axiom does not provide a formula for $a_i$ . It only asserts that a function making all these choices exists.

Example 8.4 (A Finite Family)

Let:

A_1 = \{2,4,6\}, \quad A_2 = \{1,3,5\}, \quad A_3 = \{0,10\}

A choice function may be defined by:

f(1)=2, \quad f(2)=3, \quad f(3)=0

This is a choice function because:

2 \in A_1, \quad 3 \in A_2, \quad 0 \in A_3

No special axiom is needed here, because there are only finitely many choices to make.

Example 8.5 (A Family with a Definable Choice Rule)

Let:

A_n = \{m \in \mathbb{N} : m > n\}

for each $n \in \mathbb{N}$ .

Each $A_n$ is nonempty. A choice function is:

f(n)=n+1

Indeed:

n+1 \in A_n

for every $n \in \mathbb{N}$ .

This example also does not require the full strength of the axiom of choice, because a concrete rule for choosing elements is available.

Example 8.6 (Where Choice Becomes Nontrivial)

Suppose $(A_i)_{i \in I}$ is an arbitrary family of nonempty sets, and suppose no ordering, rule, or additional structure is given on the sets $A_i$ .

For each $i$ , the statement:

A_i \ne \varnothing

says that there exists some element of $A_i$ .

However, the separate assertions:

\forall i \in I,\ \exists x,\ x \in A_i

do not by themselves give a single function $f$ satisfying:

\forall i \in I,\ f(i) \in A_i

The axiom of choice is precisely the principle that allows us to pass from these many separate existence statements to one simultaneous choice function.

The Product Form

The axiom of choice is often stated using Cartesian products.

Definition 8.7 (Product of a Family of Sets)

Let $(A_i)_{i \in I}$ be an indexed family of sets. The product of the family is:

\prod_{i \in I} A_i = \{f : I \to \bigcup_{i \in I} A_i : f(i) \in A_i \text{ for every } i \in I\}

An element of:

\prod_{i \in I} A_i

is exactly a choice function for the family $(A_i)_{i \in I}$ .

Thus the product is the set of all possible simultaneous choices.

Proposition 8.8 (Product Form of the Axiom of Choice)

The axiom of choice is equivalent to the statement that for every indexed family $(A_i)_{i \in I}$ , if:

A_i \ne \varnothing

for every $i \in I$ , then:

\prod_{i \in I} A_i \ne \varnothing

Proof

Assume the axiom of choice. Let $(A_i)_{i \in I}$ be a family of nonempty sets. By the axiom of choice, there exists a function $f$ such that:

f(i) \in A_i

for every $i \in I$ . By the definition of the product, this function $f$ is an element of:

\prod_{i \in I} A_i

Therefore:

\prod_{i \in I} A_i \ne \varnothing

Conversely, assume that every product of a family of nonempty sets is nonempty. Let $(A_i)_{i \in I}$ be a family of nonempty sets. By the assumed product statement:

\prod_{i \in I} A_i \ne \varnothing

so there exists an element:

f \in \prod_{i \in I} A_i

By the definition of the product, this means that $f$ is a function with domain $I$ and:

f(i) \in A_i

for every $i \in I$ . Hence $f$ is a choice function for the family. This is exactly the axiom of choice.

Finite Choice

Finite choice can be proved without the axiom of choice. This is important because it separates ordinary finite selection from the stronger infinite principle.

Proposition 8.9 (Choice for Two Sets)

If $A$ and $B$ are nonempty sets, then there exists a function:

f : \{0,1\} \to A \cup B

such that:

f(0) \in A

and:

f(1) \in B

Proof

Since $A$ is nonempty, there exists an element:

a \in A

Since $B$ is nonempty, there exists an element:

b \in B

Define:

f(0)=a

and:

f(1)=b

Then $f$ is a function with domain $\{0,1\}$ , and it satisfies:

f(0) \in A \quad \text{and} \quad f(1) \in B

as required.

Proposition 8.10 (Finite Choice)

Let $n \in \mathbb{N}$ , and let:

A_0, A_1, \dots, A_{n-1}

be nonempty sets. Then there exists a function:

f : \{0,1,\dots,n-1\} \to \bigcup_{k<n} A_k

such that:

f(k) \in A_k

for every $k<n$ .

Proof

We prove the statement by induction on $n$ .

For $n=0$ , the index set is empty. The empty function is a function from the empty set to the empty union, and it vacuously satisfies the condition that $f(k) \in A_k$ for every $k<0$ , since there are no such indices.

Assume the statement holds for $n$ . Let:

A_0, A_1, \dots, A_n

be nonempty sets. By the induction hypothesis, there exists a function:

f : \{0,1,\dots,n-1\} \to \bigcup_{k<n} A_k

such that:

f(k) \in A_k

for every $k<n$ .

Since $A_n$ is nonempty, there exists:

a_n \in A_n

Define a new function $g$ on $\{0,1,\dots,n\}$ by:

g(k)=f(k)

for $k<n$ , and:

g(n)=a_n

Then $g(k) \in A_k$ for every $k<n$ by the induction hypothesis, and $g(n) \in A_n$ by the choice of $a_n$ . Hence:

g(k) \in A_k

for every $k \le n$ .

Therefore the statement holds for $n+1$ , and the result follows by induction.

Countable Choice

A weaker form of the axiom of choice is countable choice.

Definition 8.11 (Countable Choice)

The axiom of countable choice says that every countable family of nonempty sets has a choice function.

In symbols, if:

(A_n)_{n \in \mathbb{N}}

is a family of nonempty sets, then there exists a function:

f : \mathbb{N} \to \bigcup_{n \in \mathbb{N}} A_n

such that:

f(n) \in A_n

for every $n \in \mathbb{N}$ .

Countable choice is weaker than the full axiom of choice because it only applies to families indexed by the natural numbers.

Proposition 8.12

The axiom of choice implies countable choice.

Proof

Assume the axiom of choice. Let:

(A_n)_{n \in \mathbb{N}}

be a countable family of nonempty sets.

This is an indexed family whose index set is:

\mathbb{N}

Since each $A_n$ is nonempty, the axiom of choice gives a choice function:

f : \mathbb{N} \to \bigcup_{n \in \mathbb{N}} A_n

such that:

f(n) \in A_n

for every $n \in \mathbb{N}$ .

This is exactly the statement of countable choice.

Choice and Surjections

The axiom of choice is also closely related to right inverses of surjective functions.

Definition 8.13 (Right Inverse)

Let:

f : X \to Y

be a function. A right inverse of $f$ is a function:

g : Y \to X

such that:

f(g(y))=y

for every $y \in Y$ .

Equivalently:

f \circ g = \mathrm{id}_Y

A right inverse chooses, for each $y \in Y$ , one element of the fiber over $y$ .

Proposition 8.14

Assume the axiom of choice. Every surjective function has a right inverse.

Proof

Let:

f : X \to Y

be a surjective function. For each $y \in Y$ , define the fiber:

X_y = \{x \in X : f(x)=y\}

Since $f$ is surjective, for every $y \in Y$ there exists $x \in X$ such that:

f(x)=y

Therefore:

X_y \ne \varnothing

for every $y \in Y$ .

The family:

(X_y)_{y \in Y}

is therefore a family of nonempty sets indexed by $Y$ . By the axiom of choice, there exists a choice function:

g : Y \to \bigcup_{y \in Y} X_y

such that:

g(y) \in X_y

for every $y \in Y$ .

Since $g(y) \in X_y$ , by the definition of $X_y$ we have:

f(g(y))=y

for every $y \in Y$ .

Thus:

f \circ g = \mathrm{id}_Y

Hence $g$ is a right inverse of $f$ .

Proposition 8.15

If every surjective function has a right inverse, then the axiom of choice holds.

Proof

Assume that every surjective function has a right inverse.

Let:

(A_i)_{i \in I}

be a family of nonempty sets. We must construct a choice function.

Define:

X = \{(i,a) : i \in I \text{ and } a \in A_i\}

Define:

\pi : X \to I

by:

\pi(i,a)=i

We claim that $\pi$ is surjective. Let $i \in I$ . Since $A_i$ is nonempty, there exists:

a \in A_i

Then:

(i,a) \in X

and:

\pi(i,a)=i

Thus every $i \in I$ is in the image of $\pi$ , so $\pi$ is surjective.

By assumption, $\pi$ has a right inverse:

s : I \to X

such that:

\pi(s(i))=i

for every $i \in I$ .

Since $s(i) \in X$ , there are elements $j \in I$ and $a \in A_j$ such that:

s(i)=(j,a)

But:

\pi(s(i))=i

and:

\pi(j,a)=j

Therefore:

j=i

So for each $i \in I$ , the value $s(i)$ has the form:

s(i)=(i,a_i)

for some:

a_i \in A_i

Define:

c(i)=a_i

Then:

c(i) \in A_i

for every $i \in I$ , and therefore $c$ is a choice function for the family $(A_i)_{i \in I}$ .

Hence the axiom of choice holds.

Corollary 8.16

The axiom of choice is equivalent to the statement that every surjective function has a right inverse.

Proof

Proposition 8.14 shows that the axiom of choice implies that every surjective function has a right inverse. Proposition 8.15 shows that if every surjective function has a right inverse, then the axiom of choice holds. Therefore the two statements are equivalent.

Choice and Families of Pairwise Disjoint Sets

The axiom of choice is often easiest to picture when the sets in the family are pairwise disjoint.

Definition 8.17 (Selector)

Let $\mathcal{A}$ be a set whose members are nonempty sets. A selector for $\mathcal{A}$ is a set $S$ such that:

|S \cap A| = 1

for every $A \in \mathcal{A}$ .

Thus $S$ contains exactly one element from each member of $\mathcal{A}$ .

Proposition 8.18

Assume the axiom of choice. Every set of pairwise disjoint nonempty sets has a selector.

Proof

Let $\mathcal{A}$ be a set of pairwise disjoint nonempty sets.

By the axiom of choice, there exists a function:

f : \mathcal{A} \to \bigcup \mathcal{A}

such that:

f(A) \in A

for every $A \in \mathcal{A}$ .

Let:

S = \{f(A) : A \in \mathcal{A}\}

We show that:

|S \cap A| = 1

for every $A \in \mathcal{A}$ .

First, since $f(A) \in A$ and $f(A) \in S$ , we have:

f(A) \in S \cap A

Thus $S \cap A$ is nonempty.

Now suppose:

x \in S \cap A

Since $x \in S$ , there exists $B \in \mathcal{A}$ such that:

x=f(B)

Since $f(B) \in B$ , we have:

x \in B

Also $x \in A$ . Therefore:

x \in A \cap B

Because the members of $\mathcal{A}$ are pairwise disjoint, this implies:

A=B

Hence:

x=f(A)

So the only element of $S \cap A$ is $f(A)$ , and therefore:

|S \cap A| = 1

Why the Axiom Is Not Merely a Definition

The axiom of choice does not define a choice function. It asserts that such a function exists.

This distinction matters. If the family has a natural rule for choosing, then a choice function can often be explicitly defined. For example, every nonempty subset of $\mathbb{N}$ has a least element, so for a family of nonempty subsets of $\mathbb{N}$ one may define:

f(A)=\min A

In that case, no use of the full axiom of choice is needed, because the ordering of $\mathbb{N}$ provides a concrete selection rule.

For arbitrary sets, there may be no given ordering, no canonical representative, and no definable way to select an element. The axiom of choice asserts that a global selection function nevertheless exists.

Example 8.19 (Choosing from Nonempty Subsets of Natural Numbers)

Let $\mathcal{A}$ be a set of nonempty subsets of $\mathbb{N}$ . Define:

f(A)=\min A

for each $A \in \mathcal{A}$ .

This is a choice function because every nonempty subset of $\mathbb{N}$ has a least element.

Proof

Let $A \in \mathcal{A}$ . Since $A$ is a nonempty subset of $\mathbb{N}$ , the well ordering property of $\mathbb{N}$ implies that $A$ has a least element.

Therefore:

\min A \in A

By definition:

f(A)=\min A

Thus:

f(A) \in A

Since this holds for every $A \in \mathcal{A}$ , the function $f$ is a choice function.

Example 8.20 (Choosing from Nonempty Finite Sets of Natural Numbers)

Let $\mathcal{A}$ be a family of nonempty finite subsets of $\mathbb{N}$ . The same rule:

f(A)=\min A

defines a choice function.

The finiteness of the sets is not needed here, because every nonempty subset of $\mathbb{N}$ has a least element. The important point is that $\mathbb{N}$ has a fixed well ordering.

Dependence on the Background Theory

In Zermelo Fraenkel set theory, usually abbreviated ZF, the axiom of choice is not included by default. When the axiom of choice is added to ZF, the resulting theory is called ZFC.

Thus:

\mathrm{ZFC} = \mathrm{ZF} + \mathrm{AC}

Many ordinary theorems in algebra, topology, and analysis use some form of choice, sometimes explicitly and sometimes indirectly. For example, the statement that every vector space has a basis requires the axiom of choice in full generality.

The axiom of choice is therefore both a set theoretic principle and a practical tool for large parts of modern mathematics.