Main Page | See live article | Alphabetical index

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).