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 for all $i\mathrm{\in }I$, then

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 for all $i\mathrm{\in }I$, then

Proof.

Let $\phi :{\bigcup }_{i\in I}{A}_i\to {\prod }_{i\in I}{B}_i$ be a function. For each $i\in I$ we have , so there is some $x_i\in B_i$ that is not equal to $(\phi (a))(i)$ for any $a\in A_i$. Define $f: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)\ne (\phi (a))(i)$, so $f\ne \phi (a)$. Therefore $f$ is not in the image of $\phi$. 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