Cardinal Arithmetic, Cofinality and the Alephs

Call a set $X$ well-orderable when some relation well-orders it (Well-order and well-ordered set). Work in ZF, with no choice principle. Then:

(a) $X$ is well-orderable if and only if $X\approx \alpha$ (Equinumerous sets, $A\approx B$ and $A⪯B$) for some ordinal $\alpha$ (Ordinal (von Neumann)).

(b) If $X$ is well-orderable there is a least ordinal equinumerous with $X$. It is written $\mid X\mid$ and called the cardinality of $X$.

(c) $\mid X\mid$ is a cardinal (Cardinal (initial ordinal) and cardinality).

(d) If $X\approx Y$ and $X$ is well-orderable, then $Y$ is well-orderable and $\mid Y\mid =\mid X\mid$.

(e) $\mid \alpha \mid \le \alpha$ for every ordinal $\alpha$, and $\mid \alpha \mid =\alpha$ exactly when $\alpha$ is a cardinal.

Assuming the Axiom of Choice (The Axiom of Choice) every set is well-orderable (The well-ordering theorem), so $\mid X\mid$ is then defined for every set and is exactly the cardinality of Cardinal (initial ordinal) and cardinality.

Why this item exists. Cardinal (initial ordinal) and cardinality introduces $\mid X\mid$ under the hypothesis "Assume the Axiom of Choice", and it needs that hypothesis only to know that $X$ carries a well-order at all. Everything below is about well-orderable sets and is a theorem of ZF, which is what makes it possible to state Hessenberg's theorem and Tarski's theorem, one of which is choice-free and the other of which is precisely about the gap between ZF and ZFC.

What is choice-free and what is not. Claims (a) to (e) are theorems of ZF: they say what happens for a well-orderable set, and the hypothesis of well-orderability is carried explicitly rather than supplied by an axiom. The Axiom of Choice enters only in the last step, where it removes the hypothesis by making every set well-orderable. Without choice a set may be equinumerous with no ordinal at all, and then $\mid X\mid$ simply does not exist; that is the situation Hartogs: an ordinal that does not inject into a given set is designed for.

Nothing is chosen. The one place a selection might be expected is step 2.1, and there the element taken is the $\in$-least member of $C$, which is determined by $C$ and not selected from it. Step 3.1 then shows that the bound ${\alpha }^{+}$, which exists only to turn "the least ordinal equinumerous with $X$" into an instance of Separation over a set, does not affect the answer.

Notation. From here on $\mid X\mid$ always means the ordinal of claim (b). For a finite set this is not yet known to agree with the natural number written $\mid A\mid$ in The cardinality $\mid A\mid$ of a finite set; that agreement is a theorem and is proved on this page.

For sets $A$ and $B$ write

$A\bigsqcup B:=(\{0\}\times A)\cup (\{1\}\times B),{}^{B}A:=\{h:h\text{ is a function }B\to A\},$

so $A\bigsqcup B$ is the disjoint union, made disjoint by tagging, and ${}^{B}A$ is the set of all functions from $B$ to $A$. Work in ZF. Then:

(a) Representative independence. If $A\approx A^{\mathrm{\prime }}$ and $B\approx B^{\mathrm{\prime }}$ (Equinumerous sets, $A\approx B$ and $A⪯B$) then

$A\bigsqcup B\approx A^{\mathrm{\prime }}\bigsqcup B^{\mathrm{\prime }},A\times B\approx A^{\mathrm{\prime }}\times B^{\mathrm{\prime }},{}^{B}A\approx {}^{B^{\mathrm{\prime }}}{A}^{\mathrm{\prime }}\mathrm{.}$

(b) Power sets. If $A\approx B$ then $\mathcal{P}(A)\approx \mathcal{P}(B)$.

(c) Two operations are choice-free. For ordinals $\alpha$ and $\beta$ (Ordinal (von Neumann)) the sets $\alpha \bigsqcup \beta$ and $\alpha \times \beta$ carry explicitly defined well-orders (Well-order and well-ordered set), so each is equinumerous with an ordinal and each has a cardinality $\mid \alpha \bigsqcup \beta \mid$, $\mid \alpha \times \beta \mid$ in ZF (A set equinumerous with some ordinal has a least such ordinal, that ordinal is a cardinal, and equinumerous sets get the same one; no choice principle is used).

(d) The third is not. Nothing here well-orders ${}^{\beta }\alpha$, and no argument on this page does. Assuming the Axiom of Choice (The Axiom of Choice) every set is well-orderable (The well-ordering theorem) and ${}^{\beta }\alpha$ has a cardinality like any other set; that is where cardinal exponentiation gets its hypothesis.

Why the disjoint union is tagged. $A\cup B$ is not an invariant of $A\approx A^{\mathrm{\prime }}$ and $B\approx B^{\mathrm{\prime }}$: taking $A=A^{\mathrm{\prime }}=B=\{0\}$ and $B^{\mathrm{\prime }}=\{1\}$ gives $A\cup B=\{0\}$ and $A^{\mathrm{\prime }}\cup B^{\mathrm{\prime }}=\{0,1\}$, which are not equinumerous. Tagging with $0$ and $1$ makes the two blocks disjoint whatever the sets were, and claim (a) is then true as stated. This is why the operation defined on this page is $\bigsqcup$ and never $\cup$.

The lexicographic order is not the order used for Hessenberg's theorem. Step 1.7 well-orders $\alpha \times \beta$, which is everything claim (c) asks for. Its order type is in general much larger than $\alpha$: the lexicographic order on $\omega \times \omega$ has order type $\omega \cdot \omega$. The proof that $\mid \kappa \times \kappa \mid =\kappa$ for infinite $\kappa$ uses a different, cleverer well-order and is Hessenberg: $\kappa \otimes \kappa =\kappa$ for every infinite cardinal $\kappa$, proved in ZF from the canonical well-order of $\kappa \times \kappa$.

Where the asymmetry between $\otimes$ and exponentiation comes from. A product of two well-ordered sets is well-ordered by an order written down from the two given ones. A set of functions between well-ordered sets has no such canonical order: the obvious candidates need a choice at each argument. That is not a defect of this proof but the reason general cardinal exponentiation is stated with the Axiom of Choice on this page; the exponential unit laws (Commutativity, associativity, distributivity and monotonicity of $\oplus$ and $\otimes$, the unit laws, the two exponent laws, and $\kappa \le \lambda$ if and only if $\kappa$ injects into $\lambda$) and the finite case (Every natural number and $\omega$ are cardinals, every infinite cardinal is a limit ordinal, and on the natural numbers the cardinal operations are the published finite counting operations, with $\mid A\mid$ in the finite sense equal to $\mid A\mid$ in the cardinal sense) are choice-free, because the function sets they count carry a canonical well-order.

Let $\kappa$ and $\lambda$ be cardinals (Cardinal (initial ordinal) and cardinality), and recall the notation of Disjoint union, cartesian product, function space and power set respect equinumerosity, and for ordinals $\alpha ,\beta$ the sets $\alpha \bigsqcup \beta$ and $\alpha \times \beta$ carry explicit well-orders, so their cardinalities exist in ZF:

$\kappa \bigsqcup \lambda =(\{0\}\times \kappa )\cup (\{1\}\times \lambda ),{}^{\lambda }\kappa =\{h:h\text{ is a function }\lambda \to \kappa \}\mathrm{.}$

Sum and product.

$\kappa \oplus \lambda :=\mid \kappa \bigsqcup \lambda \mid ,\kappa \otimes \lambda :=\mid \kappa \times \lambda \mid \mathrm{.}$

Both values exist in ZF and are cardinals: claim (c) of Disjoint union, cartesian product, function space and power set respect equinumerosity, and for ordinals $\alpha ,\beta$ the sets $\alpha \bigsqcup \beta$ and $\alpha \times \beta$ carry explicit well-orders, so their cardinalities exist in ZF well-orders each of the two sets explicitly, and A set equinumerous with some ordinal has a least such ordinal, that ordinal is a cardinal, and equinumerous sets get the same one; no choice principle is used then supplies the least equinumerous ordinal. No choice principle is used.

Exponentiation.

${\kappa }^{\lambda }:=\mid {}^{\lambda }\kappa \mid ,$

the number of functions from a set of size $\lambda$ to a set of size $\kappa$. The right-hand side is defined exactly when ${}^{\lambda }\kappa$ is well-orderable. Assuming the Axiom of Choice (The Axiom of Choice) every set is well-orderable (The well-ordering theorem) and ${\kappa }^{\lambda }$ is defined for all cardinals; every statement on this page that writes ${\kappa }^{\lambda }$ for an infinite exponent says so in its own hypotheses.

Transport to arbitrary sets. If $A$ and $B$ are well-orderable with $\mid A\mid =\kappa$ and $\mid B\mid =\lambda$, then

$\mid A\bigsqcup B\mid =\kappa \oplus \lambda ,\mid A\times B\mid =\kappa \otimes \lambda ,\mid {}^{B}A\mid ={\kappa }^{\lambda }$

whenever the sets on the left have cardinalities at all, because $A\approx \kappa$ and $B\approx \lambda$ (Equinumerous sets, $A\approx B$ and $A⪯B$) and the three constructions respect $\approx$ (claim (a) of Disjoint union, cartesian product, function space and power set respect equinumerosity, and for ordinals $\alpha ,\beta$ the sets $\alpha \bigsqcup \beta$ and $\alpha \times \beta$ carry explicit well-orders, so their cardinalities exist in ZF, Injection, surjection, bijection). So the operations may be computed from any representatives.

Finite and infinite cardinals. A cardinal $\kappa$ is finite when $\kappa \in \omega$ and infinite when $\omega \subseteq \kappa$, that is $\omega \le \kappa$; by trichotomy (Trichotomy and well-ordering of the ordinals) and $\omega$ is the least limit ordinal every cardinal is exactly one of the two.

The symbols $\oplus$ and $\otimes$ are not decoration. Ordinal addition and ordinal multiplication (Ordinal addition $\alpha +\beta$, Ordinal multiplication $\alpha \cdot \beta$) are defined on the same objects — cardinals are ordinals — and give different values. With $\omega$ read as a cardinal, $\omega \oplus \omega =\omega$, whereas the ordinal sum $\omega +\omega$ is strictly larger than $\omega$; and $\omega \otimes \omega =\omega$, whereas the ordinal product $\omega \cdot \omega$ is larger still. Writing both operations with $+$ and $\cdot$ would make every equation on this page ambiguous, so the cardinal operations get their own symbols and the plain $+$ and $\cdot$ on this page always mean the ordinal ones.

Exponentiation keeps the symbol, under a hard rule. There is no comparably readable alternative to ${\kappa }^{\lambda }$, and Ordinal ${\alpha }^{\beta }$ and cardinal ${\kappa }^{\lambda }$ are different operations that share one notation already records that ${\alpha }^{\beta }$ is used for two different operations: as ordinals $2^{\omega }=\omega$, while the cardinal $2^{\omega }$ counts the functions $\omega \to \{0,1\}$ and is uncountable. The rule adopted here, and followed on this page and its companion, is:

In an exponential, the base and the exponent are always alephs, letters or expressions denoting cardinals — $\kappa$, $\lambda$, $\mu$, $\mathfrak{c}$, $\mathrm{cf}(\kappa )$, $\mid A\mid$ — or a natural number read as a cardinal; never $\omega$, never ${\omega }_1$, and never a letter denoting an ordinal, such as $\alpha ,\beta ,\gamma ,\xi ,\eta$.

So $2^{{\mathrm{\aleph }}_0}$, ${\kappa }^{\lambda }$ and ${\mathrm{\aleph }}_1^{{\mathrm{\aleph }}_0}$ are cardinal exponentials, and an expression such as ${\omega }^{\omega }$ or ${\alpha }^{\beta }$ is never written here at all. Where a value has to be named in both readings, the two are given different letters.

What is being counted, in each case. $\kappa \oplus \lambda$ is the size of two disjoint blocks laid side by side; the tagging in $\bigsqcup$ is what makes "disjoint" true even though one of $\kappa$ and $\lambda$ is always a subset of the other, so their intersection is the smaller of the two. $\kappa \otimes \lambda$ is the size of a rectangle. ${\kappa }^{\lambda }$ is the number of ways to choose a value in $\kappa$ for each of $\lambda$ positions, independently. None of the three is sensitive to the order in which the elements are arranged, which is exactly what distinguishes them from the ordinal operations (Ordinal exponentiation ${\alpha }^{\beta }$, with the conventions ${\alpha }^0=1$ and $0^0=1$ included), whose values depend on the arrangement.

The zero and one cases are not special. $0=\mathrm{\varnothing }$ and $1=\{0\}$ are cardinals (Ordinal (von Neumann)), and the definitions apply to them unchanged: $\kappa \bigsqcup 0=\{0\}\times \kappa$, $\kappa \times 0=\mathrm{\varnothing }$, and ${}^0\kappa =\{\mathrm{\varnothing }\}$ has exactly one element, the empty function. The resulting unit laws are proved rather than stipulated, in Commutativity, associativity, distributivity and monotonicity of $\oplus$ and $\otimes$, the unit laws, the two exponent laws, and $\kappa \le \lambda$ if and only if $\kappa$ injects into $\lambda$.

Let $\kappa$, $\lambda$, $\mu$ be cardinals (Cardinal (initial ordinal) and cardinality) and let $\oplus$, $\otimes$, ${\kappa }^{\lambda }$ be as in Cardinal sum $\kappa \oplus \lambda$, product $\kappa \otimes \lambda$ and exponentiation ${\kappa }^{\lambda }$, and why they are written apart from the ordinal operations. Clauses (a) to (e) are theorems of ZF; the clauses naming an exponential hold whenever those exponentials are defined, in particular under the Axiom of Choice (The Axiom of Choice).

(a) Comparison. $\kappa \le \lambda$ if and only if $\kappa ⪯\lambda$, that is, if and only if there is an injection $\kappa \to \lambda$ (Equinumerous sets, $A\approx B$ and $A⪯B$). More generally, if $A$ and $B$ are well-orderable and $A⪯B$ then $\mid A\mid \le \mid B\mid$.

(b) Commutativity and associativity. $\kappa \oplus \lambda =\lambda \oplus \kappa$, $\kappa \otimes \lambda =\lambda \otimes \kappa$, $(\kappa \oplus \lambda )\oplus \mu =\kappa \oplus (\lambda \oplus \mu )$ and $(\kappa \otimes \lambda )\otimes \mu =\kappa \otimes (\lambda \otimes \mu )$.

(c) Distributivity. $\kappa \otimes (\lambda \oplus \mu )=(\kappa \otimes \lambda )\oplus (\kappa \otimes \mu )$.

(d) Units. $\kappa \oplus 0=\kappa$, $\kappa \otimes 0=0$, $\kappa \otimes 1=\kappa$, and ${\kappa }^0=1$, ${\kappa }^1=\kappa$, $1^{\kappa }=1$, together with $0^{\kappa }=0$ for $\kappa \mathrm{\ne }0$. The four exponential unit laws need no choice principle, because the function sets they count are empty, a singleton, or a copy of $\kappa$.

(e) Monotonicity. If $\kappa \le \lambda$ then $\kappa \oplus \mu \le \lambda \oplus \mu$ and $\kappa \otimes \mu \le \lambda \otimes \mu$; and ${\kappa }^{\mu }\le {\lambda }^{\mu }$, and ${\mu }^{\kappa }\le {\mu }^{\lambda }$ provided $\mu \mathrm{\ne }0$.

(f) The two exponent laws. ${\kappa }^{\lambda \oplus \mu }={\kappa }^{\lambda }\otimes {\kappa }^{\mu }$ and $({\kappa }^{\lambda }{)}^{\mu }={\kappa }^{\lambda \otimes \mu }$.

Each clause is an equality or an inequality of cardinals, not merely of sizes: each side is an ordinal, and the claim is that the two ordinals are the same.

Why clause (a) is the workhorse. Every other clause is proved by writing down a bijection or an injection between two concrete sets; clause (a) is what converts such a map into a statement about the ordinals $\kappa$ and $\lambda$, and it is the only clause whose proof uses The Schröder-Bernstein theorem. Note the direction of the work there: $\kappa \le \lambda \Rightarrow \kappa ⪯\lambda$ is the trivial half, and the converse is where being a cardinal rather than an arbitrary ordinal is spent.

No cancellation, and no strict monotonicity. Clause (e) gives $\le$ and not $<$, and that is not a weakness of the proof. The false statements FALSE: $\kappa \oplus \mu =\lambda \oplus \mu$ implies $\kappa =\lambda$ and FALSE: $\kappa <\lambda$ implies ${\kappa }^{\mu }<{\lambda }^{\mu }$, on this page, show that $\kappa \oplus \mu =\lambda \oplus \mu$ does not force $\kappa =\lambda$ and that $\kappa <\lambda$ does not force ${\kappa }^{\mu }<{\lambda }^{\mu }$; both failures are already visible at ${\mathrm{\aleph }}_0$.

The exponent laws hold at every value, including the degenerate ones. With $\lambda =\mu =0$ the first law reads ${\kappa }^0={\kappa }^0\otimes {\kappa }^0$, that is $1=1\otimes 1$, and with $\kappa =0$ and $\mu =0$ the second reads $(0^{\lambda }{)}^0=0^0=1$, both correct from clause (d). Nothing in the proof of clause (f) case-splits on whether an exponent is zero, because the bijections of step 1.6 are between sets of functions and remain bijections when one of the domains is empty.

Work in ZF; no choice principle is used. Let $\mathbb{N}=\omega$ be the von Neumann naturals (The natural numbers $\mathbb{N}$ (von Neumann)), and let ${+}_{\mathbb{N}}$, ${\cdot }_{\mathbb{N}}$ and $m^n$ be the natural-number operations (Exponentiation of natural numbers, $m^n$, and its agreement with the integer power in $\mathbb{R}$ for the power). Then:

(a) Every natural number is a cardinal (Cardinal (initial ordinal) and cardinality), and $\omega$ is a cardinal.

(b) Every infinite cardinal is a limit ordinal (Successor and limit ordinals).

(c) One notation, one meaning. If $A$ is finite (Finite, countably infinite, countable, uncountable) then $A$ is well-orderable and the natural number $\mid A\mid$ of The cardinality $\mid A\mid$ of a finite set is the cardinal $\mid A\mid$ of A set equinumerous with some ordinal has a least such ordinal, that ordinal is a cardinal, and equinumerous sets get the same one; no choice principle is used.

(d) One arithmetic. For $m,n\in \omega$, read as cardinals,

$m\oplus n=m{+}_{\mathbb{N}}n,m\otimes n=m{\cdot }_{\mathbb{N}}n,m^n\text{ as a cardinal }=m^n\text{ as a natural number},$

the natural-number power being that of Exponentiation of natural numbers, $m^n$, and its agreement with the integer power in $\mathbb{R}$ and the cardinal exponential being defined in ZF here because the function set it counts is finite. Moreover $m\oplus n$ and $m\otimes n$ are also the ordinal sum and product of $m$ and $n$ (On $\omega$ the ordinal $+$ and $\cdot$ are the Peano operations: $\omega$ is closed under ordinal $+$, $\cdot$ and exponentiation, and for naturals $m,n$ the ordinal $m+n$ and $m\cdot n$ are the natural-number sum and product). No agreement is claimed between the cardinal power and the ordinal power; On $\omega$ the ordinal $+$ and $\cdot$ are the Peano operations: $\omega$ is closed under ordinal $+$, $\cdot$ and exponentiation, and for naturals $m,n$ the ordinal $m+n$ and $m\cdot n$ are the natural-number sum and product itself claims none for exponentiation, and none is needed below.