Back to the index. Or to the chambers

This article has 14 links. View as Cloud or List.

Proof Axiom Of Choice Surjective Indexing Set Diagonal Function Zermelo Fraenkel Axioms Cardinal Number Implication Injective Function Generalized Cartesian Product Cardinal Arithmetic Proof Of Cantors Theorem Cantors Theorem

Loading ...

Planetmath Browser (2008—2009)

BSD licence | A django site

All articles taken from PlanetMath.org snapshot under CC-BY-SA licence.

→ The original article on PlanetMath.org

Other Formats: LaTeX

New! You can click on formulas to copy the LaTeX source to your clipboard. | Math Videos

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

1	Diagonal
1	Proof
1	Cardinal Number
1	Surjective
1	Function
1	Axiom Of Choice
1	Indexing Set
1	Injective Function
1	Zermelo Fraenkel Axioms
1	Implication
2	Cardinal Arithmetic
2	Generalized Cartesian Product
4	Cantors Theorem
5	Proof Of Cantors Theorem