Proof of König's Theorem

König's theorem is the most powerful general inequality in cardinal arithmetic, implying Cantor's theorem as a special case and restricting the behavior of the exponential function.

Statement

Theorem5.4König's theorem

Let $I$ be an index set and $\{\kappa_i\}_{i \in I}$ , $\{\lambda_i\}_{i \in I}$ be families of cardinals with $\kappa_i < \lambda_i$ for all $i \in I$ . Then:

$\sum_{i \in I} \kappa_i < \prod_{i \in I} \lambda_i.$

Proof

We need to show: (a) $\sum \kappa_i \leq \prod \lambda_i$ , and (b) $\sum \kappa_i \neq \prod \lambda_i$ .

Part (a): For each $i$ , fix an injection $f_i: \kappa_i \hookrightarrow \lambda_i$ (which exists since $\kappa_i < \lambda_i$ ). We construct an injection from $\bigsqcup_{i \in I} \kappa_i$ into $\prod_{i \in I} \lambda_i$ .

For each $(i_0, \alpha) \in \bigsqcup_{i \in I} \kappa_i$ (where $\alpha < \kappa_{i_0}$ ), define a function $g_{i_0, \alpha}: I \to \bigcup \lambda_i$ by:

$g_{i_0, \alpha}(i) = \begin{cases} f_{i_0}(\alpha) & \text{if } i = i_0, \\ 0 & \text{if } i \neq i_0. \end{cases}$

The map $(i_0, \alpha) \mapsto g_{i_0, \alpha}$ is injective: if $g_{i_0, \alpha} = g_{j_0, \beta}$ , then $i_0 = j_0$ (the only coordinate that can be nonzero) and $f_{i_0}(\alpha) = f_{i_0}(\beta)$ , so $\alpha = \beta$ .

Part (b): Suppose for contradiction that $h: \bigsqcup_{i \in I} \kappa_i \to \prod_{i \in I} \lambda_i$ is a surjection. For each $i \in I$ , consider the "slice" $S_i = \{h(i, \alpha)(i) : \alpha < \kappa_i\}$ . This is the set of values in $\lambda_i$ that appear as the $i$ -th coordinate of some $h(i, \alpha)$ .

Since $|S_i| \leq \kappa_i < \lambda_i$ , there exists $\beta_i \in \lambda_i \setminus S_i$ for each $i$ .

Define a function $g^*: I \to \bigcup \lambda_i$ by $g^*(i) = \beta_i$ . Then $g^* \in \prod_{i \in I} \lambda_i$ .

By surjectivity, $g^* = h(j, \gamma)$ for some $j \in I$ , $\gamma < \kappa_j$ . Then $g^*(j) = h(j, \gamma)(j) \in S_j$ . But $g^*(j) = \beta_j \notin S_j$ by construction. Contradiction. $\blacksquare$

■

Corollaries

ExampleImportant consequences

Cantor's theorem as a special case: Take $I = A$ , $\kappa_i = 1$ , $\lambda_i = 2$ for all $i$ . Then $\sum 1 = |A|$ and $\prod 2 = 2^{|A|}$ , so $|A| < 2^{|A|}$ .

Cofinality restriction: Taking $I = \mathrm{cf}(\kappa)$ and suitable sequences: $\mathrm{cf}(2^\kappa) > \kappa$ . In particular:

$\mathrm{cf}(\mathfrak{c}) > \aleph_0$ , so $\mathfrak{c} \neq \aleph_\omega$ .
$2^{\aleph_1} \neq \aleph_{\omega_1}$ (since $\mathrm{cf}(\aleph_{\omega_1}) = \omega_1 = \aleph_1$ ).

RemarkKönig's theorem and pcf theory

König's theorem gives an upper bound on $\sum \kappa_i$ in terms of $\prod \lambda_i$ . Shelah's pcf theory (possible cofinalities) provides much deeper results about products of cardinals, particularly the remarkable theorem that if $\aleph_\omega$ is a strong limit, then $2^{\aleph_\omega} < \aleph_{\omega_4}$ . This was a breakthrough showing that the exponential function at singular cardinals is far more constrained than at regular cardinals.