König's inequality

1. Introduction

This web page concerns a remarkable theorem on cardinal arithmetic due to the Hungarian Mathematician Gyula Kőnig, or Julius König as he was known when writing in German. (This is not the same person as Dénes Kőnig after whom König's lemma—also called König's infinity lemma—is named.) Julius König devised his theorem to tackle the continuum problem, whether $ℵ_{1} = 2^{ℵ_{0}}$ , and solved the problem negatively by quoting and using a result of Berstein. Unfortunately for König, Berstein's result was found to contain an error and was not true in the generality that König required.

2. König's inequality

Definition.

Suppose $I$ is a set and for each $i \in I$ a set $A_{i}$ is given, i.e. there is a (set-)function $i \mapsto A_{i}$ given. The sum of the sets $A_{i}$ is ${\sum_{i \in I}^{} A}_{i} = \{(i, a): a \in A_{i}\}$ . The cartesian product of the sets $A_{i}$ is ${\prod_{i \in I}^{} A}_{i} = \{f : I \to ⋃ A_{i}: \forall i \in I f (i) \in A_{i}\}$ .

Although these definitions are valid in the absence of Choice, the Axiom is Choice is required even to show that an arbitary cartesian product or sum of sets is nonempty. We shall assume Choice throughout this web page.

We write $X ≺ Y$ to mean that there is an injection from $X$ to $Y$ but no injection in the other direction, that is that $card (X) < card (Y)$ .

Theorem.

Suppose sets $I$ and $A_{i}, B_{i}$ are given for $i \in I$ , and suppose $A_{i} ≺ B_{i}$ for all $i \in I$ . Then ${\sum_{i \in I}^{} A}_{i} ≺ {\prod_{i \in I}^{} B}_{i}$ .

A special case of this is when $I = A$ and $A_{a} = \{a\}$ and $B_{a} = 2 = \{0, 1\}$ . Then $A \approx {\sum_{a \in A}^{} A}_{a}$ and $P (A) \approx {\prod_{a \in A}^{} B}_{a}$ so König's theorem says that $A ≺ P (A)$ which was proved earlier by a sort of diagonalisation. It is therefore no surprise that a diagonalisation is required here too.

Proof.

For one direction, we must define an injection from ${\sum_{i \in I}^{} A}_{i}$ to ${\prod_{i \in I}^{} B}_{i}$ . By AC there is a family of injections $f_{i} : A_{i} \to B_{i}$ (or more precisely some function $F$ on domain $I$ such that $F (i) = f_{i}$ is such an injection for each $i$ ) and by assumption none of these $f_{i}$ is onto. So my another application of AC there is for each $i$ some $x_{i} \in B_{i} ∖ f_{i} (A_{i})$ . We can therefore define $g : {\sum_{i \in I}^{} A}_{i} \to {\prod_{i \in I}^{} B}_{i}$ by $g (i, a) = g_{i, a}$ where $a \in A_{i}$ and $g_{i, a} (j) = f_{i} (a)$ if $i = j$ and $g_{i, a} (j) = x_{j}$ otherwise. if it happens that $g_{i, a} = g_{i', a'}$ then $i \neq i'$ in which case $g_{i, a} (i') = x_{i'} \notin Im f_{i'}$ or $i = i'$ and $g_{i, a} (i) = f_{i} (a)$ whereas $g_{i, a'} (i) = f_{i} (a')$ so $g_{i, a} = g_{i, a'}$ implies $a = a'$ as $f_{i}$ is injective.

For the other, more interesting, direction we must show there is no injection from ${\prod_{i \in I}^{} B}_{i}$ to ${\sum_{i \in I}^{} A}_{i}$ . Suppose $h$ is suchj a map: we construct some $e \in {\prod_{i \in I}^{} B}_{i}$ with no possible value $h (e)$ .

We start by defining $θ_{i} : C_{i} \to B_{i}$ where $C_{i} \subseteq A_{i}$ by $θ_{i} (a) = d (i)$ if there is $d \in {\prod_{i \in I}^{} B}_{i}$ with $h (d) = (i, a)$ . The set $C_{i}$ is the set of all $a \in A_{i}$ for which this is defined. Note that as $h$ is an injection there is at most one such $d$ if there is any at all, so $θ_{i}$ is well-defined.

Of course $θ_{i} : C_{i} \to B_{i}$ cannot be onto, as that would mean by AC that there is an injection $B_{i} \to A_{i}$ . Therefore, by Choice again, we may take for each $i \in I$ some $e (i) \in B_{i} ∖ Im (θ_{i})$ . Thus $e \in {\prod_{i \in I}^{} B}_{i}$ and hence $h (e) = (i, c)$ for some $i \in I$ and $c \in A_{i}$ . But this is impossible as then $θ_{i} (c) = e (i) \in Im (θ_{i})$ contradicting the choice of $e (i)$ . So there is no such $h$ , as required.

The remarkable thing about König's inequality is that it gives us a strict inequality between the product and the sum sets: normally all that can be expected is a less-than-or-equal-to result.

Assuming the Axiom of Choice to make the following well-defined, we have

Definition.

Suppose $I$ is a set and for each $i \in I$ cardinalities $κ_{i}$ is given, then the cardinal sum ${\sum_{i \in I}^{} κ}_{i}$ of the $κ_{i}$ is the cardinality of any ${\sum_{i \in I}^{} A}_{i}$ where $card (A_{i}) = κ_{i}$ for each $i$ and the cardinal product of the $κ_{i}$ , i.e. ${\prod_{i \in I}^{} κ}_{i}$ , is the cardinality of any such ${\prod_{i \in I}^{} A}_{i}$ .

Then König's inequality says

{\sum_{i \in I}^{} κ}_{i} < {\prod_{i \in I}^{} λ}_{i}

whenever $κ_{i} < λ_{i}$ for all $i$ .

For example,

ℵ_{ω} = {\sum_{i \in ω}^{} ℵ}_{i} < {\prod_{i \in ω}^{} ℵ}_{ω} = (ℵ_{ω})^{ℵ_{0}}

and it follows that $2^{ℵ_{0}} \neq ℵ_{ω}$ for if they were equal we would have

(ℵ_{ω})^{ℵ_{0}} = (2^{ℵ_{0}})^{ℵ_{0}} = 2^{ℵ_{0} \times ℵ_{0}} = 2^{ℵ_{0}} = ℵ_{ω}