## You are here

HomeK\"onig's theorem

## Primary tabs

# König’s theorem

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

###### Theorem 1.

Let $\kappa_{i}$ and $\lambda_{i}$ be cardinals, for all $i$ in some index set $I$. If $\kappa_{i}<\lambda_{i}$ for all $i\in I$, then

$\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 $A_{i}$ and $B_{i}$ be sets, for all $i$ in some index set $I$. If $|A_{i}|<|B_{i}|$ for all $i\in I$, then

$\left|\,\bigcup_{{i\in I}}A_{i}\right|<\left|\,\prod_{{i\in I}}B_{i}\right|.$ |

###### 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 $|\varphi(A_{i})|\leq|A_{i}|<|B_{i}|$, 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 $f(i)=x_{i}$ for all $i\in I$. For any $i\in I$ and any $a\in A_{i}$, we have $f(i)\neq(\varphi(a))(i)$, so $f\neq\varphi(a)$. Therefore $f$ 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. ∎

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 of nonempty sets are nonempty. (Theorem 1, on the other hand, is not meaningful without the Axiom of Choice.)

## Mathematics Subject Classification

03E10*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff

## Recent Activity

new question: Prove that for any sets A, B, and C, An(BUC)=(AnB)U(AnC) by St_Louis

Apr 20

new image: information-theoretic-distributed-measurement-dds.png by rspuzio

new image: information-theoretic-distributed-measurement-4.2 by rspuzio

new image: information-theoretic-distributed-measurement-4.1 by rspuzio

new image: information-theoretic-distributed-measurement-3.2 by rspuzio

new image: information-theoretic-distributed-measurement-3.1 by rspuzio

new image: information-theoretic-distributed-measurement-2.1 by rspuzio

Apr 19

new collection: On the Information-Theoretic Structure of Distributed Measurements by rspuzio

Apr 15

new question: Prove a formula is part of the Gentzen System by LadyAnne

Mar 30

new question: A problem about Euler's totient function by mbhatia

## Comments

## Injection -/-> -Surjection

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.

## Re: Injection -/-> -Surjection

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

## Re: Injection -/-> -Surjection

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