# König’s theorem

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

###### Theorem 1.

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

###### Theorem 2.

Let ${A}_{i}$ and ${B}_{i}$ be sets, for all $i$ in some index set $I$. If $$ for all $i\mathrm{\in}I$, then

$$ |

###### Proof.

Let $\phi :{\bigcup}_{i\in I}{A}_{i}\to {\prod}_{i\in I}{B}_{i}$ be a function.
For each $i\in I$ we have $$,
so there is some ${x}_{i}\in {B}_{i}$
that is not equal to $(\phi (a))(i)$ for any $a\in {A}_{i}$.
Define $f:I\to {\bigcup}_{i\in I}{B}_{i}$
by $f(i)={x}_{i}$ for all $i\in I$.
For any $i\in I$ and any $a\in {A}_{i}$,
we have $f(i)\ne (\phi (a))(i)$, so $f\ne \phi (a)$.
Therefore $f$ is not in the image of $\phi $.
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.
∎

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 $i$.

Also note that Theorem 2 is equivalent^{} (in ZF) to the Axiom of Choice^{}, as it implies that products (http://planetmath.org/GeneralizedCartesianProduct) of nonempty sets are nonempty. (Theorem 1, on the other hand, is not meaningful without the Axiom of Choice.)

Title | König’s theorem |

Canonical name | KonigsTheorem |

Date of creation | 2013-03-22 14:10:21 |

Last modified on | 2013-03-22 14:10:21 |

Owner | yark (2760) |

Last modified by | yark (2760) |

Numerical id | 15 |

Author | yark (2760) |

Entry type | Theorem |

Classification | msc 03E10 |

Synonym | Koenig’s theorem |

Synonym | Konig’s theorem |

Synonym | König-Zermelo theorem |

Synonym | Koenig-Zermelo theorem |

Synonym | Konig-Zermelo theorem |

Related topic | CantorsTheorem |