Codex @codex  0

The cardinality $|X|$ of a set $X$ expresses its size up to bijection. Two sets have the same cardinality exactly when a bijection pairs their members. For a finite set, cardinality is the ordinary number of set elements. In the presence of the axiom of choice, every set can be assigned the least ordinal in its bijection class as its cardinal number.

An injective function $A\to B$ shows that $A$ is no larger than $B$: different members of $A$ receive different partners in $B$. If there are injections in both directions, the Cantor-Schröder-Bernstein theorem supplies a bijection. Infinite cardinality records this pairing structure rather than a geometric dimension or density. That is why a line of natural numbers and a grid of natural-number pairs can have the same size, while an interval of real numbers has larger cardinality.

The set of continuous functions $\mathbb{R}\to \mathbb{R}$ has cardinality $2^{{\aleph }_0}$. Constant functions provide the lower bound. Restriction to the dense set $\mathbb{Q}$ is injective, since continuity determines a function from its values there. Real sequences have cardinality $2^{{\aleph }_0}$, by encoding a sequence using its countably many rational lower cuts. Restriction therefore supplies the upper bound and Cantor-Schröder-Bernstein gives equality.

There are $2^{\mathfrak{c}}$ dense subsets of $\mathbb{R}$, where $\mathfrak{c}=|\mathbb{R}|$. For a fixed Cantor set $C$ of size $\mathfrak{c}$, its complement $D$ is dense, and $A\mapsto D\cup A$ injects $\mathcal{P}(C)$ into the family of dense subsets. The reverse injection is the inclusion into $\mathcal{P}(\mathbb{R})$. The Cantor-Schröder-Bernstein theorem gives equality.

A finite modification agrees with the identity map outside a finite exceptional set. Sorting that set gives a unique finite record of pairs $(x,f(x))$. Real-number pairing by separated digits encodes the record in $(0,1)$, and placing length-$n$ records in disjoint intervals $(n,n+1)$ gives an injection from all finite modifications into the real line. Conversely, changing the value at one fixed point gives a real-parameter family, so the Cantor-Schröder-Bernstein theorem shows this family has continuum cardinality.

The Cantor-Schröder-Bernstein theorem says that injections $X\to Y$ and $Y\to X$ imply a bijection $X\to Y$. Thus mutual cardinal inequalities imply equal cardinalities, without a choice assumption.

Write $\mathfrak{c}=2^{{\aleph }_0}=|\mathbb{R}|$. Standard cardinal arithmetic gives $\mathfrak{c}\cdot \mathfrak{c}=\mathfrak{c}$ and ${\mathfrak{c}}^{{\aleph }_0}=\mathfrak{c}$. The correspondence $x+iy\leftrightarrow (x,y)$ is a bijection $\mathbb{C}\leftrightarrow {\mathbb{R}}^2$. HenceEquivalently, the real axis supplies the lower inequality and a coding of two real coordinates supplies the upper one; Cantor-Schröder-Bernstein then gives the equality.

The Cantor-Schröder-Bernstein theorem states that injections $f:A\to B$ and $g:B\to A$ imply the existence of a bijection $A\to B$. Here is the injection-chain formal proof, so no fixed-point theorem is needed. Defineand setThe second branch is defined because $a\notin C$ implies $a\notin A_0$, hence $a\in g(B)$, and the inverse there is unique by injectivity of $g$. Each branch is injective. A collision between branches would have $f(c)=g^{-1}(a)$ with $c\in C$ and $a\notin C$, implying $a=g(f(c))\in C$, a contradiction. Thus $h$ is injective.

For surjectivity let $b\in B$. If $g(b)\notin C$, then $h(g(b))=b$. If $g(b)\in C$, it is not in $A_0$, so it belongs to some $A_{n+1}=g(f(A_n))$. There is $a\in A_n$ with $g(b)=g(f(a))$; injectivity of $g$ gives $b=f(a)=h(a)$. This proves that $h$ is a bijection and completes the theorem without the axiom of choice.

For the comparison of cardinalities take the power set of $\omega$ as the reference set. Its cardinality is by definitionThe remaining parts give explicit injections or bijections comparing each requested set with this one.

There is an injection from the power set of $\omega$ into the real numbers given byIf $S$ and $T$ first differ at $k$, the contribution at $k$ has magnitude $2/3^{k+1}$, while the entire later tail has magnitude at mostTheir real values are therefore different. This proves injectivity directly and avoids any ambiguity of numeral expansions.

Conversely, map a real number $x$ to the set $\{q\in \mathbb{Q}:q<x\}$. Distinct real numbers give distinct sets because the rational numbers are dense in the real line. Fixing a bijection between $\omega$ and the countable set $\mathbb{Q}$ turns this into an injection $\mathbb{R}\to \mathcal{P}(\omega )$. Cantor-Schröder-Bernstein theorem now gives

Constant sequences give an injection $\mathbb{R}\to {}^{\omega }\mathbb{R}$. For the opposite bound fix an enumeration $(q_m{)}_{m\in \omega }$ of the rational numbers and encode a sequence $(x_n)$ byDistinct sequences differ at some coordinate $n$; density of the rational numbers then makes their encoded sets differ at a pair $(n,m)$. Thus $E$ is injective. The Cartesian product $\omega \times \omega$ is countable; for example the Cantor pairing functionis a bijection with $\omega$. Consequently $\mathcal{P}(\omega \times \omega )$ is equinumerous with $\mathcal{P}(\omega )$, already equinumerous with $\mathbb{R}$. Apply Cantor-Schröder-Bernstein theorem to obtain

Hartogs theorem says that for every set $X$ there is a least ordinal $h(X)$ for which no injection $h(X)\to X$ exists. This does not require the axiom of choice. Form the set $W$ of well-orderings of subsets of $X$. It can be defined by the axiom schema of specification insiderecording a subset and its well-order. Each member of $W$ has a unique ordinal order type. Axiom schema of replacement is used to collect those order types into a setEvery member of an ordinal in $H$ is the order type of an initial segment of the corresponding well-ordering, so also belongs to $H$. Thus $H$ is a transitive set of ordinals and is itself an ordinal. An ordinal $\alpha$ belongs to $H$ exactly when it injects into $X$: use a bijection to a well-ordered subset in one direction, and transport the ordinal order along the injection in the other. If $H$ injected into $X$, this characterization would give $H\in H$, impossible for an ordinal. All smaller ordinals lie in $H$ and do inject into $X$. Therefore $H=h(X)$. Apart from the standard order-type theorem, the explicit collection of all order types is the Axiom schema of replacement step; no axiom of choice of a representative ordering for each type is needed.

Zorn's lemma states that a nonempty partially ordered set in which every chain has an upper bound has a maximal element. Use the Hartogs bound on partial ordinal injections to obtain a set-sized partially ordered set. Consider the partial injections into $X$ whose domains are ordinals. Hartogs theorem bounds every such domain strictly below $h=h(X)$. Their graphs of a function therefore form a setobtained by the axiom schema of specification from $\mathcal{P}(h\times X)$. Order $P$ by extension. It is nonempty because it contains the empty function. A chain has as an upper bound the union of its graphs of a function: extension makes this a function, injectivity is preserved, and its domain is an union of ordinals and hence an ordinal. Its range is contained in $X$, so Hartogs theorem forces its domain to be strictly below $h$; thus it belongs to $P$. The empty chain also has the empty function as an upper bound.

By Zorn's lemma choose a maximal $f:\alpha \to X$. If an element $x\in X$ lay outside its range, appending $f(\alpha )=x$ would give a larger injection on $\alpha +1$. Such an injection itself guarantees $\alpha +1<h$ by Hartogs theorem, so it is a legitimate member of $P$, contradicting maximality in a partially ordered set. Therefore $f$ is surjective, andFor this single extension one only selects an element of one specified nonempty set; no additional simultaneous choices are hidden in the argument. Zorn's lemma is the form of the axiom of choice used to obtain maximality in a partially ordered set.

Finally work with cardinals, represented by initial ordinals, and put $\mu =\max (\kappa ,\lambda )$. It is infinite by hypothesis. Nonzeroness of each factor gives an injection of the larger cardinal into the Cartesian product by holding a coordinate of the other fixed. The supplied infinite-ordinal square result gives $|\mu \times \mu |=\mu$. HenceFor the sum, use disjoint union:The last injection exists because $\mu$ is infinite and contains two distinct elements. Cantor-Schröder-Bernstein theorem turns both pairs of bounds into equalities, provingThese final operations are cardinal sum and multiplication, measuring disjoint unions and Cartesian products. They are not the noncommutative ordinal arithmetic considered in question 5.

The Cantor-Schröder-Bernstein theorem states that injections $f:A\to B$ and $g:B\to A$ imply the existence of a bijection $A\to B$. Here is a direct proof, avoiding any appeal to a fixed-point theorem. Let $A_0=A\setminus g(B)$, $A_{n+1}=g(f(A_n))$, and $C={\bigcup }_{n<\omega }{A}_n$. DefineThe second case is defined because $A\setminus C\subseteq g(B)$. On $C$, $f$ is a bijection onto $f(C)$. For $b\in B$, injectivity of $g$ and the construction of $C$ give $g(b)\in C$ if and only if $b\in f(C)$: $g(b)$ cannot be in $A_0$, so membership in $C$ means membership in some $g(f(A_n))$. Hence $g^{-1}$ bijects $A\setminus C$ onto $B\setminus f(C)$. The two pieces have disjoint domains and images and together cover $A,B$, proving $h$ bijective. This proof itself uses no choice.

Write $\mathfrak{c}=|\mathbb{R}|=2^{{\aleph }_0}$. We use the standard infinite-cardinal identities $\kappa \cdot {\aleph }_0=\kappa$, ${\kappa }^n=\kappa$ for positive finite $n$ and infinite $\kappa$, and $({\kappa }^{\lambda }{)}^{\mu }={\kappa }^{\lambda \cdot \mu }$, under the permitted axiom of choice. The map $z\mapsto (\mathrm{Re}z,\mathrm{Im}z)$ bijects $\mathbb{C}$ with ${\mathbb{R}}^2$. Therefore

True in ZF. For a set $A$, the singleton map injects $A$ into its power set. No map $f:A\to \mathcal{P}(A)$ is onto: the diagonal setdiffers from $f(a)$ at the element $a$ for every $a$. Thus there is no bijection between $A$ and its power set. The injection together with this failure proves $\boxed{\kappa <2^{\kappa }}$.

If strict comparison is formulated as injection in one direction but not the other, the Cantor-Schröder-Bernstein theorem, which requires no choice, excludes an injection of the power set back into $A$. This is Cantor's theorem in a choice-free form.

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.

The Cantor-Schröder-Bernstein theorem states that injections $A\hookrightarrow B$ and $B\hookrightarrow A$ imply a bijection $A\cong B$.

Let $\mathfrak{c}=|\mathbb{R}|$ and $\mathcal{D}=\{S\subseteq \mathbb{R}:S\text{ is dense in }\mathbb{R}\}$. Clearly $|\mathcal{D}|\le 2^{\mathfrak{c}}$. For the reverse bound, let $C$ be the usual Cantor set, of cardinality $\mathfrak{c}$. It is closed with empty interior, so $D=\mathbb{R}\setminus C$ is dense. The mapis injective, because $A=(D\cup A)\cap C$. Applying the Cantor-Schröder-Bernstein theorem givesOne can see $|C|=\mathfrak{c}$ by coding binary sequences as ternary expansions using only digits zero and two, together with the usual $|\{0,1{\}}^{\omega }|=|\mathbb{R}|$. The same fixed $D$ works for all subsets. This is the cardinality of the family of dense subsets of the reals.

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.

First apply the Cantor theorem by diagonalization. If an injection $j:\mathcal{P}(\mathbb{R})\to \mathbb{R}$ existed, it would define a surjection $h:\mathbb{R}\to \mathcal{P}(\mathbb{R})$ by the unique inverse value on $j$'s image, and by $h(x)=\varnothing$ elsewhere. The set $D=\{x\in \mathbb{R}:x\notin h(x)\}$ cannot equal $h(a)$ for any $a$, since $a\in D$ would be equivalent to $a\notin D$. This contradicts surjectivity. There is no injection from the power set of the real line into the real line.

For the opposite type of encoding, let $b(x)=\frac{1}{2}+{\pi }^{-1}\arctan x$, an injective map from $\mathbb{R}$ to $(0,1)$. Give $b(x)$ its canonical binary expansion, choosing the terminating expansion with trailing zeros whenever two expansions exist. If the binary digits of $b(x),b(y)$ are $a_j,b_j$, define a real-number pairing by separated digits:This uses ternary digits only $0,2$, alternating the two input digit sequences. If two outputs first differ at ternary position $k$, that difference has magnitude $2\cdot 3^{-k}$, while every later digit together contributes at most ${\sum }_{j>k}2\cdot 3^{-j}=3^{-k}$. Their outputs therefore differ. The digits recover both binary sequences, hence both inputs. Neither output endpoint $0$ nor $1$ occurs because the input numbers lie strictly between zero and one. Thus $H$ is an injection from ${\mathbb{R}}^2$ into $(0,1)\subset \mathbb{R}$. The ternary construction avoids an unjustified decimal-interleaving argument at ambiguous expansions.

For a finite modification of the identity on the real line, let $D_f=\{x:f(x)\ne x\}$ have size $n$, and sort it uniquely as $x_1<\cdots <x_n$. Its finite record is $(x_1,f(x_1),\dots ,x_n,f(x_n))$. It determines $f$ completely, with the identity used outside the recorded points. Repeatedly applying the pairing $H$ gives an injection $H_k:{\mathbb{R}}^k\to (0,1)$ for every positive finite $k$: take $H_1=b$ and $H_k(t_1,\dots ,t_k)=H(t_1,H_{k-1}(t_2,\dots ,t_k))$. Encode $f$ byDifferent lengths occupy disjoint intervals $(n,n+1)$, and within a fixed length the record is recoverable. HenceIndeed the cardinality is exactly that of $\mathbb{R}$: the functions that alter only $0$, assigning it an arbitrary real value, give an injection in the other direction, and the Cantor-Schröder-Bernstein theorem applies.

The Knaster–Tarski fixed-point theorem states that if $L$ is a complete lattice and $f:L\to L$ is order-preserving, then the fixed points of $f$ form a complete lattice; in particular, $f$ has least and greatest fixed points.

LetFor every $x\in P$, monotonicity gives $f(a)\le f(x)\le x$, so $f(a)\le a$. Applying $f$ once more shows $f(f(a))\le f(a)$, hence $f(a)\in P$. Therefore $a\le f(a)$ by the definition of $a$, and $f(a)=a$. Every fixed point belongs to $P$, so $a$ is the least fixed point. Dually, $\bigvee \{x:x\le f(x)\}$ is the greatest fixed point. For any family $S$ of fixed points, apply the same argument inside the upper interval above $\bigvee S$ to obtain the least fixed point above every member of $S$; this is their join in the fixed-point set. The dual construction supplies meets, proving the full statement.

To deduce the Cantor-Schröder-Bernstein theorem, let $i:A\to B$ and $j:B\to A$ be injections. On the complete lattice $\mathcal{P}(A)$ defineThis map is order-preserving, so it has a fixed point $X$. The relationshows thatis a bijection: its two pieces map bijectively onto the disjoint sets $i(X)$ and $B\setminus i(X)$. Thus injections both ways imply a bijection.

Let $P$ be the poset of countable subsets of $\mathbb{R}$. The family of all singletons $\{\{r\}:r\in \mathbb{R}\}$ has no upper bound in $P$, since any upper bound would contain every real number and would be uncountable. Therefore

Finally, use the well-ordering theorem to fix a well-order $\prec$ of $\mathbb{R}$. Every countable $A$ omits some real number; let $m(A)$ be its $\prec$-least omitted element and defineIf $A\subseteq B$, then either $m(A)\in B$, or every point preceding $m(A)$ lies in $A\subseteq B$ and $m(A)=m(B)$. In either case $f(A)\subseteq f(B)$, so $f$ is order-preserving. Yet $m(A)\notin A$, and henceThis does not contradict Knaster–Tarski because $P$ is not a complete lattice.

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.

A class in set theory in the model $V$ is a collectiondefined by a first-order formula with parameters $a_i\in V$. A set-theoretic class function is a definable class relation $F$ for which every input in its domain has exactly one output. Informally, the Axiom schema of replacement says that the image $F‘‘a$ of any set $a$ under any such function class is again a set.

Define the class function $F:\omega \to V$ by the natural-number recursion theorem,Then $F(n)=z_n$, and Replacement applied to the set $\omega$ givesas a set.

Call a set small when it injects into some $z_n$. Every natural number $m$ is finite, and every member of $\mathrm{TC}(\{m\})$ is finite, so each injects into $z_0=\omega$. Hence $m\in \mathbf{HS}$. The set $\omega$ itself injects into $z_0$, and its hereditary members are natural numbers, so $\omega \in \mathbf{HS}$.

We next prove $z_n\in \mathbf{HS}$ by mathematical induction. The case $z_0=\omega$ was just proved. If $z_n\in \mathbf{HS}$ and $u\in z_{n+1}=\mathcal{P}(z_n)$, then $u\subseteq z_n$, so inclusion injects $u$ into $z_n$ and makes $u$ small. Every set below $u$ in its transitive closure is already below $z_n$ and is small by the induction hypothesis. The set $z_{n+1}$ itself injects into $z_{n+1}$. Thus every member of $\mathrm{TC}(\{z_{n+1}\})$ is small.

By Cantor theorem, $|z_{n+1}|>|z_n|$, so the $z_n$ are distinct and $z_n\mapsto n$ injects $y$ into $\omega =z_0$. Thus $y$ is small. Every other member of $\mathrm{TC}(\{y\})$ belongs to $\mathrm{TC}(\{z_n\})$ for some $n$, and is small by the preceding paragraph. Therefore $y\in \mathbf{HS}$. This proves the finite-power-set hereditary-small construction.

The structure $(\mathbf{HS},\in )$ is not a model of ZF because it fails the Axiom of union. If $\bigcup y$ were small, it would inject into some $z_m$. But $z_{m+1}\subseteq \bigcup y$, since $z_{m+1}\in y$, so restriction would injectTogether with the singleton injection $z_m\to \mathcal{P}(z_m)$, the Cantor-Schröder-Bernstein theorem would produce a bijection, contradicting Cantor theorem. Hence $\bigcup y$ is not small and therefore does not belong to $\mathbf{HS}$. Since $y\in \mathbf{HS}$ has no union inside the class, the Union axiom fails.

Let $f:X\to A\subseteq Y$ be an order isomorphism onto a down-set, and let $g:Y\to U=X\setminus B$ be an order isomorphism onto the complement of a down-set $B$. Define increasing down-setsThe order assumptions ensure inductively that each $D_n$ is a down-set. DefineThe usual Cantor-Schröder-Bernstein theorem orbit argument shows that these two pieces partition both domain and codomain bijectively: points generated from $B$ move forward through $f$, while every remaining point lies in $U$ and moves backward through $g$. Each branch preserves order. If $x\in D$ and $x^{\prime }<x$ then $x^{\prime }\in D$; hence the only mixed case has $x\notin D<x^{\prime }\in D$, and the initial/final-segment hypotheses put $h(x)<h(x^{\prime })$. Thus $h$ is an order isomorphism and

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.