Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I recently stumbled across the wikipedia page on equivalents to the Axiom of Choice. I noticed that every infinite Cartesian product of a non-empty family of non-empty sets being non-empty was equivalent to the axiom of choice. Which isn't hard to see, since any element from such a product is essentially a choice function.

This led me to wonder under what circumstances can you construct such infinite Cartesian products without the axiom of choice. I'm curious about general conditions required, presumably if there's some well-ordering on each set in the family this would be sufficient. In particular I'm curious about $\mathbb R^{\mathbb R}$ and $\mathbb R^{\mathbb N}$ that is the sets of real-valued functions on the real line and all real-valued sequences. Can we still claim that these sets exist without the axiom of choice?

share|cite|improve this question
up vote 9 down vote accepted

What is equivalent to the Axiom of Choice is the assertion that every cartesian product of any nonempty family of nonempty sets is itself nonempty (not merely that "an infinite Cartesian product of a non-empty family of nonempty sets").

There are plenty of families for which one can prove, without needing to invoke the Axiom of Choice, that their cartesian product is nonempty. For example, as you note, a product of any nonempty family of nonempty well-ordered sets is nonempty, regardless of the cardinality of the family. (However, proving that a denumerably infinite product of denumerably infinite sets is nonempty requires at least some Choice; you can think of this as a weakening of the previous case, since here we are saying that the sets are well-order able but not necessarily well-order ed. That is, rather than coming already provided with a well-ordering, we are just told that a well ordering exists).

In general, any family in which all the sets are the same also has nonempty product: if $\{A_i\}_{i\in I}$ is a nonempty family, and $A_i=A_j\neq\emptyset$ for all $i,j\in I$, then since $A_i$ is nonempty, there exists $a\in A_i$. Then the function $f\colon I\to\cup A_i$ given by $f(i) = a$ for all $i\in I$ is a choice function for the family (and an element of $\times_{i\in I} A_i$). In particular, both the sets $\mathbb{R}^\mathbb{R}$ and $\mathbb{R}^{\mathbb{N}}$ are nonempty, and we can prove this without invoking choice. Just the $f\colon\mathbb{R}\to\mathbb{R}$ given by $f(r)=0$ for all $r$; this is an element of $\mathbb{R}^{\mathbb{R}}$; and $g(n)=0$ for all $n\in\mathbb{N}$, this is an element of $\mathbb{R}^{\mathbb{N}}$. Neither one requires AC.

Likewise, any family $\{A_i\}_{i\in I}$ in which there is a cofinite $J\subseteq I$ with $\cap_{j\in J}A_j\neq\emptyset$ will have a choice function whose existence does not depend on AC: take any $J$ with the given property, take any $x\in \cap_{j\in J}A_j$, and letting $I-J = \{i_1,\ldots,i_k\}$, pick $a_t\in A_{i_t}$, $t=1,\ldots,k$. Then $f\colon J\to\cup A_i$ given by $$f(i) = \left\{\begin{array}{ll} x & \mbox{if $i\in J$;}\\ a_1 &\mbox{if $i=i_1$;}\\ \vdots\\ a_k &\mbox{if $i=i_k$.} \end{array}\right.$$ is a choice function for the family, whose existence can be established without invoking the Axiom of Choice. This is of course not necessary, merely sufficient.

share|cite|improve this answer
Beat me to it :-) – Asaf Karagila Feb 25 '11 at 21:47
Okay, that makes sense. Can we show that they have all the elements we'd "expect" them to have? Is it still apparent that $\mathbb R^{\mathbb R}$ has greater cardinality than $\mathbb R$? – JSchlather Feb 25 '11 at 21:51
Yes, Cantor still applies. – Henno Brandsma Feb 25 '11 at 21:54
@Jacob: Yes; there is no AC-issue in showing that $\mathbb{R}$ is bijectable with $2^{\aleph_0}$, and therefore there is also no AC-issue in showing that $\mathbb{R}^{\mathbb{R}}$ has cardinality $\mathfrak{c}^{\mathfrak{c}} = 2^{\mathfrak{c}}$, simply following through the bijections and the bijections involved in the cardinal arithmetic equalities. – Arturo Magidin Feb 25 '11 at 21:55
Ah, thanks a lot. – JSchlather Feb 25 '11 at 22:03

Sure, they exist always, by Comprehension, and they are non-empty in this case, because $X^X$ always contains the identity and constant functions. The same holds for $X^N$: we already have constant functions and many other ones. Powers are not really the issue, but product of indexed sets, of different types, that have no "structure" like a well-order to exploit, roughly speaking.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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