Past exam of the analytic topology and axiomatic set theory course of the University of Oxford / 2008 / B / 7

König theorem for cardinal numbers states that if ${\kappa }_i<{\lambda }_i$ for each index $i\in I$, thenRepresent each cardinal by its initial ordinal, let $A=\{(i,\alpha ):i\in I,\alpha <{\kappa }_i\}$, and let $B={\prod }_{i\in I}{\lambda }_i$.

First there is an injection $A\to B$: encode $(i,\alpha )$ by the function which is zero away from $i$ and takes value $\alpha +1$ at $i$. The nonzero coordinate identifies $i$, and its value identifies $\alpha$. It is valid because $\alpha +1\le {\kappa }_i<{\lambda }_i$; an index with ${\kappa }_i=0$ contributes no domain points.

For strictness suppose a surjection $F:A\to B$ existed. At coordinate $i$, the values $F(i,\alpha )(i)$ for $\alpha <{\kappa }_i$ occupy fewer than ${\lambda }_i$ possibilities. Choose $b_i$ as the least ordinal below ${\lambda }_i$ absent from that set. The resulting $b=(b_i)\in B$ differs from $F(i,\alpha )$ at coordinate $i$ for every $(i,\alpha )\in A$, contradicting surjectivity.

An injection $B\to A$ would produce a surjection $A\to B$ by inverting on its image and assigning the zero function elsewhere. It is therefore impossible. The injection in the first direction and impossibility of the reverse give the strict cardinal inequality. This diagonal argument uses the canonical well-orders of the specified cardinals to choose missing coordinate values, rather than an unexplained arbitrary choice at that step.

For an infinite cardinal regarded as an ordinal, its cofinality $\theta =\mathrm{cf}(\kappa )$ is the least cardinality of a cofinal subset of $\kappa$. Equivalently there is a family $({\alpha }_i{)}_{i<\theta }$ of ordinals below $\kappa$ whose supremum is $\kappa$, and no smaller indexed family has that property. Since an infinite initial ordinal is a limit ordinal, $\theta$ is infinite and in particular nonzero.

Use the diagonal mechanism of König theorem for cardinal numbers directly. Suppose $F:\kappa \to {}^{\theta }\kappa$ were surjective. For each $i<\theta$, the sethas cardinality at most $|{\alpha }_i|<\kappa$. Choose the least $b_i\in \kappa \setminus E_i$. The resulting function $b:\theta \to \kappa$ is not in the range: for any $\alpha <\kappa$, cofinality supplies $i$ with $\alpha <{\alpha }_i$, and then $b_i\ne F(\alpha )(i)$.

Thus no such surjection exists. Constant functions provide an injection $\kappa \to {}^{\theta }\kappa$, and an injection in the reverse direction would give a surjection by the same inverse-and-default construction as in part (i). ConsequentlyThis argument also handles $\kappa ={\aleph }_0$, when cofinal initial segments are finite; it does not incorrectly assume that smaller cardinals themselves must form a cofinal sequence in every infinite cardinal.

In the usual arithmetic under the axiom of choice of cardinal numbers, take the singular strong-limit cardinalCantor's theorem makes this sequence strictly increasing. It is countable and cofinal in its supremum, so $\mathrm{cf}(\kappa )\le {\aleph }_0$. No finite subset is cofinal in this limit ordinal, hence $\mathrm{cf}(\kappa )={\aleph }_0$. ThereforeThis construction needs no assumption such as the Continuum hypothesis. The conventional use of cardinals here includes well-orderability of these power sets, supplied by the axiom of choice. It is a separate setting from the explicit failure of well-orderability hypothesized in question 8; one must not impose choice on that later hypothesis.