Math for the people, by the people.

User login

You are here

Home ›

K\"onig's theorem

Primary tabs

König’s theorem

König’s Theorem is a theorem of cardinal arithmetic.

Theorem 1.

Let κisubscriptκi\kappa_{i} and λisubscriptλi\lambda_{i} be cardinals, for all iii in some index set III. If κi<λisubscriptκisubscriptλi\kappa_{i}<\lambda_{i} for all i∈IiIi\in I, then

∑i∈Iκi<∏i∈Iλi.subscriptiIsubscriptκisubscriptproductiIsubscriptλi\sum_{{i\in I}}\kappa_{i}<\,\prod_{{i\in I}}\lambda_{i}.

The theorem can also be stated for arbitrary sets, as follows.

Theorem 2.

Let AisubscriptAiA_{i} and BisubscriptBiB_{i} be sets, for all iii in some index set III. If |Ai|<|Bi|subscriptAisubscriptBi|A_{i}|<|B_{i}| for all i∈IiIi\in I, then

|⋃i∈IAi|<|∏i∈IBi|.subscriptiIsubscriptAisubscriptproductiIsubscriptBi\left|\,\bigcup_{{i\in I}}A_{i}\right|<\left|\,\prod_{{i\in I}}B_{i}\right|.
Proof.

Let φ:⋃i∈IAi→∏i∈IBinormal-:φnormal-→subscriptiIsubscriptAisubscriptproductiIsubscriptBi\varphi\colon\bigcup_{{i\in I}}A_{i}\to\prod_{{i\in I}}B_{i} be a function. For each i∈IiIi\in I we have |φ⁢(Ai)|≤|Ai|<|Bi|φsubscriptAisubscriptAisubscriptBi|\varphi(A_{i})|\leq|A_{i}|<|B_{i}|, so there is some xi∈BisubscriptxisubscriptBix_{i}\in B_{i} that is not equal to (φ⁢(a))⁢(i)φai(\varphi(a))(i) for any a∈AiasubscriptAia\in A_{i}. Define f:I→⋃i∈IBinormal-:fnormal-→IsubscriptiIsubscriptBif\colon I\to\bigcup_{{i\in I}}B_{i} by f⁢(i)=xifisubscriptxif(i)=x_{i} for all i∈IiIi\in I. For any i∈IiIi\in I and any a∈AiasubscriptAia\in A_{i}, we have f⁢(i)≠(φ⁢(a))⁢(i)fiφaif(i)\neq(\varphi(a))(i), so f≠φ⁢(a)fφaf\neq\varphi(a). Therefore fff is not in the image of φφ\varphi. This shows that there is no surjection from ⋃i∈IAisubscriptiIsubscriptAi\bigcup_{{i\in I}}A_{i} onto ∏i∈IBisubscriptproductiIsubscriptBi\prod_{{i\in I}}B_{i}. As ∏i∈IBisubscriptproductiIsubscriptBi\prod_{{i\in I}}B_{i} is nonempty, this also means that there is no injection from ∏i∈IBisubscriptproductiIsubscriptBi\prod_{{i\in I}}B_{i} into ⋃i∈IAisubscriptiIsubscriptAi\bigcup_{{i\in I}}A_{i}. This completes the proof of Theorem 2. Theorem 1 follows as an immediate corollary. ∎

Note that the above proof is a diagonal argument, similar to the proof of Cantor’s Theorem. In fact, Cantor’s Theorem can be considered as a special case of König’s Theorem, taking κi=1subscriptκi1\kappa_{i}=1 and λi=2subscriptλi2\lambda_{i}=2 for all iii.

Also note that Theorem 2 is equivalent (in ZF) to the Axiom of Choice, as it implies that products of nonempty sets are nonempty. (Theorem 1, on the other hand, is not meaningful without the Axiom of Choice.)

Keywords: 
inequality, cardinal
Related: 
CantorsTheorem
Synonym: 
Koenig's theorem, Konig's theorem, K\"onig-Zermelo theorem, Koenig-Zermelo theorem, Konig-Zermelo theorem
Type of Math Object: 
Theorem
Major Section: 
Reference
Parent: 
cardinal arithmetic
Groups audience: 
Editing Group for KonigsTheorem

Mathematics Subject Classification

03E10 Ordinal and cardinal numbers

Comments

Submitted by Yoda of Borg on Mon, 08/20/2012 - 01:12

In the proof, you show phi is an injection, and then show that there is an element of the codomain that is not in the range of phi. From this you conclude that there is no possible surjection from phi's domain to it's codomain. This isn't the case.

Let F:N->N be f(n)=2n. The number 3 is in the codomain of f, but not in it's range, however g:N->N, g(n)=n is a surjection.

Submitted by Arthur Rubin on Mon, 08/20/2012 - 03:38

That's not what it's saying. We show an arbitrary phi, whether or not it's an injection, _cannot_ be a surjection. (The proof here omits the proof that there _is_ an injection, though.)

Submitted by Yoda of Borg on Mon, 08/20/2012 - 16:04

Hmm, it wasn't clear to me on the first several readthroughs, that phi was any arbitrary function. I took it to be a fixed function, rather than a generic representative of the set of all functions from the first space to the second. I recommend you emphasize this by stating it explicitly either in the first sentence of the proof for Theorem 2 ("Let phi:... be any function"), or later you could conclude "Since we've shown this for any arbitrary phi, there is no surjection..."

Another sticking point I had that could be improved for readability was when you defined phi as mapping to the cross-product space of B_i's, but then used phi(a) as a function whose domain is I and whose range is Union(B_i).

Since functions in set theory are subsets of cross-product spaces (with no two points in the subset sharing the same coordinates in the dimensions that make up the domain), using phi(a) as a function from I to Union(B_i) implies that phi(a) is an element of IxUnion(B_i) not an element of Product(B_i) (as implied by the codomain in the definition of phi). I tried establishing a bijection between Product(B_i) and the function space from I to Union(B_i) [a subset of the powerset of IxUnion(B_i)], and it took me a bit of time to recognize that I could do so once I restricted the function space to those functions that only matched elements from B_i to i (as opposed to matching any element of Union(B_i) to i). It clicked when I saw that these were those function that chose an element of B_i for each i - the set of choice functions on {B_i}. [If F \sub Power(IxUnion(B_i)) is the set of functions from I to Union(B_i), then the set of choice functions on {B_i} is F \intersect Power(Union({i}xB_i)).]

So the way you've defined phi, it is an abuse of notation to say (phi(a))(i). Instead you can establish a bijection theta from Product(B_i) to the set of choice functions on {B_i}. Then instead of (phi(a))(i), it would be (theta(phi(a)))(i).

Thanks,
YoB

Subscribe to Comments for "K\&quot;onig&#039;s theorem"

Info

Owner: yark
Added: 2004-02-20 - 11:56
Author(s): yark

Versions

(v15) by yark 2013-03-22
Powered By: = + + ♡