nLab
König's theorem

In set theory, König’s theorem, due to Julius König (Hungarian: Gyula Kőnig), is a basic result in cardinal arithmetic. It uses the axiom of choice. It is not to be confused however with König's lemma?, another result of combinatorial set theory, but using instead the axiom of dependent choice (and due to the son, Dénes Kőnig).

Theorem

(König) Let |X|{|X|} be the cardinality of a set XX. If |A i|<|B i|{|A_i|} \lt {|B_i|} for all iIi \in I, then | iA i|<| iB i|{|\sum_i A_i|} \lt {|\prod_i B_i|}.

Proof

Suppose we have proper inclusions f j:A jB jf_j: A_j \hookrightarrow B_j. Choose basepoints x jB jA jx_j \in B_j \setminus A_j and, letting iB iπ jB j\prod_i B_i \stackrel{\pi_j}{\to} B_j be the product projection and A ji j iA iA_j \stackrel{i_j}{\to} \sum_i A_i the coproduct inclusion, define a map f: jA j jB jf: \sum_j A_j \to \prod_j B_j:

(π jfi k)(a) = f j(a) ifaA kandj=k = x j ifaA kandjk\array{ (\pi_j \circ f \circ i_k)(a) & = & f_j(a) & \; if \; a \in A_k \; and \; j = k \\ & = & x_j & \; if \; a \in A_k \; and \; j \neq k }

It is immediate that this ff is injective, and so | iA i|| iB i|{|\sum_i A_i|} \leq {|\prod_i B_i|}.

Now we prove the last inequality is strict. Suppose to the contrary that there exists a surjective function f: iA i iB if: \sum_i A_i \to \prod_i B_i. The function f j=π jfi j:A jB jf_j = \pi_j \circ f \circ i_j: A_j \to B_j is not surjective, by the hypothesis |A j|<|B j|{|A_j|} \lt {|B_j|}. Thus for each jIj \in I we may choose b jB jb_j \in B_j such that b jIm(f j)b_j \notin Im(f_j). By supposition, there exists a iA ia \in \sum_i A_i such that f(a)=(b j) jIf(a) = (b_j)_{j \in I}. But aA ja \in A_j for some jIj \in I, whence π jf(a)=f j(a)\pi_j f(a) = f_j(a), i.e., b j=f j(a)b_j = f_j(a), and this contradicts how we chose b jb_j.

One can see immediately how the axiom of choice enters the result: the product iB i\prod_i B_i might be empty otherwise, hence could not satisfy the required inequality. In fact one can prove the axiom of choice from König’s theorem, in the form of “every product of a family of inhabited sets is inhabited”, by taking A iA_i to be empty for each ii.

The following important corollary deserves to be called König’s corollary, since it is itself often referred to in the literature, but only ever as a follow-on from the above theorem. Note that we do not need to appeal to the full strength of König’s theorem to prove this corollary.

Corollary

For any infinite cardinal κ\kappa, the cardinal 2 κ2^\kappa has cofinality greater than κ\kappa.

Proof

We have 2 κ=2 κ×κ=(2 κ) κ2^\kappa = 2^{\kappa \times \kappa} = (2^\kappa)^\kappa. If (λ α) α<κ(\lambda_\alpha)_{\alpha \lt \kappa} is an increasing sequence with least upper bound 2 κ2^\kappa, then we have surjection α<κλ α2 κ=(2 κ) κ\sum_{\alpha \lt \kappa} \lambda_\alpha \to 2^\kappa = (2^\kappa)^\kappa which immediately contradicts König’s theorem.

The appeal to the axiom of choice in the form discussed above is unnecessary, since 2 κ= iκ22^\kappa = \prod_{i\in \kappa} 2 is obviously inhabited. However, there are other ways in which choice-specific features make themselves known, for instance 2 κ2^\kappa is a cardinal (i.e. has a well-ordering). And the statement that every infinite cardinal κ\kappa satisfies κκ×κ\kappa \simeq \kappa \times \kappa is equivalent to the axiom of choice. And lastly, the definition of cofinality is very difficult in the absence of AC, see for instance this blog post by Karagila.

Last revised on November 21, 2018 at 10:59:09. See the history of this page for a list of all contributions to it.