# König’s theorem

König’s Theorem is a theorem of cardinal arithmetic.

###### Theorem 1.

Let $\kappa_{i}$ and $\lambda_{i}$ be cardinals, for all $i$ in some index set $I$. If $\kappa_{i}<\lambda_{i}$ for all $i\in I$, then

 $\sum_{i\in I}\kappa_{i}<\,\prod_{i\in I}\lambda_{i}.$

The theorem can also be stated for arbitrary sets, as follows.

###### Theorem 2.

Let $A_{i}$ and $B_{i}$ be sets, for all $i$ in some index set $I$. If $|A_{i}|<|B_{i}|$ for all $i\in I$, then

 $\left|\,\bigcup_{i\in I}A_{i}\right|<\left|\,\prod_{i\in I}B_{i}\right|.$
###### Proof.

Let $\varphi\colon\bigcup_{i\in I}A_{i}\to\prod_{i\in I}B_{i}$ be a function. For each $i\in I$ we have $|\varphi(A_{i})|\leq|A_{i}|<|B_{i}|$, so there is some $x_{i}\in B_{i}$ that is not equal to $(\varphi(a))(i)$ for any $a\in A_{i}$. Define $f\colon I\to\bigcup_{i\in I}B_{i}$ by $f(i)=x_{i}$ for all $i\in I$. For any $i\in I$ and any $a\in A_{i}$, we have $f(i)\neq(\varphi(a))(i)$, so $f\neq\varphi(a)$. Therefore $f$ is not in the image of $\varphi$. This shows that there is no surjection from $\bigcup_{i\in I}A_{i}$ onto $\prod_{i\in I}B_{i}$. As $\prod_{i\in I}B_{i}$ is nonempty, this also means that there is no injection from $\prod_{i\in I}B_{i}$ into $\bigcup_{i\in I}A_{i}$. This completes the proof of Theorem 2. Theorem 1 follows as an immediate corollary. ∎

Note that the above proof is a diagonal argument, similar to the proof of Cantor’s Theorem. In fact, Cantor’s Theorem can be considered as a special case of König’s Theorem, taking $\kappa_{i}=1$ and $\lambda_{i}=2$ for all $i$.

Also note that Theorem 2 is equivalent (in ZF) to the Axiom of Choice, as it implies that products (http://planetmath.org/GeneralizedCartesianProduct) of nonempty sets are nonempty. (Theorem 1, on the other hand, is not meaningful without the Axiom of Choice.)

 Title König’s theorem Canonical name KonigsTheorem Date of creation 2013-03-22 14:10:21 Last modified on 2013-03-22 14:10:21 Owner yark (2760) Last modified by yark (2760) Numerical id 15 Author yark (2760) Entry type Theorem Classification msc 03E10 Synonym Koenig’s theorem Synonym Konig’s theorem Synonym König-Zermelo theorem Synonym Koenig-Zermelo theorem Synonym Konig-Zermelo theorem Related topic CantorsTheorem