König's theorem (set theory)

:"For other uses, see König's theorem."

In set theory, König's theorem (named after the Hungarian mathematician Gyula König) colloquially states that if the axiom of choice holds, "I" is a set, "mi" and "ni" are cardinal numbers for every "i" in "I", and m_i < n_i ! for every "i" in "I" then :sum_{iin I}m_i

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, this formulation cannot even be stated without the use of some form of the Axiom of Choice.

Details

The precise statement of the result: if "I" is a set , "Ai" and "Bi" are sets for every "i" in "I", and A_i for every "i" in "I" then :sum_{iin I}A_iwhere < 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. cite book|last=Rubin|first=H.|coauthors=Rubin, J.E.|title=Equivalents of the Axiom of Choice, II|publisher=North Holland|Place=New York, NY|year=1985|pages=185|id=ISBN 0-444-87708-8]

(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 m_i < n_i ! for all "i" in "I", THEN we can only conclude :sum_{iin I} m_i le sum_{iin I} n_i since, for example, setting m_i = 1 & n_i = 2 where the index set "I" is the natural numbers, yields the sum aleph_0 for boths sides and we have a strict equality.

Corollaries of König's theorem

*If kappa, is a cardinal then kappa < 2^{kappa}.!If we take "mi" = 1, and "ni" = 2 for each "i" in κ, then the left hand side of the above inequality is just κ, while the right hand 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. (Historically of course Cantor's theorem was proved much earlier.)

Axiom of choice

One way of stating the axiom of choice is "An arbitrary Cartesian product of non-empty sets is non-empty.". Let "Bi" be a non-empty set for each "i" in "I". Let "Ai" = {} for each "i" in "I". Thus by König's theorem, we have:
*If forall iin I({}, then {}.That is, the Cartesian product of the given non-empty sets, "Bi", has a larger cardinality than the sum of empty sets. Thus it is non-empty which is just what the axiom of choice states. Since the axiom of choice follows from König's theorem, we will use it freely and implicitly when discussing consequences of the theorem.

König's theorem and cofinality

König's theorem has also important consequences for cofinality of cardinal numbers.

*If kappagealeph_0, then kappa.Choose a strictly increasing cf(κ)-sequence of cardinals approaching κ. Each of them is less than κ, so their sum which is κ is less than the product of cf(κ) copies of κ.

According to Easton's theorem, the next consequence of König's theorem is the only nontrivial constraint on the continuum function for regular cardinals.

*If kappageqaleph_0 and lambdageq 2, then kappa.Let mu = lambda^kappa !. Suppose that, contrary to this corollary, kappa ge cf(mu). Then using the previous corollary, mu, a contradiction. Thus the supposition must be false and this corollary must be true.

A proof of König's theorem

Assuming Zermelo–Fraenkel set theory, including especially the axiom of choice, we can prove the theorem. Remember that we are given forall iin Iquad A_i, and we want to show sum_{iin I}A_i.

First, we show that there is an injection from the sum to the product. Using the axiom of choice, for each "i" we choose an injection "fi" from "Ai" to "Bi". Notice that "fi" cannot be a surjection because then its inverse would be an injection from "Bi" to "Ai". So, for each "i", there must be an element of "Bi" not in the range of "fi". Using the axiom of choice again, we choose such an "xi" for each "i". Define "g" on the sum by "g"("i,a") ("j") = "fi"("a") when "j" = "i" and "a" is an element of "Ai" and "g"("i,a") ("j") = "xj" when "j" ≠ "i" and "a" is an element of "Ai". Since "fi"("a") ≠ "xi" for each "i", "g" is an injection from the sum to the product.

Second, we show that there is no injection "h" from the product to the sum. Suppose, to the contrary, that such an "h" existed. In a similar manner to Cantor's diagonal argument, we will construct an element "e" of the product, which cannot have a value under "h". For each "i" in "I", construct a partial function "fi" from "Ai" to "Bi" by "fi"("a") = "d"("i") if there is a "d" in the product such that "h"("d") = ("i","a"). (This is a partial function because "h" is an injection, so the "d" is unique.) If "fi" were a surjection, then, using the axiom of choice, we could construct an injection "g" from "Bi" into "Ai" ("g" would be a right inverse of "f""i"), contradicting the hypothesis. Hence, for each "i" in "I", there are elements of "Bi" not in the image of "fi". So using the axiom of choice again, we choose "e"("i") in "Bi" but not in the image of "fi". Consider, now, the value of "h"("e") = ("i","c") with "c" in "Ai". But then "fi"("c") = "e"("i"), contradicting the construction of "e". Hence no such injection can exist, and the product is strictly larger in cardinality than the sum.

External links

* [http://planetmath.org/encyclopedia/KonigsTheorem.html König's theorem] article on PlanetMath, includes a proof

References

*cite book | author=M. Holz, K. Steffens and E. Weitz | title=Introduction to Cardinal Arithmetic | publisher=Birkhäuser | year=1999 | id=ISBN 3764361247


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • König's theorem (graph theory) — In the mathematical area of graph theory, König s theorem describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs. Setting A graph is bipartite if its vertices can be partitioned into …   Wikipedia

  • König's theorem — There are several theorems with the name König s theorem:* König s theorem (set theory), named after the Hungarian mathematician Julius König * König s theorem (graph theory), named after his son Dénes Kőnig * König s theorem (kinetics), named… …   Wikipedia

  • Set theory — This article is about the branch of mathematics. For musical set theory, see Set theory (music). A Venn diagram illustrating the intersection of two sets. Set theory is the branch of mathematics that studies sets, which are collections of objects …   Wikipedia

  • De Bruijn–Erdős theorem (graph theory) — This article is about coloring infinite graphs. For the number of lines determined by a finite set of points, see De Bruijn–Erdős theorem (incidence geometry). In graph theory, the De Bruijn–Erdős theorem, proved by Nicolaas Govert de Bruijn and… …   Wikipedia

  • Paradoxes of set theory — This article contains a discussion of paradoxes of set theory. As with most mathematical paradoxes, they generally reveal surprising and counter intuitive mathematical results, rather than actual logical contradictions within modern axiomatic set …   Wikipedia

  • Tree (set theory) — In set theory, a tree is a partially ordered set (poset) ( T …   Wikipedia

  • König — is the German language word for King . Family names derived from König are also spelled without the umlaut ö as Koenig or without correct transliteration of the umlaut just as Konig. People named König or Konig *Arthur König (1856 1901), German… …   Wikipedia

  • König's lemma — or König s infinity lemma is a theorem in graph theory due to Dénes Kőnig (1936). It gives a sufficient condition for an infinite graph to have an infinitely long path. The computability aspects of this theorem have been thoroughly investigated… …   Wikipedia

  • Easton's theorem — In set theory, Easton s theorem is a result on the possible cardinal numbers of powersets. W. B. harvtxt|Easton|1970 (extending a result of Robert M. Solovay) showed via forcing that : kappa < operatorname{cf}(2^kappa),and, for kappale lambda,,… …   Wikipedia

  • Dénes Kőnig — Born September 21, 1884(1884 09 21) Budapest …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.