König’s theorem

König’s Theorem is a theorem of cardinal arithmetic.

Theorem 1.

Let κi and λi be cardinals, for all i in some index setMathworldPlanetmathPlanetmath I. If κi<λi for all iI, then


The theorem can also be stated for arbitrary sets, as follows.

Theorem 2.

Let Ai and Bi be sets, for all i in some index set I. If |Ai|<|Bi| for all iI, then


Let φ:iIAiiIBi be a function. For each iI we have |φ(Ai)||Ai|<|Bi|, so there is some xiBi that is not equal to (φ(a))(i) for any aAi. Define f:IiIBi by f(i)=xi for all iI. For any iI and any aAi, we have f(i)(φ(a))(i), so fφ(a). Therefore f is not in the image of φ. This shows that there is no surjection from iIAi onto iIBi. As iIBi is nonempty, this also means that there is no injection from iIBi into iIAi. This completesPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath 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 κi=1 and λi=2 for all i.

Also note that Theorem 2 is equivalentMathworldPlanetmathPlanetmathPlanetmath (in ZF) to the Axiom of ChoiceMathworldPlanetmath, 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