# Does the Cartesian product get smaller if I use fewer sets?

My introduction into Axiom of Choice has been kind of confusing (Zorn's lemma) for the start, so it took me some time to realize it's nothing but to say The non-empty product of non-empty sets is non-empty. I still find it quite puzzling that this doesn't follow from the plain ZF axioms, but still ...

Just to understand the nature of infinite Cartesian products better now, I has asked myself the following: Does the Cartesian product get "bigger" the more non-empty sets I take, as it is with finite products ($|\{1,2\}|\leq |\{1,2\}^2|$)? To put it more correctly

Let $\{A_i\}_{i \in I}$ be a family of non-empty sets and $J \subset I$ a subset of the index set $I$. Does my intuition hold and the following is correct?$$\left|\prod_{j\in J} A_j \right| \leq \left|\prod_{i\in I} A_i\right|$$

As I see it, if this was true, Axiom of Choice follows (let $J$ be finite $\Rightarrow$ LHS is not empty), but is the statement equivalent to the Axiom of Choice? If so, how would one prove that?

-

Yes, they are equivalent. You argue correctly that your formulation implies the Axiom of Choice.

In the other direction, given the Axiom of Choice, you can find a fixed element of $\prod_{j\in I\setminus J} A_j$ and use that to extend each each element of $\prod_{j\in J} A_j$ to be defined for all of $I$ in in injective way. This proves your formulation.

-
Thank you, choosing from the complement of $I$ was the idea I looked for ;) –  Jomer Aug 2 '12 at 10:19

Taking $J$ to be a one-element set (or, even better, a zero-element set!) shows that this is equivalent to the axiom of choice. By the way, you don't need the first "non-empty": the empty product is the one-element set, so it's also non-empty.

If you find it puzzling that this statement doesn't follow from the plain ZF axioms, then (to put it bluntly) you should study the plain ZF axioms more carefully. None of them allow you to do anything like construct elements of arbitrary products.

-
Yes, but how do I prove the statement itself from AC? –  Jomer Aug 1 '12 at 16:40
@Jomer: write down an injection from one set to the other. You can do this by choosing an element in $\prod_{j \not \in J} A_j$. –  Qiaochu Yuan Aug 1 '12 at 16:41

(this is too long for a comment)

I still find it quite puzzling that this doesn't follow from the plain ZF axioms, but still ...

If I tell you $A$ is a non-empty set, can you pick an element from it?

You can't, really. You don't know anything about $A$ other than the fact it is non-empty, and so you don't have a way to select an element from it.

But you can fake it: you can argue

If x is an A, then <theorem I want to prove about A>.


If you can prove this, then the fact $A$ is non-empty allows you to conclude the theorem (if the theorem were false, then $\forall x: x \notin A$).

If I tell you $A$ and $B$ are non-empty, you can't choose an element of $A \times B$. But you can fake it by faking a choice from $A$ and faking a choice from $B$: you can argue

If x is in A and y is in B, then <theorem I want to prove about A and B>.


You can fake three choices, four choices, and so forth. But this method doesn't allow you to fake infinitely many choices. You can't fake choosing an element from an infinite product using the axioms of ZF.

-
Thank you, that's an interesting insight. Would upvote this but SE doesn't allow me to -.- –  Jomer Aug 2 '12 at 10:19