|
|
There is also a proposition in graph theory called König's lemma.
In set theory, König's theorem states that if I is a set and mi and ni are cardinal numbers for every i in I, and
- <math>\forall i\in I\quad m_i
then
- <math>\sum_{i\in I}m_i<\prod_{i\in I}n_i.<math>
The sum here is the cardinality of the disjoint union of the sets ni; and the product is the cardinality of the cartesian product; we can similarly state it for arbitrary sets (not necessarily cardinal numbers) by replacing < by strictly less than in cardinality, i.e. there is an injective function from mi to ni, 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, anyway).
(Of course this 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 hand 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 mi < ni for all i in I, THEN we can only conclude <math>\sum_{i\in I} m_i \le \sum_{i\in I} n_i <math>.
Corollary of König's theorem
If we take mi = 1, and ni = 2 for all i, then the left hand side of the above inequality is just |I|, the cardinality of the index set I, while the right hand side is 2|I|, or the cardinality of the power set of I.
Thus, one can conclude Cantor's theorem from König's theorem. (Historically of course Cantor's theorem was proved much earlier.)