PlanetMath: König's theorem

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (192)
Orphanage
Unclass'd
Unproven (496)
Corrections (23)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

König's theorem

(Theorem)

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

Theorem 1 Let $\kappa_i$ and $\lambda_i$ be cardinals, for all in some index set . If $\kappa_i<\lambda_i$ for all $i\in I$ , then

$\displaystyle \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 and be sets, for all in some index set . If $\vert A_i\vert<\vert B_i\vert$ for all $i\in I$ , then

$\displaystyle \left\vert\,\bigcup_{i\in I}A_i\right\vert<\left\vert\,\prod_{i\in I}B_i\right\vert.$

Proof. Let $\varphi\colon\bigcup_{i\in I}A_i\to\prod_{i\in I}B_i$ be a function. For each $i\in I$ we have $\vert\varphi(A_i)\vert\le\vert A_i\vert<\vert B_i\vert$ , so there is some $x_i\in B_i$ that is not equal to $(\varphi(a))(i)$ for any $a\in A_i$ . Define $f\colon I\to\bigcup_{i\in I}B_i$ by

for all $i\in I$ . For any $i\in I$ and any $a\in A_i$ , we have $f(i)\ne(\varphi(a))(i)$ , so $f\ne\varphi(a)$ . Therefore

is not in the image of $\varphi$ . This shows that there is no surjection from $\bigcup_{i\in I}A_i$ onto $\prod_{i\in I}B_i$ . As $\prod_{i\in I}B_i$ is nonempty, this also means that there is no injection from $\prod_{i\in I}B_i$ into $\bigcup_{i\in I}A_i$ . This completes the proof of Theorem 2. Theorem 1 follows as an immediate corollary. $\qedsymbol$

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 $\kappa_i=1$ and $\lambda_i=2$ for all .

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

"König's theorem" is owned by yark.

(view preamble)