Axiom of Choice and Cartesian Products

According to Wikipedia one formulation of AC is

The Cartesian product of any family of nonempty sets is nonempty.

If I consider an cartesian product $\prod_{i} X_i$ of nonempty sets $X_i$, then there exists some $x_i \in X_i$ for each $i$ (simply by non-emptiness), and so $x := (x_i)$ is an element of the product $\prod_i X_i$ by definition. This seems quite trivial to me... imposed by the rules of logic, so why state it as an axiom? Indeed to me it appears as there isn't needed any axiom at all, by setting $x := (x_i)$ I have actually constructed the element?

• You've canonically expressed the axiom of choice in your first sentence - for each $X_i$ there may exist an element $x_i$ in $X_i$, but you can't make the choice of all the (infinitely many!) $x_i$ in any 'canonical' fashion. Note that for any sets where you can make this choice (for instance, if there's an ordering on $X_i$ so you can say 'take the least $x_i$'), AC holds as a theorem and not just an axiom; the most common metaphor for explaining this seems to be a 'shoes vs. socks' formulation of the axiom, and you can probably find more information by searching for those words. – Steven Stadnicki Jan 2 '14 at 21:39

Your proof is not a proof, but rather an intuition why the AC should be true.

Recall the precise(!) definition of the product of a family of sets: $\prod_{i \in I} X_i$ consists of functions $f : I \to \bigcup_{i \in I} X_i$ such that $f(i) \in X_i$ for all $i \in I$. Also recall the definition of a function $A \to B$ as a special subset of $A \times B$.

Now, given non-empty sets $X_i$, how do you define such a function, using the other ZF axioms? You say, for every $i \in I$ we choose some element $x_i \in X_i$. This works for every single $i$ at a time, but this doesn't define a function $i \mapsto x_i$.

Example: Let $I$ be the set of all non-empty subsets of $\mathbb{R}$, and $X_i = i$. Then an element $f$ in $\prod_{i \in I} X_i$ is a function which picks an element $f(T) \in T$ for every non-empty $T \subseteq \mathbb{R}$. How do you define such an $f$? If we would have $\mathbb{N}$ instead of $\mathbb{R}$, we could take $f(T)=\min(T)$, but this doesn't work for $\mathbb{R}$. Apparently, there is no canonical choice of an element in a non-empty set of real numbers. But the AC tells us that we don't have to worry about this, it gives us such a function, even if we cannot "write it down" (which means: construct it from the other ZF axioms).

By the way, if we let $I$ be to be the set of all non-empty open subsets of $\mathbb{R}$, then there is a choice function (provably in ZF): Choose any bijection $\tau : \mathbb{N} \to \mathbb{Q}$, and then assign to each open subset $\emptyset \neq U \subseteq \mathbb{R}$ the element $\tau(\min \{n \in \mathbb{N} : \tau(n) \in U\})$. This works since $U \cap \mathbb{Q} \neq \emptyset$.

• thx for the many answers, but sorry I still did not see why $f(i) := x_i$ for some $x_i \in X_i$ is not a function, what exactly goes wrong here? This so defined $f$ is a subset of $I \times \bigcup X_i$ and $f(i) \in X_i$ by definition... – StefanH Jan 2 '14 at 22:16
• @Stefan: As I wrote in my answer, we cannot prove that sets exists "just like that". Consider Skolem's paradox, if $\sf ZFC$ is consistent, then it has a countable model $M$, therefore $\{x\mid M\models x\text{ is a real number}\}$ is countable, but we know that $M$ also thinks that this is an uncountable set. Paradoxical, ain't it? Well. Shucks, it just means that not every set that we want to exist will exist. To do so, we have to use axioms and inference rules to prove that it does. To prove that $f$ as you "defined" it exists, you have use the axiom of choice. – Asaf Karagila Jan 2 '14 at 22:35
• does that mean that there aren't any real numbers in the countable model $M$, i.e. $\{ x : M \models x \mbox{ is a real number } \} = \emptyset$ or that the notion of countable in $M$ is not the one we "expect intuitively"? – StefanH Jan 2 '14 at 23:27
• is my definition like defining $N$ to be the biggest natural number, which obvisouly is not well-defined because such number does not exists? – StefanH Jan 2 '14 at 23:35
• @Stefan: It is more similar to the least uninteresting natural number. As for the first comment, it means that the notion of being uncountable or countable is not absolute internally to a model of set theory. – Asaf Karagila Jan 2 '14 at 23:38

Sure, if you have five or six sets, then writing such a choice function, or an element of the product, is easily done. But the rules of logic only apply finitely many times.

What happens when you have an infinite number of sets? First of all, it's hard to talk about infinite objects explicitly with logic which is very finitary. So we need another framework, something like set theory works out just fine, because set theory is really just the study of infinite set so to speak.

And indeed the axioms of set theory (without the axiom of choice, that is) allow us to prove by induction that every finite product of non-empty sets is non-empty (and I am not even getting into the bog of standard and non-standard integers).

The role of axioms in set theory is to allow us to construct new sets. They assure us that from such and such conditions, we can ensure the existence of a particular set.

Nothing ensures that given an infinite number of non-empty sets, their product is non-empty. In fact, now we can even show that if set theory is at all consistent, then it is consistent that some products like that are empty.

The axiom of choice is, in fact, independent of the Zermelo-Fraenkel axioms.

The difficulty is to find a rule to select a real number out of ANY set.

But the axiom of choice is true for CONSTRUCTIBLE sets.

• There are models of the set theory, for which the axiom of choice is false! And some mathematicians prefere those models. – Peter Jan 2 '14 at 21:37
• But as said, for "concrete" sets, it is true. – Peter Jan 2 '14 at 21:39