The axiom of choice guarantees that every collection of disjoint non-empty sets has at least one choice function.

Intuitively, a stronger result holds. We expect that the number of choice functions on a collection of disjoint sets is equal to the cardinality of the Cartesian product of that collection.

Given the ZFC axioms, does the Axiom of Choice also imply this expected statement?

  • 1
    $\begingroup$ 'disjoint' is not needed in the formulation of AC: Every collection of non-empty sets admits a choice function. $\endgroup$ – Ittay Weiss Feb 2 '13 at 0:50

The product of the sets is the set of choice functions. This is how we define it. Of course they have the same cardinality, the two collections have the same elements.

To see this, note that when we simply take a product of two sets then we think about it as ordered pairs, or ordered tuples in the case of three, or four, or whatever finite number you can think of. However how do you write an infinite tuple? What is exactly the definition of an infinite tuple?

Well, we can think of an $I$-tuple is a function from $I$ into some non-empty set. In particular if we take the product of $A_i$ then we require the $i$-th "coordinate" of the $I$-tuple to be a member of $A_i$, then we can think about an $I$-tuple as a function $f$ from $I$ into $\bigcup_{i\in I}A_i$ such that $f(i)\in A_i$ for all $i$.

If the product is the collection of all $I$-tuples, then it is exactly the set of choice functions.

On a side note, we don't even care if the sets are disjoint or not. The product is invariant under definable bijections, and we can always replace $A_i$ with $A_i'=\{i\}\times A_i$. The product of $A_i$ has a bijection with the product of the $A_i'$, and the existence of this bijection does not depend on the axiom of choice.

| cite | improve this answer | |
  • $\begingroup$ Makes sense. Quick question: Is the cartesian product of the indexed collection $\{A_i\}_{i\in\mathbb{N}}$ equinumerous with $A_0 \times \{A_i\}_{i\in\mathbb{N}\setminus\{0\}}$ $\endgroup$ – goblin GONE Feb 2 '13 at 0:24
  • $\begingroup$ Do you mean with the product of $A_0$ with the product of the remainder? Yes, there is an obvious bijection between the two sets. $f\in\prod_{n\in\Bbb N}A_n$ is mapped to $\langle f(0),f\upharpoonright\mathbb N\setminus\{0\}\rangle$. $\endgroup$ – Asaf Karagila Feb 2 '13 at 0:26
  • $\begingroup$ Yeah, that's what I meant. $\endgroup$ – goblin GONE Feb 2 '13 at 0:53

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.