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

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 }$.

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.

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.

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