Cardinal arithmetic

Cardinal sums are cardinalities of disjoint unions, products are cardinalities of Cartesian products, and exponentials ${\kappa }^{\lambda }$ count functions from a set of size $\lambda$ to one of size $\kappa$.

Cardinal exponentiation counts functions from a set of size $\lambda$ to one of size $\kappa$. The currying law for cardinal exponentiation gives $({\kappa }^{\lambda }{)}^{\mu }={\kappa }^{\lambda \cdot \mu }$. These are cardinal operations, distinct from ordinal exponentiation. For example the Generalized continuum hypothesis specifies $2^{\kappa }={\kappa }^{+}$ at infinite cardinals.

Assume the Generalized continuum hypothesis. For necessity, König theorem for cardinal numbers gives ${\rho }^{\mathrm{cf}(\rho )}>\rho$ for every infinite cardinal. But $\lambda ={\kappa }^{\mu }$ implies ${\lambda }^{\mu }=\lambda$ by the currying law for cardinal exponentiation, so $\mathrm{cf}(\lambda )>\mu$. This direction uses only ZFC. Conversely, uncountable cofinality bounds the range of every countable sequence in $\lambda$. Under GCH, each smaller infinite cardinal $\nu$ satisfies ${\nu }^{{\aleph }_0}\le 2^{\nu }={\nu }^{+}\le \lambda$. There are only $\lambda$ ordinal bounds to consider, giving ${\lambda }^{{\aleph }_0}=\lambda$ and the representation with base $\lambda$ and exponent ${\aleph }_0$.

The cardinal product is the cardinality of the set of functions $f$ on the index set with $f(i)<{\kappa }_i$ at every coordinate. The empty product is one, because it contains the empty function. A zero factor makes a nonempty-index product zero. In ZFC, a family of nonzero cardinals has nonzero product by the axiom of choice.

The cardinal sum is the cardinality of the disjoint union of sets of the specified sizes. Using initial ordinals, this is $|\{(i,\xi ):i\in I,\xi <{\kappa }_i\}|$. The tags distinguish overlapping summands. The empty sum is zero.

For an infinite well-orderable cardinal number $\kappa$, each strict total order is a subset of ${\kappa }^2$, giving at most $2^{\kappa }$ possibilities by the square of an infinite cardinal. For a lower bound, order $\kappa$ two-element blocks by the ordinal index and independently reverse each block according to a subset of $\kappa$. Transport along $\kappa \times 2\cong \kappa$. Distinct subsets give distinct orders. The usual axiom of choice development supplies these product identities; for well-orderable cardinals they are already provable in ZF.

For an infinite cardinal number, $\gimel (\kappa )={\kappa }^{\mathrm{cf}(\kappa )}$. The singular cardinals hypothesis predicts its value when $\kappa$ is a singular cardinal and $2^{\mathrm{cf}(\kappa )}<\kappa$. For a regular cardinal, its value is $2^{\kappa }$.

Choose cofinal ordinals ${\alpha }_i<\kappa$, indexed by $\mu =\mathrm{cf}(\kappa )$, and set $a_i=|{\alpha }_i|$. Then ${\sum }_i{a}_i=\kappa$ and $a_i^{+}\le \kappa$. The König theorem for cardinal numbers gives $\kappa <{\prod }_i{a}_i^{+}\le {\kappa }^{\mu }$. The estimate holds for every infinite cardinal number, regular or singular, under the usual axiom of choice convention for cardinal arithmetic.

The Gimel function determines all infinite cardinal powers. For a regular base, $2^{\kappa }=\gimel (\kappa )$. For a singular base, put $s={\sup }_{\rho <\kappa }{2}^{\rho }$ and $\theta =\mathrm{cf}(\kappa )$; then $2^{\kappa }=s^{\theta }$, which is $s$ if attained below $\kappa$ and $\gimel (s)$ otherwise. After these powers are known, fix an infinite exponent $\lambda$ and recurse on the base. Below $\lambda$ use $2^{\lambda }$; at successors use the Hausdorff formula for cardinal exponentiation. At a limit base greater than $\lambda$, put $a={\sup }_{\rho <\kappa }{\rho }^{\lambda }$. The answer is $a$ if $\mathrm{cf}(\kappa )>\lambda$ or the supremum is attained, and $\gimel (a)$ otherwise. In the nonattained cases, the cofinal-index argument identifies the cofinality of the supremum.

For every singular infinite cardinal number $\kappa$, the Gimel function has the smallest value permitted by König theorem for cardinal numbers and the exponent: ${\kappa }^{\mathrm{cf}(\kappa )}=\max \{{\kappa }^{+},2^{\mathrm{cf}(\kappa )}\}$. Where $2^{\mathrm{cf}(\kappa )}<\kappa$, this is the singular cardinals hypothesis. The hypothesis imposes no separate successor-power condition on regular cardinals.

The cardinal numbers defined by ${\beth }_0={\aleph }_0$, ${\beth }_{\alpha +1}=2^{{\beth }_{\alpha }}$, and ${\beth }_{\lambda }={\sup }_{\alpha <\lambda }{\beth }_{\alpha }$ at limit ordinals are the beth numbers. In particular ${\beth }_1=|\mathcal{P}(\omega )|$, the cardinality of the continuum. This notation distinguishes iterated power sets from the enumeration by Aleph numbers of well-orderable infinite cardinal numbers.

The Beth numbers ${\beth }_0={\aleph }_0$, ${\beth }_{n+1}=2^{{\beth }_n}$ form a strictly increasing countable sequence by Cantor's theorem. Their supremum ${\beth }_{\omega }$ has cofinality $\omega$ because no finite subset is cofinal. It exceeds $2^{{\aleph }_0}={\beth }_1$. It is also a strong limit cardinal: if $\rho <{\beth }_{\omega }$, some $n$ has $\rho <{\beth }_n$, so $2^{\rho }\le {\beth }_{n+1}<{\beth }_{\omega }$. Thus the singular cardinal example needs no Continuum hypothesis.

In ZF, let $K,L$ be nonempty. If $K\times L$ injects into $K\bigsqcup L$, then there is either an injection or a surjection from $K$ to $L$.

Indeed, extend the inverse of the given injection to a surjection $p:K\bigsqcup L\to K\times L$ by sending points outside its range to one fixed pair $(k_{\ast },l_{\ast })$. If the second coordinate of $p$ restricted to the $K$-summand covers $L$, it is the required surjection. Otherwise choose $l_0$ that it misses. Every $(k,l_0)$ then has its preimage in the $L$-summand. Except possibly for the default pair, that preimage is unique, so these preimages inject $K$ into $L$. In the exceptional case they inject $K\setminus \{k_{\ast }\}$ into $L$; either their image is all of $L$, yielding a surjection from $K$, or an omitted point extends the map to an injection from $K$.

For infinite cardinals, choice gives $\kappa +\kappa =\kappa \cdot \kappa =\kappa$. Exponentiation satisfies $({\kappa }^{\lambda }{)}^{\mu }={\kappa }^{\lambda \mu }$, while a countable sum of cardinals has size the maximum of ${\aleph }_0$ and their supremum.

A compatible transfinite family of bijections can enumerate the square of an ordinal by adjoining a new row and then the remaining new column. Starting with $g_0=\varnothing$, extend at a successor by $g_{\alpha +1}(\alpha ,\beta )={\gamma }_{\alpha }+\beta$ for $\beta \le \alpha$ and $g_{\alpha +1}(\beta ,\alpha )={\gamma }_{\alpha }+(\alpha +1)+\beta$ for $\beta <\alpha$. Thus ${\gamma }_{\alpha +1}={\gamma }_{\alpha }+(\alpha +1)+\alpha$. At limits take compatible unions. The two new domain pieces are disjoint; the column is empty at the initial step $\alpha =0$. Each step enumerates consecutive ordinal intervals, proving bijectivity by transfinite induction. Finite stages have ${\gamma }_n=n^2$. Successor and limit cardinality arguments then give the square equality for well-orderable infinite cardinals without using that equality to justify the construction.

There is a natural bijection between functions $M\to K^L$ and functions $M\times L\to K$, obtained by sending $f$ to $(m,l)\mapsto f(m)(l)$. Therefore

Assuming the axiom of choice, every infinite cardinal satisfiesOne proof takes a least counterexample $\kappa$, identifies cardinals with initial ordinals, and well-orders $\kappa \times \kappa$ first by $\max \{\alpha ,\beta \}$. Every proper initial segment then has cardinality below $\kappa$ by minimality, so the whole order has cardinality at most $\kappa$, contradicting the choice of $\kappa$.

For infinite cardinals $\kappa$ and $\lambda$, the axiom of choice and the square of an infinite cardinal giveThe maximum is a lower bound for both operations, while both are bounded above by respectively $\mu +\mu$ and ${\mu }^2$, where $\mu =\max \{\kappa ,\lambda \}$.

For finitely many infinite sets $X_1,\dots ,X_n$, choose one whose cardinality $\kappa$ is largest. Thenso the union has the same cardinality as that largest member.

Pairwise distinct cardinalities do not prevent a countable family from having a largest member. For example, take $X_1={\aleph }_{\omega }$ and $X_{n+2}={\aleph }_n$ for $n<\omega$, viewing cardinals as initial ordinals. Every later set is a subset of $X_1$, soalthough all the cardinalities are different.

If $\lambda$ is infinite and $2\le \kappa \le \lambda$, thenIndeed,

If ${\kappa }_i<{\lambda }_i$ for every $i\in I$, thenThe injection uses functions supported at one coordinate. For non-surjectivity, given any map from the disjoint union to the product, choose at coordinate $i$ a value omitted by the $i$th row; the resulting diagonal element is outside its image.

For infinite cardinals $\kappa ,\lambda$, Hausdorff's formula is

The continuum hypothesis asserts that every infinite subset of the real numbers is either countable or equinumerous with the real numbers, equivalently $2^{{\aleph }_0}={\aleph }_1$.

Every function $f:\mathbb{R}\to [\mathbb{R}{]}^{<{\omega }_1}$ has reals $x,y$ with $x\notin f(y)$ and $y\notin f(x)$. The values are countable subsets. Requiring distinct witnesses is equivalent, by first adjoining $x$ to $f(x)$. The Freiling theorem identifies this axiom with the negation of the Continuum hypothesis in ZFC.

In ZFC, the Freiling axiom of symmetry is equivalent to failure of the Continuum hypothesis. Under the hypothesis, countable initial segments of a well-order of the reals violate symmetry. When the continuum exceeds ${\aleph }_1$, the union of the countable values on an ${\aleph }_1$-sized set leaves a real outside; avoiding that real's countable value gives the two witnesses.

The generalized continuum hypothesis states that $2^{\kappa }={\kappa }^{+}$ for every infinite cardinal number $\kappa$.

Put $\kappa ={\aleph }_{\omega }$. ZFC gives ${\kappa }^{\kappa }=2^{\kappa }$. König's theorem and the shift of product coordinates give $\kappa <{\prod }_n{\aleph }_n\le {\kappa }^{{\aleph }_0}\le 2^{\kappa }$. The single instance $2^{\kappa }={\kappa }^{+}$ of the generalized continuum hypothesis therefore fixes all three displayed values. The strict lower bound explains why countable exponentiation cannot leave this singular cardinal unchanged.