# Cardinality of the Union is less than the cardinality of the Cartesian product

Suppose I have two collections of sets, $\{A_i\}_{i \in I}$ and $\{B_i\}_{i \in I}$. It is given in the problem that $$\mathrm{card}(A_i) < \mathrm{card}(B_i) \text{ for all }i \in I$$

I want to show that $$\operatorname{card}\left(\bigcup_{i \in I} A_i \right) < \operatorname{card}\left( \prod_{i \in I} B_i \right)$$

There are no stipulations given about the cardinalities of $A_i, B_i$ or $I$.

This question came up when I was looking through a book on Naive Set Theory, and it has proved intractable so far. Any help would be much appreciated!

-
You have to make use of the axiom of choice (otherwise you couldn't even prove that every cartesian product is non-empty.) – Dominik Nov 26 '12 at 20:06

This is known as König's Theorem (there is also a lemma called the son of this one). We are going to assume the axiom of choice through this answer, otherwise one cannot prove this theorem (more on that at the bottom).

Michael Greinecker gave a concise argument for the fact there is no surjective function from the union to the product. Which under the axiom of choice is enough to conclude there is a surjection in the other direction, and an injection from the union to the product, as wanted. Here is a more explicit construction of an injection:

If any of the $A_i$ is empty let us drop it from the list, and remove the corresponding $B_i$ as well. I hope it's clear why this is not going to harm the result. We may also assume that the $A_i$'s are pairwise disjoint sets.

The fact that $|A_i|<|B_i|$ means that there is an injection $f_i\colon A_i\to B_i$. And there is no injection in the other direction, else by Cantor-Bernstein we would have equality rather than a sharp inequality. For simplicity we can also assume that $A_i\subsetneqq B_i$ for all $i\in I$.

Fix $\langle b_i\mid i\in I\rangle$ some sequence in the product. Let us define an injection now. Let $a\in A_j$, if $a\neq b_j$ then send $a$ to the sequence $\langle \overline b_i\mid i\in I\rangle$ such that $\overline b_i=b_i$ for $i\neq j$ and $a$ otherwise.

If $a=b_j$, we know that $B_i$ has at least two elements for every $i\in I$ then we can fix $\langle c_i\mid i\in I\rangle$ in the product, such that $c_i\neq b_i$ for every $i\in I$. So in the case $a=b_j$ we send $a$ to the sequence of $\langle \overline c_i\mid i\in I\rangle$ such that $\overline c_i=c_i$ for $i\neq j$, and $a$ otherwise.

It is not hard to see that this is an injective function. Therefore the union has cardinality less or equal than that of the product.

A word about the axiom of choice. It is consistent that without the axiom of choice there is a countable set of disjoint pairs that has no choice function. Namely $\{P_n\mid n\in\omega\}$ such that $\prod P_n=\varnothing$. It is easy to see that even if we take $A_n=\{0\}$ for all $n$, then $|A_n|=1<2=|P_n|$, and $$\left|\bigcup A_n\right| = |\{0\}| = 1 > 0 = |\varnothing| =\left|\prod P_n\right|$$

I will remark, however, that if we assume that $A_i$ and $B_i$ are all sets of ordinals then the lemma holds regardless to the axiom of choice.

-
I think the usual terminology is "König's Theorem" for this result and "König's Lemma" for the one about branches in trees. – Andreas Blass Nov 26 '12 at 20:30
@Andreas: It is? I remember only vaguely the distinction in Hebrew, but I'll change this. Thanks! – Asaf Karagila Nov 26 '12 at 20:31
@Asaf There is a Hebrew word for Lemma? – Michael Greinecker Nov 26 '12 at 20:32
@MichaelGreinecker: למה :-) (But it is possible and even likely that I was taught this as a lemma) – Asaf Karagila Nov 26 '12 at 20:33
@Asaf Lemma=Lama? youtube.com/watch?v=B3-HBpK3oCU – Michael Greinecker Nov 26 '12 at 20:39

Let $f:\bigcup_i A_i\to\prod_i B_i$ be any function. We show it can not be surjective. Let $\pi_i:\prod_i B_i\to B_i$ be the projection onto the $i^\text{th}$ factor for all $i$. Let $X_i=B_i\backslash \pi_i\big(f(A_i)\big)$. By assumption, $X_i\neq\emptyset$ for all $i$. So $\prod_i X_i\neq\emptyset$. By construction, an element of $\prod_i X_i$ is not in the range of $f$.

Remark: This is an old result from König. The proof here is taken from this book.

-

This is called König's theorem. The proof I know is reasonably simple but not something I'd expect anyone to think up as an exercise. See the bottom of page 15 here (page 17 in the PDF).

-
Thanks Clive, appreciated – Moderat Nov 26 '12 at 20:10