König's theorem
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
-
then
-
The
sum here is the
disjoint union of the sets
ni; and the product is 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).