Details
The precise statement of the result: if I is a set, Ai and Bi are sets for every i in I, and for every i in I, then
where < means strictly less than in cardinality, i.e. there is an injective function from the left-hand side to the right-hand side, but not one going the other way. The union involved need not be disjoint (a non-disjoint union can't be any bigger than the disjoint version, also assuming the axiom of choice). In this formulation, Kőnig's theorem is equivalent to the axiom of choice.1
(Of course, Kőnig's theorem is trivial if the cardinal numbers mi and ni are finite and the index set I is finite. If I is empty, then the left sum is the empty sum and therefore 0, while the right product is the empty product and therefore 1.)
Kőnig's theorem is remarkable because of the strict inequality in the conclusion. There are many easy rules for the arithmetic of infinite sums and products of cardinals in which one can only conclude a weak inequality ≤, for example: if for all i in I, then one can only conclude
since, for example, setting and , where the index set I is the natural numbers, yields the sum for both sides, and we have an equality.
Corollaries of Kőnig's theorem
If we take , and for each in , then the left side of the above inequality is just , while the right side is , the cardinality of functions from to , that is, the cardinality of the power set of . Thus, Kőnig's theorem gives us a proof of Cantor's theorem. (Historically of course Cantor's theorem was proved much earlier.)
Axiom of choice
One way of stating the axiom of choice is "an arbitrary Cartesian product of non-empty sets is non-empty". Let Bi be a non-empty set for each i in I. Let Ai = {} for each i in I. Thus by Kőnig's theorem, we have:
That is, the Cartesian product of the given non-empty sets Bi has a larger cardinality than the sum of empty sets. Thus it is non-empty, which is just what the axiom of choice states. Since the axiom of choice follows from Kőnig's theorem, we will use the axiom of choice freely and implicitly when discussing consequences of the theorem.
Kőnig's theorem and cofinality
Kőnig's theorem has also important consequences for the cofinality of cardinal numbers.
If κ is regular, then this follows from Cantor's theorem. If κ is singular, then κ is a limit cardinal. Choose a strictly increasing cf(κ)-sequence of cardinals approaching κ. Let λ be their sum. Each summand is less than κ, so, by Kőnig's theorem, λ is less than the product of cf(κ) copies of κ. We finish the proof by showing that λ = κ. Since each summand is a lower bound for λ, λ ≥ κ. For the other inequality, λ ≤ cf(κ)·κ = κ.
According to Easton's theorem, the next consequence of Kőnig's theorem is the only nontrivial constraint on the for .
A proof of Kőnig's theorem
Assuming Zermelo–Fraenkel set theory, including especially the axiom of choice, we can prove the theorem. Remember that we are given , and we want to show
The axiom of choice implies that the condition A < B is equivalent to the condition that there is no function from A onto B and B is nonempty. So we are given that there is no function from Ai onto Bi≠{}, and we have to show that any function f from the disjoint union of the As to the product of the Bs is not surjective and that the product is nonempty. That the product is nonempty follows immediately from the axiom of choice and the fact that the factors are nonempty. For each i choose a bi in Bi not in the image of Ai under the composition of f with the projection to Bi. Then the product of the elements bi is not in the image of f, so f does not map the disjoint union of the As onto the product of the Bs.2
References
- M. Holz, K. Steffens and E. Weitz (1999). Introduction to Cardinal Arithmetic. Birkhäuser. ISBN 3-7643-6124-7.
- Kőnig, J. (1904), "Zum Kontinuum-Problem", in Krazer, Adolf (ed.), Verhandlungen des dritten Internationalen Mathematiker-Kongresses in Heidelberg vom 8. bis 13. August 1904, pp. 144–147, archived from the original on 2015-01-04, retrieved 2014-06-14, reprinted as Kőnig, J. (1905), "Zum Kontinuum-Problem", Mathematische Annalen, 60 (2): 177–180, doi:10.1007/BF01677263, S2CID 177788074
Let . Suppose that, contrary to this corollary, . Then using the previous corollary, , a contradiction.
