Draft lesson.

Well-orders, cardinal bounds and regular successors

Written by GPT-6.1 Sol (OpenAI), October 2026. Original exposition and exercises: CC0. Linked proofs retain their stated terms.

A well-order gives each element a precise position. A cardinal records how many positions are needed to list a set, while forgetting the particular order of that list. We will construct this distinction from Choice, prove that an infinite set has the same cardinality as its square, and use that equality to bound unions and function sets. The proofs keep track of the actual bijections and the universe in which their encodings live.

Read Universes and small categories, Sections 1–4 first. We use its complete proofs of universe closure, transport along bijections, Cantor's diagonal argument and the obstruction to a small family representing every small set. Those proofs are imported here. The prerequisites for the new arguments are elementary sets, functions, natural-number induction and partially ordered sets.

1. Foundations and positions in a well-order

Our ambient set theory has the Zermelo–Fraenkel axioms: Extensionality, Empty Set, Pairing, Union, Power Set, Infinity, Separation, Replacement and Foundation. Choice means that every set-indexed family of nonempty sets has a function selecting an element of each member. Only set-indexed choices will be used. We also assume the enlargement axiom stated in Universes and small categories, Section 1.

Fix a Grothendieck universe \(\mathcal U\): it is transitive, contains \(\mathbb N\), and is closed under singletons, power sets and unions of families of its members indexed by a member. A universe member is a \(\mathcal U\)-set. A set bijective to a member is \(\mathcal U\)-small. The member and smallness bounds for products, function sets, quotients and indexed unions are the proved statements of Sections 2–3 of that prerequisite. Choose a larger universe \(\mathcal V\) containing \(\mathcal U\) when collecting all \(\mathcal U\)-cardinal types.

For a partially ordered set \((I,\leq)\), write \(x<y\) when \(x\leq y\) and \(x\ne y\). It is well ordered if every nonempty subset has a least element. Applying this property to \(\{x,y\}\) proves that any two elements are comparable. Thus the order is total. The empty set is well ordered.

If \(x\) is not the largest element, its strict upper tail is nonempty. Its least element is the immediate successor \(x+1\): there is no element strictly between \(x\) and \(x+1\). This notation denotes the successor in the particular order, rather than arithmetic on arbitrary labels.

Proposition 1.1. Exactly one of the following holds for an element \(x\) of a well-ordered set:

1. \(x\) is the least element;
2. \(x\) has an immediate predecessor;
3. the strict lower set is nonempty, has no greatest element, and has supremum \(x\).

In the second case the predecessor is unique and is the supremum of that strict lower set.

Proof. Put \(L_x=\{y\in I:y<x\}\). If it is empty, \(x\) is least. If it has a greatest element \(p\), no element lies strictly between \(p\) and \(x\), so \(p\) is an immediate predecessor. Every immediate predecessor must be greatest in \(L_x\), proving uniqueness. A greatest element of a subset is its supremum.

Suppose instead that \(L_x\) is nonempty with no greatest element. The element \(x\) is an upper bound. An element \(z<x\) cannot be an upper bound: it belongs to \(L_x\), and some \(y\in L_x\) satisfies \(z<y\). Hence no smaller upper bound exists and \(x=\sup L_x\). The three cases are disjoint and exhaustive. \(\square\)

2. Set recursion and a bound on possible order types

We need a recursion principle before deriving well-ordering from Choice. Its proof uses the set axioms and uniqueness, rather than choices of orders on arbitrary sets.

Lemma 2.1 (recursion on a given well-order). Let \(I\) be a well-ordered set. Suppose a rule, given by a formula with fixed set parameters, assigns a unique set \(F(x,p)\) to each \(x\in I\) and each function \(p\) on \(L_x\). There is a unique function \(f\) on \(I\) satisfying

The rule may use fixed ambient set parameters.

Proof. Two solutions on initial segments agree on their common domain. Otherwise the least point of disagreement has identical previous values, and the rule gives identical values there. This also proves uniqueness of any partial solution.

Call a point \(x\) a failure if there is no solution on \(L_x\cup\{x\}\). The failures form a subset of \(I\), by Separation. If one existed, choose its least member \(x\). For every \(y<x\) there is a unique solution \(p_y\) on \(L_y\cup\{y\}\). Replacement collects this uniquely specified family as a set. Its functions agree wherever their domains meet; their union is therefore a function \(p\) on \(L_x\) and satisfies the rule there. Appending the value \(F(x,p)\) gives a solution through \(x\), a contradiction. This includes a least point, for which \(p\) is empty.

There are consequently no failures. Replacement collects the unique partial solution through each \(x\in I\); their union is the required function on \(I\). If \(I\) is empty, the empty function is that solution. \(\square\)

An ordinal is a transitive set well ordered by membership. We use \(0=\varnothing\), the successor \(\alpha+1=\alpha\cup\{\alpha\}\), and the ordinal \(\omega\) of the natural numbers. The finite ordinals are its elements. Foundation implies \(\alpha\notin\alpha\).

Here are the order facts about ordinals needed below. If \(\gamma\in\alpha\), transitivity gives \(\gamma\subseteq\alpha\). Transitivity of the membership order on \(\alpha\) makes \(\gamma\) transitive, and restriction of that well-order well orders \(\gamma\). Thus \(\gamma\) is an ordinal; its elements are exactly the earlier members of \(\alpha\). Adding the point \(\alpha\) above all its elements likewise makes \(\alpha+1\) an ordinal. A proper downward-closed subset of an ordinal is its least omitted member: all earlier elements are included, and downward closure excludes all later ones. For ordinals \(\alpha,\beta\), their intersection is downward closed in both. If it were proper in both, it would be an element of both, hence an element of itself. Therefore one ordinal is a subset of the other; a proper inclusion makes the smaller one an element of the larger.

The union of a set of ordinals is an ordinal. It is transitive, and membership is total by the preceding comparison. To find the least element of a nonempty subset, take one element \(\gamma\) and find the least element of the subset's intersection with \(\gamma+1\). Every element outside \(\gamma+1\) is larger. This also shows that any set of ordinals is well ordered by their usual comparison. These arguments establish the comparison and union facts directly from the definition.

Lemma 2.2 (the ordinal of a well-order). Every well-ordered set \((I,<)\) is uniquely order-isomorphic to an ordinal. At a point \(x\), its position is the ordinal of its strict lower set.

Proof. Apply Lemma 2.1 to the rule

Induction in the given well-order proves that each \(o(x)\) is an ordinal. Indeed, the earlier values are ordinals; for \(y<z<x\) the definition gives \(o(y)\in o(z)\), so they are distinct. Their set is transitive, because an element of \(o(y)\) is some \(o(t)\) with \(t<y<x\). Its membership order is exactly the well-order on \(L_x\), so it is an ordinal. This is the induction step, including an empty lower set.

The set \(\theta=\{o(x):x\in I\}\), formed by Replacement, is likewise transitive and well ordered by membership. The function \(o:I\to\theta\) is an order-isomorphism. For any other isomorphism from \(I\) to an ordinal, the image of \(x\) must be the set of images of its predecessors. Uniqueness in Lemma 2.1 forces the same function and the same ordinal. The empty well-order has ordinal \(0\). \(\square\)

Lemma 2.3 (Hartogs' bound). For every set \(A\), there is an ordinal \(h(A)\) with no injection \(h(A)\to A\).

Proof. The pairs \((B,R)\) with \(B\subseteq A\) and \(R\) a strict well-order on \(B\) form a set: it is a subset of

By Lemma 2.2 and Replacement, their order types form a set \(H\) of ordinals. It contains \(0\). If \(\alpha\in H\) and \(\beta<\alpha\), restricting an order representing \(\alpha\) to its first \(\beta\) elements represents \(\beta\). Thus \(H\) is downward closed among ordinals and is itself an ordinal. Set \(h(A)=H\).

An injection \(h(A)\to A\) would transport the membership order of \(h(A)\) to a well-order on its image, a subset of \(A\). Its order type would be \(h(A)\), so \(h(A)\in H=h(A)\), contrary to Foundation. \(\square\)

All choices of orders in this proof ranged over an existing set of relations. The construction of \(h(A)\) uses only ZF; it is therefore available before well-ordering is deduced from Choice.

3. Well-ordering from Choice and universe bounds

Theorem 3.1. Under Choice, every set admits a well-order.

Proof. Choice applied to the family of all nonempty subsets of \(A\) gives a function \(c\) with \(c(B)\in B\). Use the marker \(A\), which is not an element of \(A\) by Foundation. Recursion on \(h(A)\) defines \(e(\alpha)\) by

Lemma 2.1 applies: each previous assignment determines these sets and the next value uniquely. If every \(R_\alpha\) were nonempty, all values would be distinct members of \(A\). This would give an injection \(h(A)\to A\), contradicting Lemma 2.3. Let \(\beta<h(A)\) be the least stage with \(R_\beta=\varnothing\). Before \(\beta\), the values are distinct members of \(A\); their range is all of \(A\). Consequently \(e|_\beta:\beta\to A\) is a bijection. Transporting the ordinal order along it well orders \(A\). For \(A=\varnothing\), \(\beta=0\) and the same argument gives the empty order. \(\square\)

Proposition 3.2. If the underlying set of a well-order belongs to \(\mathcal U\), its order type belongs to \(\mathcal U\). Every \(\mathcal U\)-small well-order has the same conclusion for its order type.

Proof. Suppose \(I\in\mathcal U\). In the recursion (2.2), induction proves \(o(x)\in\mathcal U\). Its predecessor set \(L_x\) is a subset of \(I\), hence a universe member. If each earlier \(o(y)\) is a member, then so is \(\{o(y)\}\); the universe's indexed-union axiom gives

The same axiom with index \(I\) gives \(\theta=\bigcup_{x\in I}\{o(x)\}\in\mathcal U\). This use of indexed unions permits ambient families; their function graphs need not have been members beforehand. The closure statement and that convention are proved and stated in the prerequisite.

If \(b:I\to I_0\) is a bijection with \(I_0\in\mathcal U\), transport the relation by \(u<_0v\) exactly when \(b^{-1}(u)<b^{-1}(v)\). It is a relation on \(I_0\) and belongs to \(\mathcal U\) by the imported subset and product bounds. The two well-orders have the same order type, by Lemma 2.2. Apply the member case. \(\square\)

Corollary 3.3. For \(A\in\mathcal U\), the Hartogs ordinal \(h(A)\) and the choice and recursion functions used in Theorem 3.1 have encodings in \(\mathcal U\).

Proof. The set \(W\) of ordered-subset pairs used in (2.3) is a universe member, by the imported power-set, product and subset bounds. For \(w=(B,R)\in W\), Proposition 3.2 gives its order type \(\theta_w\in\mathcal U\). The successor \(\theta_w+1\) is a member by singleton and union closure. Downward closure of the represented order types gives

Indeed, a term \(\theta_w+1\) contains that represented type and all its smaller types, and every represented type occurs in such a term. The indexed-union axiom therefore applies with index \(W\). A choice function on nonempty subsets of \(A\) has graph in \(\mathcal P(A)\times A\). The recursion function has graph in \(h(A)\times(A\cup\{A\})\); both factors of that product are universe members. Imported subset closure gives the two graph bounds.

For a small set with other labels, transporting ordered subsets along a representative bijection preserves their order types, so it preserves \(h(A)\). The original choice and recursion graphs are small by the imported transport and product bounds; their member encodings are the ones just constructed. \(\square\)

For example, \(\omega+2\) has a least point \(0\), the successor points \(1,2,\ldots,\omega+1\), and the point \(\omega\) whose nonempty strict lower set has no greatest element. Its order type differs from \(\omega\), but the bijection

shows that the two underlying sets have the same cardinality. Its inverse sends \(0,1\) to the two displayed upper points and \(m\geq2\) to \(m-2\).

4. Cardinal representatives and comparison by injections

Two sets have the same cardinality if a bijection exists between them. A \(\mathcal U\)-cardinal is such an equicardinality type of \(\mathcal U\)-small sets. We encode all these types using the quotient

This quotient is formed in \(\mathcal V\), where \(\mathcal U\) is a member. Every small set has a representative in \(\mathcal U\), so this encoding includes every small cardinal type. It avoids treating the collection of all arbitrary relabelings of one set as a set. A different labeling of a small set leaves its type unchanged.

An ordinal \(\kappa\) is initial if no smaller ordinal is bijective to it. The initial ordinals will be our explicit cardinal representatives.

Proposition 4.1. Every set \(A\) is bijective to a unique initial ordinal, denoted \(|A|\). If \(A\) is \(\mathcal U\)-small, then \(|A|\in\mathcal U\).

Proof. Theorem 3.1 and Lemma 2.2 give an ordinal \(\alpha\) bijective to \(A\). Among the ordinals \(\beta\leq\alpha\) bijective to \(A\), choose the least, \(\kappa\). This is a least element of a nonempty subset of \(\alpha+1\). A bijection between \(\kappa\) and a smaller ordinal would make that smaller ordinal bijective to \(A\), a contradiction. Thus \(\kappa\) is initial.

If two initial ordinals are bijective, compare them as ordinals. A strict inequality contradicts initiality of the larger one, so they are equal. This proves uniqueness independent of the chosen order on \(A\). For a small set, first take a universe-member representative and well order it. Proposition 3.2 puts its order type \(\alpha\) in \(\mathcal U\). Since \(\kappa\subseteq\alpha\), imported subset closure puts \(\kappa\) there too. \(\square\)

The correspondence \([A]\mapsto|A|\) identifies (4.1) with

Its inverse sends \(\kappa\) to its class in (4.1). Since any set of ordinals is well ordered, the \(\mathcal U\)-cardinals are well ordered through this identification. Their entire collection is a set in \(\mathcal V\). It is not \(\mathcal U\)-small: if it were, choosing a universe-member representative for each class would give a small family representing every object of \(\mathsf{Set}_{\mathcal U}\), ruled out by the complete argument in Universes and small categories, Example 4.2. This is precisely the already proved representative-family obstruction.

For finite sets the cardinal representatives are the finite ordinals. The finite pigeonhole fact follows by induction, starting with the impossibility of \(1\to0\). For \(n\geq1\), an injection \(n+1\to n\) would, after deleting its last domain point and its image and relabeling the remaining codomain, give an injection \(n\to n-1\), contradicting the preceding step. An injection \(\omega\to n\) would restrict to the forbidden injection \(n+1\to n\). Since every ordinal below \(\omega\) is finite, the natural-number set has initial representative \(\omega\). We write \(\aleph_0=\omega\). An infinite cardinal is an initial ordinal \(\kappa\geq\omega\).

Theorem 4.2 (Cantor–Bernstein). Injections \(f:A\to B\) and \(g:B\to A\) give a bijection \(A\to B\).

Proof. Define

The graph of the inverse of \(g\) on its image is a function because \(g\) is injective. Since \(A_0\subseteq D\), every \(a\notin D\) belongs to \(g(B)\). Set

Each branch is injective. Their images are disjoint: if \(b=f(a)\) with \(a\in D\), then \(g(b)=g(f(a))\in D\), so \(b\) cannot be the second-branch image of a point outside \(D\).

For surjectivity, take \(b\in B\). If \(b\in f(D)\), the first branch reaches it. Otherwise \(g(b)\notin D\). Indeed, \(D=A_0\cup g(f(D))\); the point \(g(b)\) is outside \(A_0\), and membership in \(g(f(D))\) would imply \(b\in f(D)\) by injectivity of \(g\). The second branch therefore sends \(g(b)\) to \(b\). The inverse is explicitly

The definitions include empty sets. If \(A,B\in\mathcal U\), all \(A_n,D\) are subsets of \(A\), and both function graphs are subsets of products of universe members. They belong to \(\mathcal U\) by the imported closure results. For small sets with other labels, transport the maps to universe-member representatives, apply this construction there and conjugate the resulting bijection back. \(\square\)

Corollary 4.3. For any sets \(A,B\),

Proof. Choose bijections from \(A,B\) to their initial ordinals \(\kappa,\lambda\). If \(\kappa\leq\lambda\), their inclusion is injective and can be transported back. Conversely, an injection gives \(\kappa\to\lambda\). If \(\lambda<\kappa\), inclusion gives \(\lambda\to\kappa\); Theorem 4.2 would make \(\kappa\) bijective to the smaller ordinal \(\lambda\), contradicting initiality. Therefore \(\kappa\leq\lambda\). \(\square\)

5. Cardinal operations and the infinite square

For cardinals represented by sets \(A,B\), define

We also write \(\operatorname{Map}(A,B)=B^A\) for the set of functions. In a cardinal equality, an exponent denotes the initial cardinal of that function set. In actual arrows involving cardinal representatives, \(\operatorname{Map}\) will specify the function-set domain explicitly.

The exponent is the domain cardinal. The proved transport maps in Universes and small categories, Proposition 3.1 make these definitions independent of representatives: product maps use the two coordinate bijections, and a function is sent to \(c\circ f\circ b^{-1}\) for bijections \(b:A\to A_0\), \(c:B\to B_0\). Their inverses and all universe bounds are provided there. For \(\mathcal U\)-small inputs, the imported closure results and Proposition 4.1 give universe-member initial ordinals for these products and powers. The empty-domain function set is a singleton, and no function has a nonempty domain and an empty codomain.

The characteristic-function bijection

has inverse \(u\mapsto u^{-1}(\{1\})\). The singleton map injects \(A\) into \(\mathcal P(A)\). The complete Cantor argument in Universes and small categories, Lemma 1.1 excludes an injection in the reverse direction. By Corollary 4.3 this gives

We retain that proved diagonal argument and supply the comparison with initial ordinals here.

The square theorem needs a preliminary fact that does not use infinite cardinal multiplication. If \(\alpha\geq\omega\), the following is a bijection \(\alpha+1\to\alpha\): send the new upper point \(\alpha\) to \(0\), send each \(n<\omega\) to \(n+1\), and fix every \(\xi\) with \(\omega\leq\xi<\alpha\). The inverse sends \(0\) to \(\alpha\), a positive natural number \(n+1\) to \(n\), and fixes the remaining points. An infinite initial ordinal consequently cannot be a successor ordinal. Thus every infinite cardinal \(\kappa\) is a limit ordinal, and

Theorem 5.1. For every infinite cardinal \(\kappa\), there is a bijection \(\kappa\times\kappa\to\kappa\). In particular \(\kappa\cdot\kappa=\kappa\).

Proof. We use induction on the infinite initial ordinals. For a fixed cardinal under consideration, the cardinals up to it form a set, so this is ordinary well-ordered induction on a set. At the step \(\kappa\), assume the theorem for each infinite cardinal strictly below \(\kappa\).

Order \(\kappa\times\kappa\) by comparing the triples

lexicographically. This is a well-order: in a nonempty subset first choose the least maximum coordinate, then the least first coordinate among those pairs, then the least second coordinate. These three least-element operations give its least pair.

Consider a pair with maximum coordinate \(\rho<\kappa\). All its predecessors lie in \((\rho+1)\times(\rho+1)\). Put \(\mu=|\rho+1|\). Equation (5.4) and initiality of \(\kappa\) give \(\mu<\kappa\). If \(\mu\) is finite, this product is finite, hence has cardinal below \(\kappa\). If \(\mu\) is infinite, the induction hypothesis gives its cardinal as \(\mu\), again below \(\kappa\). The product transport maps of (5.1) apply to the bijection \(\rho+1\to\mu\). Thus every strict initial segment of our pair order has cardinal below \(\kappa\).

Let \(\theta\) be this well-order's ordinal, supplied by Lemma 2.2. If \(\theta>\kappa\), its point at position \(\kappa\) would have a strict initial segment bijective to \(\kappa\). This contradicts the bound just proved. Hence \(\theta\leq\kappa\). The order-isomorphism gives an injection \(\kappa\times\kappa\to\kappa\); the diagonal \(\alpha\mapsto(\alpha,\alpha)\) gives the reverse injection. Theorem 4.2 proves the required bijection. In fact \(\theta\) must equal \(\kappa\): if it were smaller, the diagonal followed by the order-isomorphism would inject \(\kappa\) into a smaller ordinal, contradicting Corollary 4.3 and initiality. Therefore the position map itself is a bijection

For \(\kappa=\omega\), every \(\rho<\kappa\) is finite, so the finite branch of the argument supplies the first induction step. No infinite square was assumed at that step. \(\square\)

The relation in (5.5) is a subset of \((\kappa\times\kappa)\times(\kappa\times\kappa)\). For \(\kappa\in\mathcal U\), imported universe closure puts this relation and its underlying set in \(\mathcal U\). Proposition 3.2 puts its order type there, and the graph of \(r_\kappa\) is a subset of \((\kappa\times\kappa)\times\kappa\), hence a member. For a small set \(A\) with bijection \(b:A\to\kappa\), an actual square bijection is

Its inverse applies \(r_\kappa^{-1}\) and then \(b^{-1}\) to the two coordinates. With external labels these graphs are small, and membership is asserted for their encodings after transport.

Corollary 5.2. If \(\kappa\) is infinite and \(1\leq\mu\leq\kappa\), then \(\kappa\cdot\mu=\kappa\). If two cardinals are infinite, their product is their maximum.

Proof. Inclusion embeds \(\kappa\times\mu\) into \(\kappa\times\kappa\), whose cardinal is \(\kappa\). The map \(\alpha\mapsto(\alpha,0)\) embeds \(\kappa\) into \(\kappa\times\mu\), since \(\mu\ne0\). Apply Theorem 4.2. For two infinite cardinals, take \(\kappa\) to be their maximum and use this argument, interchanging the coordinates if needed. If a factor is zero, the product is zero. \(\square\)

Corollary 5.3 (a union bound). Let \(\kappa\) be infinite. If \(|I|\leq\kappa\) and \(|B_i|\leq\kappa\) for every \(i\in I\), then the tagged union \(\coprod_iB_i\) and the ordinary union \(\bigcup_iB_i\) have cardinal at most \(\kappa\).

Proof. Choose an injection \(e:I\to\kappa\). By set-indexed Choice, choose an injection \(b_i:B_i\to\kappa\) for each \(i\); an empty \(B_i\) has its unique empty map. The map

is injective: injectivity of \(r_\kappa\), then of \(e\) and \(b_i\), recovers both labels. This proves the tagged bound. For a point in the ordinary union choose the least index containing it after well-ordering \(I\); this gives an injection of that union into the tagged union. For empty \(I\), both unions are empty. If the sets and index are small, their smallness and the exact reindexing maps are already supplied by the imported Proposition 3.1; (5.8) supplies the sharper cardinal bound. \(\square\)

6. Regular cardinals and successors

An infinite cardinal \(\lambda\) is regular if, whenever a set \(I\) and sets \(B_i\) satisfy \(|I|<\lambda\) and \(|B_i|<\lambda\) for every \(i\),

For \(\lambda\in\mathcal U\), every test set in this definition is automatically \(\mathcal U\)-small: Corollary 4.3 injects it into \(\lambda\), and it is bijective to its image, a universe member by subset closure. Thus this is exactly the fixed-universe condition using small indices and small summands. The union is tagged, so repeated elements in different summands remain distinct. Empty summands and an empty index are included. Ordinary unions satisfy the same bound, by the injection in Corollary 5.3. For \(\lambda=\aleph_0\), (6.1) says that a finite union of finite sets is finite, which follows by finite induction. Thus \(\aleph_0\) is regular.

Proposition 6.1. Every cardinal \(\kappa\) has a least larger cardinal \(\kappa^+\). If \(\kappa\in\mathcal U\), then \(\kappa^+\in\mathcal U\).

Proof. Equation (5.3) supplies a larger cardinal \(2^\kappa\). The cardinals in the ordinal interval \((\kappa,2^\kappa]\) form a nonempty set with a least member \(\lambda\). Any cardinal strictly between \(\kappa\) and \(\lambda\) would also be in that interval, so none exists. This makes \(\lambda\) the least larger cardinal, \(\kappa^+\). For a universe-member \(\kappa\), the power set and its cardinal representative are members, by the imports and Proposition 4.1. As \(\lambda\leq2^\kappa\), it is a subset of that ordinal and hence belongs to \(\mathcal U\). \(\square\)

Theorem 6.2. The successor \(\kappa^+\) of every infinite cardinal \(\kappa\) is regular.

Proof. Suppose \(|I|<\kappa^+\) and \(|B_i|<\kappa^+\) for all \(i\). By the definition of the next cardinal, all these cardinals are at most \(\kappa\). Corollary 5.3 gives

This is (6.1), including the empty cases. The maps establishing the inequality are the single injections (5.8), chosen for the whole indexed family. Their construction uses Choice and the already proved square theorem. \(\square\)

For instance \(\aleph_1=\aleph_0^+\) is regular: a countable family of countable sets has countable tagged union. The word infinite alone does not imply regularity; Exercise 3 constructs an explicit failure. In the statements here, \(\kappa,\mu,\lambda\) called infinite cardinals are unrestricted infinite cardinal representatives. When \(\pi\) denotes a cardinal parameter, it is also assumed infinite; regularity must be stated separately.

7. A larger cardinal unchanged by a prescribed exponent

For sets \(A,B,C\), the currying bijection is

Its inverse sends \(G\) to the function \(b\mapsto(a\mapsto G(a,b))\). Substitution in either direction recovers the original function. For universe-member inputs, the function sets and these graphs are members by the imported closure results. For small inputs, the imported transport maps give the same bijection on representatives. Hence cardinal exponentiation satisfies

Theorem 7.1. For every infinite cardinal \(\kappa\), there is a cardinal \(\theta>\kappa\) such that \(\theta^\kappa=\theta\). One can take \(\theta=2^\kappa\).

Proof. Strict inequality is (5.3). Currying and Theorem 5.1 give

The equality is implemented by actual maps. For \(F:\kappa\to\{0,1\}^\kappa\), define \(\Phi(F):\kappa\to\{0,1\}\) by

Its inverse sends \(u:\kappa\to\{0,1\}\) to \(\beta\mapsto(\alpha\mapsto u(r_\kappa(\alpha,\beta)))\). The two composite identities follow from those of \(r_\kappa\) and its inverse. Finally choose a bijection \(q:\theta\to\{0,1\}^\kappa\). The actual bijection using the initial-ordinal representatives is

with inverse obtained from \(q\), \(\Phi^{-1}\) and pointwise \(q^{-1}\). If \(\kappa\in\mathcal U\), then \(\theta\), all function sets in these maps, and their graphs on the displayed universe-member representatives belong to \(\mathcal U\). This follows from the imported function-set bounds and Proposition 4.1. \(\square\)

Taking \(\kappa=\aleph_0\) gives \(\theta=2^{\aleph_0}\) and \(\theta^{\aleph_0}=\theta\). The construction does not require identifying \(2^{\aleph_0}\) with any particular successor cardinal. The square theorem concerns two factors: the function set \(\operatorname{Map}(\omega,\omega)\) has cardinal greater than \(\omega\), since it contains \(\{0,1\}^\omega\) and (5.3) applies.

8. Four exercises with complete solutions

1. (introductory) A bijection assembled from two dilations

Exercise. Use the proof of Cantor–Bernstein with \(A=B=\mathbb N\), including \(0\), and injections \(f(n)=3n\), \(g(n)=2n\). Compute \(D\), the resulting bijection and its inverse. Check the values at \(0,1,2,6,12\).

Solution. Here \(A_0\) is the set of positive odd integers and \(g\circ f\) multiplies by \(6\). Consequently

Every positive odd integer lies in \(D\), so the second branch has an integer value. Zero is outside \(D\). The inverse is \(h^{-1}(b)=b/3\) for \(b\in3D\), and \(h^{-1}(b)=2b\) otherwise. In the first case \(b/3\in D\), so substitution gives \(h(b/3)=b\). In the second case \(2b\notin D\): if \(2b=6^k(2m+1)\), parity forces \(k\geq1\) and gives \(b=3\cdot6^{k-1}(2m+1)\in3D\), a contradiction. Thus \(h(2b)=b\). Conversely, \(3n\in3D\) when \(n\in D\). When \(n\notin D\), putting \(b=n/2\) gives \(b\notin3D\), since otherwise \(n\in6D\subseteq D\); the inverse then recovers \(n\). These verify both composites directly. The requested values are

For \(12\), removing one factor of \(6\) leaves the even integer \(2\), so \(12\notin D\). All sets and graphs here belong to \(\mathcal U\) by the imported bounds for subsets of products of natural-number sets.

2. (intermediate) Finite words with a chosen cut

Exercise. Let \(\kappa\) be an infinite cardinal. Let \(W_\kappa\) be the set of all finite words in the alphabet \(\kappa\), including the empty word. Let \(M_\kappa\) consist of pairs \((w,k)\) with a word of length \(n\) and a cut \(0\leq k\leq n\); the cut separates the first \(k\) letters from the remaining letters. Prove that both sets have cardinal \(\kappa\), with explicit injections. Explain why this argument does not bound all infinite words by \(\kappa\).

Solution. Define injections \(p_n:\operatorname{Map}(n,\kappa)\to\kappa\) recursively, interpreting a word as a function from its finite ordinal of positions. For \(n=0\), send the empty word to \(0\). Given \(p_n\), put

Injectivity follows by induction, using the two-coordinate injectivity of \(r_\kappa\); for \(n=1\) it is injectivity of its second coordinate with first coordinate fixed at \(0\). Since \(n,k<\omega\leq\kappa\), the following are injections:

Decoding \(r_\kappa\) first recovers the length and, in the second map, the cut; injectivity of \(p_n\) then recovers the word. Conversely \(a\mapsto(a)\) injects \(\kappa\) into \(W_\kappa\), and \(a\mapsto((a),0)\) injects it into \(M_\kappa\). Cantor–Bernstein gives the two bijections, with its construction (4.3)–(4.5) supplying inverses if desired.

For \(\kappa\in\mathcal U\), these finite-domain function sets, their \(\omega\)-indexed tagged union, and its ordinary union \(W_\kappa\) belong to \(\mathcal U\). Length is recovered from the function's domain. The marked words form a subset of \(W_\kappa\times\omega\), so they belong to \(\mathcal U\) too. The injections are graphs between universe members. An infinite word has no finite length tag \(n\) in (8.4). For \(\kappa=\omega\), binary infinite words inject into \(\operatorname{Map}(\omega,\omega)\), and Cantor's imported theorem gives \(2^{\aleph_0}>\aleph_0\). Thus even this particular infinite-word set exceeds the proposed bound.

3. (advanced) A small cardinal that fails regularity

Exercise. Set \(\kappa_0=\aleph_0\), \(\kappa_{n+1}=2^{\kappa_n}\), and \(\lambda=\bigcup_{n<\omega}\kappa_n\), with cardinals represented by initial ordinals. Show that \(\lambda\) is a universe-member infinite cardinal and that \(\lambda\) is not regular, although \(\lambda^+\) is regular. Give the maps proving the size of the witnessing tagged union.

Solution. The imported function-set bounds, followed by Proposition 4.1, put every \(\kappa_n\) in \(\mathcal U\). Recursion on \(\omega\) defines this uniquely specified family, and the indexed-union axiom puts \(\lambda\) in \(\mathcal U\). Cantor's theorem makes the sequence strictly increasing; its union is an ordinal and each \(\kappa_n<\lambda\).

The ordinal \(\lambda\) is initial. If \(\beta<\lambda\), choose \(n\) with \(\beta<\kappa_n\). Then \(|\beta|<\kappa_n\), by initiality of \(\kappa_n\). A bijection \(\lambda\to\beta\), restricted to the included \(\kappa_n\), would give an injection \(\kappa_n\to\beta\), contradicting Corollary 4.3. Hence no smaller ordinal is bijective to \(\lambda\). It is infinite and in fact \(\aleph_0<\lambda\).

Let \(T=\coprod_{n<\omega}\kappa_n\). An injection \(\lambda\to T\) sends \(\alpha\) to \((n(\alpha),\alpha)\), where \(n(\alpha)\) is the least natural number for which \(\alpha<\kappa_{n(\alpha)}\). The ordinal union guarantees that this number exists, and the second coordinate recovers \(\alpha\). An injection in the other direction is

Here \(n<\omega<\lambda\) and \(\alpha<\kappa_n<\lambda\), and pair injectivity proves the claim. Thus \(|T|=\lambda\). Every summand has cardinal below \(\lambda\) and the index has cardinal \(\aleph_0<\lambda\), but their tagged union does not. This disproves regularity of \(\lambda\). Theorem 6.2 proves regularity of \(\lambda^+\). Both \(T\) and the displayed graphs are encoded by universe members, using the imported union and function bounds.

4. (advanced) The exact range of an exponent collapse

Exercise. Fix an infinite cardinal \(\kappa\) and put \(\theta=2^\kappa\). Prove \(\theta^\mu=\theta\) for every \(1\leq\mu\leq\kappa\), identify the actual function-table bijection, and compute \(\theta^0\). Prove that the same equality fails when the exponent is \(\theta\).

Solution. Corollary 5.2 provides a bijection \(t:\kappa\times\mu\to\kappa\). A table \(F:\mu\to\{0,1\}^\kappa\) corresponds to the single function

Its inverse is \(u\mapsto\bigl(b\mapsto(a\mapsto u(t(a,b)))\bigr)\). The identities of \(t\) verify both composites. For a bijection \(q:\theta\to\{0,1\}^\kappa\), conjugating this table bijection as in (7.5) gives \(\operatorname{Map}(\mu,\theta)\to\theta\), with the conjugated inverse. Equivalently currying yields \(\theta^\mu=2^{\kappa\cdot\mu}=2^\kappa=\theta\).

There is exactly one function from the empty set to \(\theta\), so \(\theta^0=1\). For the exponent \(\theta\), choose two distinct elements of \(\theta\); they exist because \(\theta>\kappa\geq\aleph_0\). The resulting injection \(\{0,1\}\to\theta\) induces, pointwise, an injection \(\{0,1\}^\theta\to\operatorname{Map}(\theta,\theta)\). Therefore

by Corollary 4.3 and Cantor's imported theorem. This establishes the failure without an additional hypothesis on the cardinal between \(\kappa\) and \(\theta\). All sets and maps in the solution are universe members when their initial-ordinal inputs belong to \(\mathcal U\), by the imported operations and Proposition 4.1.

Proof dependencies

The complete imported provider is Universes and small categories: Lemma 1.1 for Cantor's diagonal obstruction, Propositions 2.1 and 3.1 for operations and explicit transport maps, and Example 4.2 for the failure of a small cardinal-representative family. Its independent exposition is CC0. The set recursion, ordinal-type construction, Hartogs bound, well-ordering argument, Cantor–Bernstein bijection, cardinal comparison, infinite-square induction, regular-successor proof, function-table bijections and four solved exercises are proved in this lesson under the stated foundational axioms.