2
$\begingroup$

Given the axiom of choice, we know that the Cartesian product of an infinite family of non-empty sets is non-empty. However, this doesn't tell us whether the Cartesian product contains every element we might "expect".

For example, consider the Cartesian product of the family $\{A_i\}$ for $i \in \mathbb{N}$, where $A_i = \mathbb{N}$ for each $i$. Is it the case that every possible sequence of natural numbers appears in this Cartesian product?

More generally:

If we take the axiom of choice, can we make a general statement about the Cartesian product of an infinite family of non-empty sets that's stronger than the statement "it's non-empty"?

$\endgroup$
  • 1
    $\begingroup$ Sure. We can use Cantor's argument, even without Axiom of choice, to prove that $\prod_{i\in\mathbb N} \mathbb N$ is uncountable, for example. $\endgroup$ – Thomas Andrews Aug 18 '14 at 0:25
  • 1
    $\begingroup$ The question in your previous to last paragraph makes no sense. Of course "every possible" sequence of natural numbers belongs to the set of all sequences of natural numbers. $\endgroup$ – Andrés E. Caicedo Aug 18 '14 at 0:47
  • 1
    $\begingroup$ The actual question in the last paragraph is perhaps more interesting, though I am not sure what kind of question you expect beyond "Yes, that products are nonempty actually implies that they are typically rather large." $\endgroup$ – Andrés E. Caicedo Aug 18 '14 at 0:49
  • $\begingroup$ (Sorry for the question/answer typo in the previous comment.) $\endgroup$ – Andrés E. Caicedo Aug 18 '14 at 1:01
  • 1
    $\begingroup$ You might as well focus on the simple special case where $A_i=\{0,1\}$ for each $i\in\mathbb N$. So, does $\mathcal P(\mathbb N)$ really contain every possible subset of $\mathbb N$? $\endgroup$ – bof Aug 18 '14 at 22:40
2
$\begingroup$

Axiom of choice implies König's theorem which estimates cardinality of the product from below, namely $|\prod_{i\in I}A_i|\geq|\sum_{i\in I}A_i|$, the sum stands for the disjoint union. In particular, the product has at least as many elements as any of the factors, which is stronger than just non-empty.

However, if $I=\mathbb{N}$ and $A_i=A$ "every possible sequence" from $A$ is in the product by definition of the product regardless, even if the product is empty. When $A=\mathbb{N}$ there is no need even for the axiom of choice to claim non-emptiness since $\mathbb{N}$ is well ordered and we can pick $1$ from each copy.

$\endgroup$
0
$\begingroup$

No. Generally, you can't say something stronger which isn't a consequence of the "weaker" formulation anyway.

Suppose that $\{A_i\mid i\in I\}$ is a family of sets. The product $\prod_{i\in I}A_i$ is a set defined using the separation schema. It is the set of all functions $f$ with domain $I$ such that $f(i)\in A_i$.

All of them. And the existence of this set has nothing to do with the axiom of choice. If $\{A_i\mid i\in I\}$ is a family whose product is empty, then its product is the empty set. Certainly if any set exists, it should be the empty set.

But all of them doesn't mean that any such function exists to begin with, so this set might be empty. The axiom of choice simply says, no it's not empty. If it isn't empty it has all the choice functions that the universe knows about.

To sum up, choice functions are like cockroaches. Where there is one, there are many. Usually infinitely many.


There is a delicate issue here about different models of set theory which may know about more choice functions or less choice functions. But I think it might be counterproductive to start a discussion about that here.

$\endgroup$
  • 1
    $\begingroup$ That last sentence is really just glossing over the question at hand - why does axiom of choice ensuring at least one element imply it has "all the choice functions that the universe knows about." That is the heart of the question, and you've merely asserted it is true. $\endgroup$ – Thomas Andrews Aug 18 '14 at 0:26
  • 1
    $\begingroup$ I'm not sure why you think I glossed over this. The definition of the product is to take everything. The only issue is that "everything" might be nothing in the absence of choice. $\endgroup$ – Asaf Karagila Aug 18 '14 at 0:28
  • $\begingroup$ Asaf, is it correct to say that the axiom of choice lets you use the fact that "such a set exists" (in addition to the more commonly cited fact that "such a set is non-empty")? $\endgroup$ – Elliott Aug 18 '14 at 18:21
  • $\begingroup$ @Elliott: No, it is not true. As I wrote in my answer, the set exists for other reasons, namely union, power set and separation. Choice is only used to show it is not empty. $\endgroup$ – Asaf Karagila Aug 18 '14 at 18:23

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.