%%% This file is part of PlanetMath snapshot of 2009-01-12
%%% Primary Title: K\"onig's theorem
%%% Primary Category Code: 03E10
%%% Filename: KonigsTheorem.tex
%%% Version: 12
%%% Owner: yark
%%% Author(s): yark
%%% PlanetMath is released under the GNU Free Documentation License.
%%% You should have received a file called fdl.txt along with this file.        
%%% If not, please write to gnu@gnu.org.
\documentclass[12pt]{article}
\pagestyle{empty}
\setlength{\paperwidth}{8.5in}
\setlength{\paperheight}{11in}

\setlength{\topmargin}{0.00in}
\setlength{\headsep}{0.00in}
\setlength{\headheight}{0.00in}
\setlength{\evensidemargin}{0.00in}
\setlength{\oddsidemargin}{0.00in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9.00in}
\setlength{\voffset}{0.00in}
\setlength{\hoffset}{0.00in}
\setlength{\marginparwidth}{0.00in}
\setlength{\marginparsep}{0.00in}
\setlength{\parindent}{0.00in}
\setlength{\parskip}{0.15in}

\usepackage{html}

\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}

\newtheorem{theorem}{Theorem}

\begin{document}











\emph{K\"onig's Theorem} is a theorem of \htmladdnormallink{cardinal arithmetic}{http://planetmath.org/encyclopedia/ProductOfCardinals.html}.

\begin{theorem}
Let $\kappa_i$ and $\lambda_i$ be \htmladdnormallink{cardinals}{http://planetmath.org/encyclopedia/Cardinal.html}, for all $i$ in some \htmladdnormallink{index set}{http://planetmath.org/encyclopedia/IndexedBy.html} $I$.
If $\kappa_i<\lambda_i$ for all $i\in I$, then
$$\sum_{i\in I}\kappa_i<\,\prod_{i\in I}\lambda_i.$$
\end{theorem}

The theorem can also be stated for arbitrary sets, as follows.
\begin{theorem}
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|.$$
\end{theorem}
\begin{proof}
Let $\varphi\colon\bigcup_{i\in I}A_i\to\prod_{i\in I}B_i$ be a \htmladdnormallink{function}{http://planetmath.org/encyclopedia/Range2.html}.
For each $i\in I$ we have $|\varphi(A_i)|\le|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)\ne(\varphi(a))(i)$, so $f\ne\varphi(a)$.
Therefore $f$ is not in the image of $\varphi$.
This shows that there is
no \htmladdnormallink{surjection}{http://planetmath.org/encyclopedia/Surjection.html} 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 \htmladdnormallink{injection}{http://planetmath.org/encyclopedia/Embedding.html} from $\prod_{i\in I}B_i$ into $\bigcup_{i\in I}A_i$.
This completes the \htmladdnormallink{proof}{http://planetmath.org/encyclopedia/Proof.html} of Theorem 2.
Theorem 1 follows as an immediate corollary.
\end{proof}

Note that the above proof is a \htmladdnormallink{diagonal}{http://planetmath.org/encyclopedia/Diagonal.html} argument,
similar to the \htmladdnormallink{proof of Cantor's Theorem}{http://planetmath.org/encyclopedia/ProofOfCantorsTheorem.html}.
In fact, \htmladdnormallink{Cantor's Theorem}{http://planetmath.org/encyclopedia/CantorsTheorem.html} can be considered as a special case of K\"onig's Theorem, taking $\kappa_i=1$ and $\lambda_i=2$ for all $i$.

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

\end{document}