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 isno 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 thatthere 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