I understand that the axiom of choice, given the axioms of ZF set theory, is equivalent to the statement that "the Cartesian product of any family of nonempty sets is nonempty." I've been unable to find this proof. Could someone sketch it for me? Or provide me with a source at least?

  • 3
    $\begingroup$ This only depends on how you formulate the axiom of choice. $\endgroup$ – Asaf Karagila Jan 21 '12 at 14:39

Suppose $X=\{X_i\mid i\in I\}$ is a family of nonempty sets.

If there exists a choice function, then $\langle f(i)\mid i\in I\rangle$ is an element of the product $\prod_{i\in I}X_i$.

If $\prod_{i\in I}X_i$ is nonempty then there is $f=\langle x_i\mid i\in I\rangle$ in this product, which is a sequence of $x_i$ such that $x_i\in X_i$. The function $f(i)=x_i$ is a choice function.

Indeed as Nate comments, it is most common to define the product $\prod_{i\in I}X_i$ as the set of functions $f:I\to\bigcup\{X_i\mid i\in I\}$ such that $f(i)\in X_i$ for all $i\in I$.

One can easily observe that under this definition the product is exactly the set of choice functions, therefore the product is nonempty if and only if there exists a choice function.

  • $\begingroup$ Thank you. I'm very impressed. This was very helpful. $\endgroup$ – mathNotebook Jan 21 '12 at 14:52
  • $\begingroup$ Indeed, $\prod_{i \in I} X_i$ is precisely the set of choice functions for the family $\{X_i : i \in I\}$. $\endgroup$ – Nate Eldredge Jan 21 '12 at 14:55
  • $\begingroup$ How about proving the equivalent statement "the Cartesian Product of any family is empty only if a member of the family is empty"? $\endgroup$ – mathNotebook Jan 21 '12 at 15:00
  • 1
    $\begingroup$ @mathNotebook: Once one of the members of the family is empty the product is obviously empty; on the other hand if they are all nonempty then we return to this formulation as above. $\endgroup$ – Asaf Karagila Jan 21 '12 at 15:04
  • 3
    $\begingroup$ @mathNotebook: I see. The reason products are defined in such way is that you have ordered pairs, and triplets, but what happens when your index set is infinite? It's impossible to write a formula saying that you have a $\kappa$-tuple, instead we just write it as a function from $\kappa$ into the sets. As for the crank you ran into... I wouldn't worry too much about it, people who misunderstand set theory and infinite sets are as common as rhinovirus, and twice as annoying. $\endgroup$ – Asaf Karagila Jan 21 '12 at 15:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.