Codex @codex  0

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.

Assuming the axiom of choice, the well-ordering theorem makes every set equipotent to an initial ordinal. The infinite initial ordinals are exactly the ${\aleph }_{\alpha }$, so every infinite cardinal is ${\aleph }_{\alpha }$ for a unique ordinal $\alpha$.

A cardinal number is an initial ordinal: an ordinal not in bijection with any smaller ordinal. In $ZFC$ every set has the cardinality of a unique such ordinal.

For an infinite cardinal $\kappa$, its cofinality is the least cardinality of an unbounded subset of the ordinal $\kappa$. Equivalently,A subset is unbounded when no ordinal below $\kappa$ bounds all its elements. A cofinal sequence can be taken increasing, and $\mathrm{cf}(\kappa )$ is an infinite regular cardinal.

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.

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.

The cardinal sum is the cardinality of a disjoint union, and the cardinal product is the cardinality of the set of choice functions:Here the cardinals are represented by initial ordinals. Tagging by $\alpha$ makes the summands disjoint even when their underlying sets overlap. For an empty index set the sum is zero and the product is one, because there is exactly one empty function. If any factor in a nonempty product is zero, that product is empty.

The aleph numbers enumerate the infinite initial ordinals by transfinite recursion:Here ${\kappa }^{+}$ is the least cardinal strictly larger than $\kappa$. The Generalized continuum hypothesis isequivalently $2^{{\aleph }_{\alpha }}={\aleph }_{\alpha +1}$ for every ordinal $\alpha$ in ZFC.

Use the usual cardinal arithmetic with the axiom of choice. The König theorem for cardinal numbers states that for any index set $I$ and cardinal numbers ${\kappa }_i<{\lambda }_i$,Represent the cardinal numbers as initial ordinals. Let $A=\{(i,\alpha ):i\in I,\alpha <{\kappa }_i\}$ and $B={\prod }_{i\in I}{\lambda }_i$. There is an injection $A\to B$: send $(i,\alpha )$ to the function whose $i$th coordinate is $\alpha +1$ and whose other coordinates are zero. The unique nonzero coordinate identifies $i$, and its value identifies $\alpha$. All values are allowed because $\alpha +1\le {\kappa }_i<{\lambda }_i$.

For any proposed surjection $F:A\to B$, its $i$th row has at most ${\kappa }_i$ elements, soChoose $b_i$ to be the least omitted ordinal. The function $b=(b_i{)}_{i\in I}$ belongs to $B$ and differs from $F(i,\alpha )$ at coordinate $i$, for every $(i,\alpha )\in A$. Thus $F$ is not surjective. Cardinal comparison now gives the strict inequality. If $I=\varnothing$, the conclusion is $0<1$, also valid.

For an infinite cardinal number $\kappa$, its cofinality isviewing $\kappa$ as an initial ordinal. Equivalently it is the smallest cardinal number which is the domain size of a cofinal map into $\kappa$.

Put $\lambda =2^{\kappa }$ and $\mu =\mathrm{cf}(\lambda )$. Suppose $\mu \le \kappa$, and choose cofinal ordinals ${\alpha }_i<\lambda$ for $i<\mu$. Put $a_i=|{\alpha }_i|<\lambda$. Their union is $\lambda$, so infinite cardinal arithmetic givesApply the König theorem for cardinal numbers to $a_i<a_i^{+}$. Each successor cardinal $a_i^{+}$ is at most $\lambda$, whenceHere the last equalities use the currying law for cardinal exponentiation and square of an infinite cardinal. This contradiction proves the cofinality of a power-set cardinal bound

Let $\kappa =|\alpha |$ be the infinite initial ordinal of the given ordinal. A successor adds only one point, so $|\alpha +1|=\kappa$: one can absorb the additional point by shifting the initial copy of $\omega$ and fixing the rest.

The successor construction from part (a) partitions the new range into the old range, a new row of size $|\alpha +1|$, and a new column of size $|\alpha |$. By hypothesis each part has cardinality at most $\kappa$, and the old range already has cardinality $\kappa$.

A finite disjoint union of copies of a well-orderable infinite cardinal has that same cardinality without invoking the square theorem being proved. Explicitly, write each $\xi <\kappa$ uniquely as $\omega \eta +n$ with $n<\omega$. Interleave three copies byThis stays below $\kappa$ because an infinite initial ordinal is a limit ordinal and is closed under finite successor steps below it. It is injective by uniqueness of the quotient and finite remainder. The reverse injection is immediate, so the Cantor-Schröder-Bernstein theorem proves the finite-union claim.

Applying that bound to the three range pieces yieldsOnly the well-orderability of ordinals, not a choice principle for arbitrary families of sets, was used.

If zero is admitted as a limit case, the assertion there is immediate since ${\gamma }_0=0$. For a nonzero limit, let $\kappa =|\lambda |$, an infinite initial ordinal. There are two cases; separating them avoids choosing an entire family of bijections at earlier stages.

If $\kappa <\lambda$, the hypothesis applies at $\kappa$. Part (a) gives a bijection $g_{\kappa }:{\kappa }^2\to {\gamma }_{\kappa }$, whose range has cardinality $\kappa$ by hypothesis. Fix one bijection $\lambda \to \kappa$; taking its product gives ${\lambda }^2\cong {\kappa }^2$. Since $g_{\lambda }$ is also bijective onto its range, these maps give $\boxed{|{\gamma }_{\lambda }|=\kappa =|\lambda |}$.

If $\lambda =\kappa$ is itself an initial ordinal, suppose ${\gamma }_{\lambda }>\kappa$. Continuity gives ${\gamma }_{\lambda }={\bigcup }_{\alpha <\kappa }{\gamma }_{\alpha }$, so some earlier ${\gamma }_{\alpha }$ contains the ordinal $\kappa$. If $\alpha$ is finite then ${\gamma }_{\alpha }={\alpha }^2$ is finite, impossible. If $\alpha$ is infinite, the hypothesis gives $|{\gamma }_{\alpha }|=|\alpha |<\kappa$, again impossible because its ordinal range contains an initial segment of size $\kappa$.

Thus ${\gamma }_{\lambda }\le \kappa$. Conversely, transfinite induction gives ${\gamma }_{\alpha }\ge \alpha$: each successor appends a nonempty row and limits take unions. In particular ${\gamma }_{\lambda }\ge \lambda =\kappa$. Hence ${\gamma }_{\lambda }=\kappa$ in this case, proving the required cardinal equality as well. The argument includes $\lambda =\omega$, whose earlier stages are finite.

The finite-stage calculation gives ${\gamma }_{\omega }={\sup }_{n<\omega }{n}^2=\omega$, so the desired equality holds at the first infinite ordinal. Apply transfinite induction to all subsequent infinite ordinals. The successor step is part (b), and the limit step is part (c). ThusBy the well-ordering theorem, any infinite cardinal in the question may be represented by an infinite initial ordinal $\kappa$. The corrected recursion supplies a bijection $g_{\kappa }:\kappa \times \kappa \to {\gamma }_{\kappa }$, and the just-proved equality gives $|{\gamma }_{\kappa }|=\kappa$. ThereforeThe proof used only finite-copy interleaving before reaching this conclusion; using the square equality itself to estimate the successor or limit stages would have been circular.

Let $\mathcal{O}$ be the set of strict total orders on $\kappa$. Each is a subset of $\kappa \times \kappa$, so the square of an infinite cardinal givesFor the lower bound, use the set $\kappa \times \{0,1\}$ and order the two-element blocks by their first coordinates, using the well-order of $\kappa$. For every $A\subseteq \kappa$, put $(\alpha ,0)$ before $(\alpha ,1)$ exactly when $\alpha \in A$, reversing them otherwise. This defines a strict total order for each $A$, and different subsets give different orders. Transport these orders to $\kappa$ along a fixed bijection $\kappa \times \{0,1\}\cong \kappa$. Thus $2^{\kappa }\le |\mathcal{O}|$, and the Cantor-Schröder-Bernstein theorem givesIf using the customary axiom of choice development of infinite cardinal arithmetic, its use here is precisely to supply $\kappa \times \kappa \cong \kappa$ and $\kappa \times 2\cong \kappa$. The ordering construction makes no further choices. It proves the cardinality of the family of strict total orders. For $\kappa$ itself an initial ordinal, these particular product identities can also be proved in ZF by well-ordering pairs according to their maximum coordinate, so full axiom of choice is stronger than this instance intrinsically requires.

Use ZFC and infinite input sets, the usual scope of the stated claim. For a finite set of size $n$, its Hartogs number is $n+1$, which is a finite successor cardinal rather than an aleph. Without the axiom of choice, one cannot silently identify every infinite input with an aleph, and the asserted conclusion needs those hypotheses.

The Hartogs number $h(X)$ is the least ordinal that does not inject into $X$. It is an initial ordinal: if it were equinumerous with a smaller ordinal $\alpha <h(X)$, composing that bijection with an injection $\alpha \to X$ would contradict its definition. With choice, well-order an infinite $X$ and put $|X|=\kappa ={\aleph }_{\eta }$. Every ordinal below ${\kappa }^{+}$ has cardinal at most $\kappa$ and injects into $X$, whereas ${\kappa }^{+}$ does not. Hence the Hartogs numbers under choice satisfyTo prove regularity, suppose $\mathrm{cf}({\kappa }^{+})=\mu <{\kappa }^{+}$. Since ${\kappa }^{+}$ is a successor cardinal, $\mu \le \kappa$. Choose a cofinal sequence $⟨{\alpha }_i:i<\mu ⟩$ below ${\kappa }^{+}$. Each ${\alpha }_i$ has cardinal at most $\kappa$, and choice givesBut cofinality makes this union all of ${\kappa }^{+}$, a contradiction. Therefore $\mathrm{cf}({\kappa }^{+})={\kappa }^{+}$, and every infinite-input Hartogs value is a regular initial successor aleph. Conversely every successor aleph occurs by taking $X$ to be its predecessor cardinal.

Call a set function $f$ with ordinal domain $\gamma$ good if $f(\xi )=G(\xi ,\mathrm{ran}(f{|}_{\xi }))$ for every $\xi <\gamma$. Any two good functions agree on their common domain: otherwise their first disagreement has identical earlier ranges and hence identical values under $G$. This is transfinite induction, not an assumption of the desired recursion.

Good functions exist with every ordinal domain. At a successor stage extend the unique previous function by its prescribed value under $G$. At a limit stage, Axiom schema of replacement collects the unique good functions on all smaller domains into a set, and their compatible union is a good function on the limit domain. Each earlier range is a set, so $G$ is applied only to sets. Transfinite induction now establishes existence at all stages. Define $F(\alpha )$ to be the value at $\alpha$ of the unique good function on $\alpha +1$. This is a definable class function because goodness and the uniqueness assertion are formulas in the defining formula for $G$. Compatibility gives

An initial ordinal is an ordinal not bijective with any smaller ordinal. It is the canonical ordinal representative of a well-orderable cardinal, so cardinal arithmetic can be defined by taking the initial ordinal equinumerous with a disjoint union, Cartesian product or function set. In the usual setting with the axiom of choice, every cardinal has such a representative. Hartogs theorem says that for every set $A$ there is an ordinal $h(A)$ which does not inject into $A$, and there is a least such ordinal. For an initial ordinal $\kappa$ it is the next larger initial ordinal: every smaller ordinal injects into $\kappa$, and if $h(\kappa )$ were equinumerous with a smaller ordinal it too would inject into $\kappa$.

Use the recursion just proved to set ${\omega }_0=\omega$, ${\omega }_{\beta +1}=h({\omega }_{\beta })$ and ${\omega }_{\lambda }={\sup }_{\beta <\lambda }{\omega }_{\beta }$ for nonzero limit $\lambda$. These instructions use the earlier value set alone: at a successor it has a maximum, and at a limit its supremum is taken. They are therefore implemented by an appropriate definable $G$. The limit supremum is initial: if it were bijective with $\gamma$ below it, choose an earlier ${\omega }_{\beta }>\gamma$; then ${\omega }_{\beta }$ would inject into $\gamma$, contradicting initiality. The sequence is strictly increasing and continuous. There are no omitted infinite initial ordinals, since each successor chooses the least next one and each limit is the supremum; more formally, a least omitted initial ordinal cannot lie between successive terms, and the least term above it cannot be a limit term. Terms eventually exceed any prescribed ordinal, since a strictly increasing ordinal sequence satisfies ${\omega }_{\beta }\ge \beta$.

There is a fixed point of a normal ordinal function. Explicitly let ${\alpha }_0=0$, ${\alpha }_{n+1}={\omega }_{{\alpha }_n}$ and $\alpha ={\sup }_{n<\omega }{\alpha }_n$. The sequence is strictly increasing, by induction from $0<{\omega }_0$ and strict increase of the enumeration. It is cofinal in the limit $\alpha$, so continuity gives

A cardinal number is identified with an initial ordinal, namely an ordinal not in bijection with any smaller ordinal. An inaccessible cardinal, in the strong sense used here, is an uncountable regular cardinal that is also a strong limit cardinal. ThusA worldly cardinal is a cardinal number whose level of the Von Neumann hierarchy satisfies all of ZFC:Worldliness is this model-theoretic condition; regularity is not part of its definition. The original PDF asks for these two notions; the extra comma in the local TeX makes “cardinal” look like a separate requested item.

An aleph number is an infinite initial ordinal. More explicitly,for a limit ordinal $\lambda$. By the well-ordering theorem, every set is equipotent to an ordinal and hence to a unique initial ordinal. If the set is infinite, that initial ordinal occurs in the aleph enumeration. Thus every infinite set has cardinality ${\aleph }_{\alpha }$ for a unique ordinal $\alpha$.

We next prove the square of an infinite cardinal. Suppose otherwise and let $\kappa$ be the least infinite cardinal for which ${\kappa }^2>\kappa$. Well-order $\kappa \times \kappa$ by increasingbreaking ties lexicographically. The predecessors of $(\alpha ,\beta )$ lie inside $\gamma \times \gamma$ for some $\gamma <\kappa$. If $\mu =|\gamma |$, then $\mu <\kappa$; by minimality, ${\mu }^2=\mu$ when $\mu$ is infinite, while the finite case is immediate. Every proper initial segment therefore has cardinality less than $\kappa$.

Recursively assign to each pair the least ordinal below $\kappa$ not already assigned to one of its predecessors. Such an ordinal always exists by the preceding bound, so this constructs an injection $\kappa \times \kappa \to \kappa$. The map $\alpha \mapsto (\alpha ,0)$ gives the reverse injection, and the Cantor-Schröder-Bernstein theorem yields

For infinite $X_1,\dots ,X_n$, finitely many applications of the cardinal comparability principle let us choose $X_i$ of largest cardinality $\kappa$. Thenwhere the final equality follows from infinite cardinal arithmetic. Consequently

For a countable family of pairwise different infinite cardinalities, the answer is yes. Regard initial ordinals as sets and takeThe cardinalities are pairwise distinct, but every $X_{n+2}$ is a subset of $X_1$. Hencewhich is the countable family of distinct infinite cardinalities with a largest member construction.

Choose sets $K,L,M$ of cardinalities $\kappa ,\lambda ,\mu$. Their cardinal arithmetic operations arewhere $K^L$ is the set of functions $L\to K$. The relation $\kappa \le \lambda$ means that there is an injective function $K\to L$.

The currying law for cardinal exponentiation follows from the explicit bijectionand provesMoreover, $2^{\kappa }$ is the cardinality of the power set of a set of size $\kappa$, so Cantor theorem gives

For completeness, identify each cardinal with its initial ordinal. Suppose that some infinite $\kappa$ violates ${\kappa }^2=\kappa$, and choose the least such cardinal. Well-order the pairs $(\alpha ,\beta )\in {\kappa }^2$ first by $\max \{\alpha ,\beta \}$ and then lexicographically. Every proper initial segment is contained in ${\gamma }^2$ together with finitely many boundary pieces for some $\gamma <\kappa$, and has cardinality below $\kappa$ by minimality. The resulting well-order therefore has cardinality at most $\kappa$. The reverse inequality is immediate from $\alpha \mapsto (\alpha ,0)$, contradicting the choice of $\kappa$. Thus the square of an infinite cardinal satisfies ${\kappa }^2=\kappa$.

If $\nu =\max \{\kappa ,\lambda \}$, monotonicity now givesHence the sum and product of two infinite cardinals obey

Assertion (i) can be false. For any infinite $\lambda$, take $\kappa =(2^{\lambda }{)}^{+}$. Then ${\kappa }^{\lambda }\ge \kappa >2^{\lambda }$, so

Assume the axiom of choice. By the well-ordering theorem, every set is bijective with an ordinal, and hence with an initial ordinal. Any two ordinals are comparable, so for any sets $K,L$ either $K$ injects into $L$ or $L$ injects into $K$. Transitivity is immediate, and antisymmetry on cardinalities follows from the Cantor-Schröder-Bernstein theorem. Thus cardinal comparison is a total order.

Conversely, assume the cardinal comparability principle. Given any set $X$, let $h(X)$ be its Hartogs ordinal. By Hartogs theorem, there is no injection $h(X)\to X$. Comparability therefore supplies an injection $X\to h(X)$. Pulling the ordinal order back to $X$ gives a well-order of $X$. Hence every set can be well-ordered, and the well-ordering theorem implies the axiom of choice.

Under the axiom of choice, identify every infinite cardinal $\kappa$ with its initial ordinal. We prove ${\kappa }^2=\kappa$ by transfinite induction on infinite cardinals. The countable case follows from the usual diagonal enumeration of $\mathbb{N}\times \mathbb{N}$.

For the induction step, well-order the Cartesian product $\kappa \times \kappa$ by first comparingand then using lexicographic order among pairs with the same maximum. The predecessors of $(\alpha ,\beta )$ lie in $(\eta +1)\times (\eta +1)$, where $\eta =\max \{\alpha ,\beta \}<\kappa$. Put $\mu =|\eta +1|<\kappa$. If $\mu$ is infinite, the induction hypothesis makes this predecessor set have cardinal at most ${\mu }^2=\mu <\kappa$; if $\mu$ is finite, the same conclusion is immediate.

Let $\theta$ be the order type of this well-order. Every proper initial segment of $\theta$ therefore has cardinal less than $\kappa$. Hence $\theta <{\kappa }^{+}$, since otherwise its initial segment of order type $\kappa$ would have cardinal $\kappa$. Thus $|\kappa \times \kappa |=|\theta |\le \kappa$. The map $\alpha \mapsto (\alpha ,0)$ gives the reverse injection, and the Cantor-Schröder-Bernstein theorem yields