14
$\begingroup$

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
    This only depends on how you formulate the axiom of choice.2012-01-21

1 Answers 1

23

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.

  • 0
    Thank you. I'm very impressed. This was very helpful.2012-01-21
  • 0
    Indeed, $\prod_{i \in I} X_i$ is precisely the set of choice functions for the family $\{X_i : i \in I\}$.2012-01-21
  • 0
    How about proving the equivalent statement "the Cartesian Product of any family is empty only if a member of the family is empty"?2012-01-21
  • 1
    @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.2012-01-21
  • 0
    Is it obvious because that is the definition of the Cartesian Product?2012-01-21
  • 0
    @mathNotebook: Yes. $x\in A\times B$ if and only if $x=\langle a,b\rangle$ and $a\in A, b\in B$. If $B=\varnothing$ then there is no such $b$, therefore the product is empty.2012-01-21
  • 0
    This formulation of the Cartesian Product is new to me. I'll need to study it some more. Thanks again.2012-01-21
  • 0
    @mathNotebook: I'm confused... how do you define products if not using ordered pairs (or tuples)?2012-01-21
  • 0
    I define them using ordered pairs. I'm just not familiar with this:2012-01-21
  • 0
    "Indeed as Nate comments, it is most common to define the product ∏i∈IXi as the set of functions f:I→⋃{Xi∣i∈I} such that f(i)∈Xi for all i∈I."2012-01-21
  • 0
    I've been asking these questions about set theory because I've come across someone online who believes that by restricting multiplication by 0 to the finite cardinals he can prove the continuum hypothesis. I think he is completely wrong about this. But it got me curious about what the consequences of such a restriction would be. Based on the last few threads, I believe that, in such a system, it is impossible to formulate the Axiom of Choice. (Among other issues)2012-01-21
  • 0
    But, apart from that, these proofs are interesting in their own right. I was an applied mathematician and this is the first time I've really looked a infinite cardinals.2012-01-21
  • 3
    @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.2012-01-21
  • 0
    Thanks. Your replies have been incredibly helpful.2012-01-21