The theorem can also be stated for arbitrary sets, as follows.
Let and be sets, for all in some index set . If for all , then
Let be a function. For each we have , so there is some that is not equal to for any . Define by for all . For any and any , we have , so . Therefore is not in the image of . This shows that there is no surjection from onto . As is nonempty, this also means that there is no injection from into . This completes 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 and for all .
Also note that Theorem 2 is equivalent (in ZF) to the Axiom of Choice, 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.)
|Date of creation||2013-03-22 14:10:21|
|Last modified on||2013-03-22 14:10:21|
|Last modified by||yark (2760)|