Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
König's theorem (set theory)
Summary
In set theory, König's theorem states that if the axiom of choice holds, I is a set, and are cardinal numbers for every i in I, and for every i in I, then
The sum here is the cardinality of the disjoint union of the sets mi, and the product is the cardinality of the Cartesian product. However, without the use of the axiom of choice, the sum and the product cannot be defined as cardinal numbers, and the meaning of the inequality sign would need to be clarified.
König's theorem was introduced by in the slightly weaker form that the sum of a strictly increasing sequence of nonzero cardinal numbers is less than their product.
The precise statement of the result: if I is a set, Ai and Bi are sets for every i in I, and for every i in I, then
where < means strictly less than in cardinality, i.e. there is an injective function from Ai to Bi, 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, also assuming the axiom of choice). In this formulation, König's theorem is equivalent to the axiom of choice.
(Of course, König's theorem 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 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 for all i in I, then one can only conclude
since, for example, setting and , where the index set I is the natural numbers, yields the sum for both sides, and we have an equality.
If is a cardinal, then .
If we take mi = 1, and ni = 2 for each i in κ, then the left side of the above inequality is just κ, while the right side is 2κ, the cardinality of functions from κ to {0, 1}, that is, the cardinality of the power set of κ. Thus, König's theorem gives us an alternate proof of Cantor's theorem.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.