I'm currently trying to write a paper on the Axiom of Choice. With my research I have found one very simple definition of the Axiom of Choice : "Let X be a non-empty set of non-empty sets. There exists a choice function for X." This seems intuitive to me and I feel like I can understand this from the classic shoes and socks example. But I am also seeing the Axiom of Choice defined as: "The Cartesian Product of a nonempty family of nonempty sets is nonempty." This seems less easy to understand at first glance, but reading further I understand how this could make sense. The issue is, I'm struggling to connect these two definitions. In my head I see them as two separate statements, each making sense individually. Is there an easy example to understand the Cartesian Product Definition, like can I relate it back to the sock and shoe example?
Connection between the many different definitions of the Axiom of Choice
axiom-of-choiceaxiomselementary-set-theoryset-theory
Related Solutions
In both examples you are given an infinite family of sets of size 2, and a choice function picks an element of each family. In the case of the sets of shoes, each set comes with an ordering (left, right), and so we can define a choice function explicitly. In the case of pairs of socks, this is not the case: Of course, given any pair, we can assign an ordering to it so we can select one of the two socks. However, there is no obvious way of uniformly doing this for all pairs at the same time. This means (at least intuitively) that there is no way of defining a choice function. Its existence can only be granted by applying the axiom of choice.
There are several variants of this example. One that may be useful to think about is the following: One can show explicitly that if $A_n$ is a set of reals and $|A_n|=2$ for each $n\in{\mathbb N}$, then $\bigcup_n A_n$ is a (finite or infinite) countable set. However, it is consistent with the axioms of set theory except choice that there is a sequence $(A_n\mid n\in{\mathbb N})$ of sets, each $|A_n|=2$, and yet $\bigcup_n A_n$ is not countable. Although the construction of the model where this happens is technical, the point is that this formalizes the intuition that there is no "explicit" way of choosing a sock from each pair, simultaneously, and that any way of doing so is essentially non-constructive.
For more on the set theoretic versions of these collections of socks (Russell cardinals), see here.
The main challenge here is explaining the precise set-theoretic statement which is meant by "we can make finitely many choices without the axiom of choice"; the proof is then relatively easy. I am going to write in a sort of semi-formal way, which I hope will be clear enough that you can see how to translate into statements of ZF.
By CHOICE, I mean the statement:
Let $X$ and $Y$ be sets, with a map $\pi: X \to Y$. Suppose that, for every $y \in Y$, there is an $x \in X$ with $\pi(x) = y$. Then there is a subset $K$ of $X$ such that, for every $y \in Y$, there is a unique $x \in K$ with $\pi(x) = y$
So $X$ is the set we are choosing from (the set of all socks in the universe), $Y$ is the number of choices we're making, and $K$ is the set of choices we make.
Now, I want to show that this statement is true if $Y$ is finite. So we must discuss the definition of finite.
For any set $Z$, define $s(Z) = Z \cup \{ Z \}$. A set $I$ is called inductive if $\emptyset \in I$ and if, for all $Z \in I$, we also have $s(Z) \in I$. One can show (see any intro set theory book) that there is a unique set $\mathbb{N}$ such that (1) $\mathbb{N}$ is inductive and (2) every inductive set contains $\mathbb{N}$. A set $Y$ is called finite if it can be put in bijection with some member of $\mathbb{N}$.
We have now finished the definitions, and can move to the proof. We are going to show that, if $A \in \mathbb{N}$, if there is a bijection $Y \to A$, and if we have any map $\pi: X \to Y$ satisfying the hypotheses of CHOICE, then the conclusion of CHOICE holds.
First of all, composing $\pi: X \to Y$ with the bijection $Y \to A$, we may assume that $Y$ is an element of $\mathbb{N}$. (Exercise!)
Let's say that "we may make $Y$ choices" if CHOICE is true for $Y$, for all $\pi$ and $X$. Let $T \subseteq \mathbb{N}$ be the set of those elements $Y$ of $\mathbb{N}$ for which we can make $Y$ choices. (Exercise: Actually write out the definition of $T$ set theory notation.) We will show that $T$ is inductive.
First of all, we can make $\emptyset$ choices. Take $K = \emptyset$.
Now, suppose that we can make $Z$ choices. We must show that we can make $s(Z)$ choices. Consider any map $\pi: X \to s(Z)$. Let $X' = \pi^{-1}(Z)$, using the inclusion $Z \subseteq s(Z)$. So, by hypothesis, there is a subset $K' \subseteq X'$ such that, for every $y \in Z$, there is a unique element $x \in K'$ with $\pi(x) = y$. Also, by the hypotheses of AC, there is an element $x \in X$ such that $\pi(x) = \{ Z \}$. Take $K = K' \cup \{ x \}$.
We have now shown that $T$ is inductive, so $\mathbb{N} \subseteq T$. But also $T \subseteq \mathbb{N}$, by construction. So $T = \mathbb{N}$. We have shown that we can make $Y$ choices for every $Y \in \mathbb{N}$, as desired.
By the way, you may notice that this proof looks a lot like a proof by induction. This is how you write a proof by induction in ZF. Set theorists writing for a more experienced audience would just say "do it by induction", without all the explanation I've given.
Best Answer
($X$ and $I$ will denote sets throughout.)
You are probably used to interpreting $X^{n}$ as the set of $n$-tuples $(x_{1}, \ldots, x_{n})$ such that each $x_{i}$ is in $X$.
However, an equivalent way of interpreting this is as the set of all functions $\{1, \ldots, n\} \to X$. Indeed, $(x_{1}, \ldots, x_{n}) \in X^{n}$ corresponds to the function $i \mapsto x_{i}$, whereas a function $f : \{1, \ldots, n\} \to X$ corresponds to the tuple $(f(1), \ldots, f(n))$.
In general, given sets $X_{1}, \ldots, X_{n}$, you can interpret $X_{1} \times \cdots \times X_{n}$ either as the set of $n$-tuples or as the set of functions $\{1, \ldots, n\} \to \bigcup_{i = 1}^{n} X_{i}$ such that $f(i) \in X_{i}$ for all $i \in I := \{1, \ldots, n\}$.
But this is precisely what a choice function is, for the collection $\{X_{1}, \ldots, X_{n}\} = \{X_{i} : i \in I\}$.
Once you have the above in place, it is easy to see how one would define an arbitrary product of sets. Indeed, let $\{X_{i} : i \in I\}$ be a collection of sets, where $I$ is arbitrary (let us assume it to be nonempty). Then, one defines $$\prod_{i \in I} X_{i} := \left.\left\{f : I \to \bigcup_{i \in I} X_{i} \;\right\vert f(i) \in X_{i} \text{ for all } i \in I\right\}.$$ In other words, $\prod_{i \in I} X_{i}$ is precisely the set of all choice functions. It should now be clear how the two versions of choice are equivalent (this is actually an equivalence by definition, not by any mathematical work).