nLab König's theorem

Without the axiom of choice

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.

Without the axiom of choice

However, it is possible to recover some of König’s theorem in the absence of the axiom of choice. For sets AA, BB, define (A⪰̸B)(A \nsucceq B) to be the set of assignments fn(f)f \mapsto n(f) which for each partial function f:ABf:A \rightharpoonup B specify an element n(f)Bim(f)n(f) \in B \setminus im(f). This set being nonempty imiplies a strong form of “there are no partial surjections ABA \twoheadrightarrow B” (aka A *BA \ngeq^* B), and the definition is as one might define A *BA \ngeq^* B using propositions as types. Conversely, if AC holds, then the (A⪰̸B)(A \nsucceq B) is nonempty iff A<BA \lt B.

Proposition

Given n i(A i⪰̸B i)n_i \in (A_i \nsucceq B_i) for each iIi \in I, then iA i⪰̸ iB i\sum_i A_i \nsucceq \prod_i B_i.

Proof

Let f: iA i iB if: \sum_i A_i \rightharpoonup \prod_i B_i. We define a member m(f) iB im(f) \in \prod_i B_i as m(f)(i)=n i(af(i,a)(i))m(f)(i) = n_i(a \mapsto f(i,a)(i)). Now, note that it can’t be the case that m(f)=f(i,a)m(f) = f(i,a) for any iIi \in I, aA ia \in A_i, as then f(i,a)(i)=m(f)(i)=n i(af(i,a)(i))im(af(i,a)(i))f(i,a)(i) = m(f)(i) = n_i(a \mapsto f(i,a)(i)) \notin im(a \mapsto f(i,a)(i)). This means that m(f) iB iim(f)m(f) \in \prod_i B_i \setminus \operatorname{im}(f), as required.

Although the preconditions of the theorem are harder to attain, as (A⪰̸B)(A \nsucceq B) is nonempty much less often than A<BA \lt B, it still holds in several useful cases:

Proposition

The following conditions are each sufficient to construct an element nn of A⪰̸BA \nsucceq B:

  1. m(A⪰̸B)m \in (A \nsucceq B') and an injection i:BBi:B' \hookrightarrow B

  2. m(A⪰̸B)m \in (A' \nsucceq B) and an injection i:AAi:A \hookrightarrow A'

  3. B=𝒫(A)B = \mathcal{P}(A)

  4. BB has a wellorder <\lt, and there is no partial surjection ABA \to B

  5. An element bBb \in B and, for each total function f:ABf:A \to B, a specified m(f)Bim(f)m(f) \in B \setminus im(f)

Proof
  1. For f:ABf:A \rightharpoonup B, ff restricts to a partial function f:ABf':A \rightharpoonup B' (f(a)=bf'(a) = b iff f(a)=i(b)f(a) = i(b)), and m(f)m(f') gives an element of Bim(f)B'\setminus im(f'), so taking n(f)=i(m(f))n(f') = i(m(f')) gives n(f)=i(m(f))Bim(f)n(f') = i(m(f')) \in B \setminus im(f)

  2. For f:ABf:A \rightharpoonup B, ff extends to a partial function f:ABf':A' \rightharpoonup B (defined as f(i(a))=f(a)f'(i(a)) = f(a)), and m(f)Bim(f)=Bim(f)m(f') \in B \setminus im(f) = B \setminus im(f'), so take n(f)=m(f)n(f) = m(f').

  3. Immediate from 1⪰̸21 \nsucceq 2 and the above choiceless variant of König’s theorem, but can also be proven directly. Let f:A𝒫(A)f:A \rightharpoonup \mathcal{P}(A) be a partial function, and let n(f)={aAadom(f)andaf(a)}n(f) = \{a \in A \mid a \in dom(f) and a \notin f(a)\}. Then if f(a)=n(f)f(a) = n(f), we have that an(f)a \in n(f) iff adom(f)andaf(a)a \in dom(f) and a \notin f(a), so adom(f)a \notin dom(f), contradicting f(a)=n(f)f(a) = n(f). Therefore, n(f)𝒫(A)im(f)n(f) \in \mathcal{P}(A) \setminus im(f).

  4. For f:ABf:A \rightharpoonup B, let n(f)=min{αBαim(f)}n(f) = min \{ \alpha \in B \mid \alpha \notin im(f) \}. Then n(f)n(f) is uniquely defined as BB is wellordered and the set is nonempty (otherwise f is a partial surjection), and n(f)Bim(f)n(f) \in B \setminus im(f).

  5. For f:ABf:A \rightharpoonup B, extend it to a total function f:ABf':A \to B by letting f(x)=f(x)f'(x) = f(x) where defined and f(x)=bf'(x) = b otherwise. Then m(f)Bim(f)Bim(f)m(f') \in B \setminus im(f') \subseteq B \setminus im(f), so let n(f)=m(f)n(f) = m(f').

Last revised on July 20, 2021 at 15:07:48. See the history of this page for a list of all contributions to it.