# Axiom of Choice (Naive Set Theory, Halmos)

I'm currently reading Naive Set Theory by Paul Halmos and I'm not quite understanding what he means in sec. 15, The Axiom of Choice.

Suppose that $\mathscr{C}$ is a non-empty collection of non-empty sets. We may regard $\mathscr{C}$ as a family, or, to say it better, we can convert $\mathscr{C}$ into an indexed set, just by using the collection $\mathscr{C}$ itself in the role of the index set and using the identity mapping on $\mathscr{C}$ in the role of the indexing.

This much I understand, essentially $\mathscr{C}_{x}=x$ (correct me if I'm wrong).

The axiom of choice says that the Cartesian product of the sets of $\mathscr{C}$ has at least one element. An element of such a Cartesian product is, by definition, a function (family, indexed set) whose domain is the index set (in this case $\mathscr{C}$) and whose value at each index belongs to the set bearing that index. Conclusion: there exists a function $f$ with domain $\mathscr{C}$ such that if $A \in \mathscr{C}$, then $f(A) \in A$.

I'm a little confused by the manner in which we define the Cartesian product of a family of three sets or more. Do we define it as $A \times B \times C = \{(a,b,c) \; \; | \; \; a \in A , b \in B, c \in C\}$?

My understanding was that a function consists of only ordered pairs, am I missing something here? Any help would be appreciated, thanks!

• I feel that I've covered this exact issue not long ago in an answer. – Asaf Karagila May 6 '14 at 19:18
• math.stackexchange.com/questions/733817/…, does this possibly answer your question? I think it might. – Asaf Karagila May 6 '14 at 19:19
• This is also very useful, thanks for providing me with the link to your answer. – Fizzle May 6 '14 at 21:15

The set theoretic definition of an ordered pair is not such that allow a nice generalization for ordered tuples. So in order to define $A\times B\times C$ we need to choose, $A\times(B\times C)$ or $(A\times B)\times C$. Truly it doesn't matter one bit, since there is a very natural bijection between the two sets.

But then we move to longer and longer and longer products. And finally to infinite products, which we cannot even represent as repeated Cartesian products.

Instead we define a notion of $I$-tuples, where $I$ is any index set: If $I$ is our index set, and for every $i\in I$ we match some $A_i$, then the product $\prod_{i\in I}A_i$ is all the functions whose domain is $I$ and $f(i)\in A_i$. Then we redefine the product as the set of $2$-tuples, and product of three sets as $3$-tuples and so on. In the case of $A\times B\times C$ we have $I=\{0,1,2\}$ and $A_0=A,A_1=B,A_2=C$.

This notion also generalizes to infinite index sets quite easily, so we can define $I$-tuples when $I$ is any set.

But note that if $I$ is given, and $A_i$ are given, and all are non-empty, then an $I$-tuple is really a choice function on the family $\{A_i\mid i\in I\}$. And the axiom of choice really just says that given any such family their product is non-empty, that is to say that there is some choice function on this family.

If the family is finite, then we can prove this without using the axiom of choice. It's quite easy. But if the family is infinite, then we can prove that we have to use the axiom of choice to prove that their product is non-empty.

Note that, for your example, one can define

$$A\times B\times C:=\left\{\;f:\{1,2,3\}\to A\cup B\cup C\;\;:\;\;f(1)\in A\;,\;f(2)\in B \;,\;f(3)\in C\;\right\}$$

The above, of course, is way more cumbersome than the usual definition you wrote since this is a finite, easy-to-grasp, example.

Thus, in your example, the element $\;(a,b,c)\;$ would be represented by the function

$$f:\{1,2,3\}\to A\cup B\cup C\;\;s.t.\;\; f(1)=a\in A\;,\;\;f(2)=b\in B\;,\;\;f(3)=c\in C$$

• Great example! Thanks for that, that's very helpful. – Fizzle May 6 '14 at 20:07