König’s theorem
König’s Theorem is a theorem of cardinal arithmetic.
The theorem can also be stated for arbitrary sets, as follows.
Theorem 2.
Let and be sets, for all in some index set . If for all , then
Proof.
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.)
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 |