Cardinal number

In the presence of choice, a cardinal number may be represented by the least ordinal in its bijection class.

An infinite cardinal number is a limit cardinal if it is not a successor cardinal; equivalently it is an aleph number with zero or a limit ordinal as index. Uncountable limit cardinals are either singular cardinals or weakly inaccessible cardinals. This concerns succession among cardinals, rather than merely being a limit ordinal.

The cardinality $|X|$ of a set $X$ is the cardinal number shared by all sets in bijection with $X$. For a finite set, it is the number of elements.

The successor cardinal ${\kappa }^{+}$ is the least cardinal number strictly larger than $\kappa$.

The cofinality of an ordinal $\alpha$ is the least order type of an unbounded subset of $\alpha$, equivalently the least ordinal $\beta$ admitting a cofinal function $\beta \to \alpha$.

At a nonzero limit ordinal $\delta$, a strictly increasing continuous sequence of cardinals $({\kappa }_{\alpha }{)}_{\alpha \le \delta }$ satisfies $\mathrm{cf}({\kappa }_{\delta })=\mathrm{cf}(\delta )$. A cofinal sequence of indices gives the upper bound. Conversely, bounds for a cofinal set of values must have cofinal indices, giving the lower bound. In particular the assertion applies to Beth numbers.

A map $f:\delta \to \alpha$ whose range is cofinal: every $\xi <\alpha$ lies below or equals some $f(\eta )$. It need not be increasing.

If $\alpha$ is a nonzero limit ordinal and $({\gamma }_{\xi }{)}_{\xi <\alpha }$ is strictly increasing, then $\mathrm{cf}({\sup }_{\xi <\alpha }{\gamma }_{\xi })=\mathrm{cf}(\alpha )$. A cofinal subsequence of the index order gives one inequality. Conversely, a cofinal family in the supremum determines a cofinal family of indices by choosing an index past each of its values. This also explains the cofinality of limit-indexed aleph numbers.

An infinite cardinal number $\kappa$ is singular when $\mathrm{cf}(\kappa )<\kappa$. Thus a short cofinal function reaches arbitrarily high ordinals below $\kappa$. For example, ${\aleph }_{\omega }$ has cofinality $\omega$. The complementary case is a regular cardinal.

If the power-set function is eventually constant below a singular cardinal $\kappa$, its constant value persists at $\kappa$. Writing $\theta =\mathrm{cf}(\kappa )$ gives $2^{\kappa }=(2^{<\kappa }{)}^{\theta }$. On the plateau choose a cardinal $\mu \ge \theta$, so $(2^{\mu }{)}^{\theta }=2^{\mu \cdot \theta }=2^{\mu }$.

Write ${\sigma }_{\alpha }$ for the $\alpha$th uncountable singular cardinal in increasing order. It begins with ${\sigma }_0={\aleph }_{\omega }$ and ${\sigma }_1={\aleph }_{\omega +\omega }$. At a nonzero limit ordinal index it is continuous exactly when the supremum of its earlier values is singular. It can jump when that supremum is a weakly inaccessible cardinal. The first member of uncountable cofinality occurs at index ${\omega }_1$, with value ${\aleph }_{{\omega }_1}$.

There is an uncountable cardinal number $\kappa$ with ${\sigma }_{\kappa }=\kappa$. Iterate ${\kappa }_{n+1}={\sigma }_{{\kappa }_n}$ starting with ${\aleph }_0$. If there is no earlier fixed point, the increasing supremum $\kappa$ has countable cofinality, hence is a singular cardinal. The singular cardinal enumeration is cofinal in $\kappa$ below index $\kappa$, and continuity at this singular supremum gives equality.

The singular cardinals hypothesis asserts that every infinite singular cardinal $\kappa$ satisfiesEquivalently, $\gimel (\kappa )=\max \{{\kappa }^{+},2^{\mathrm{cf}(\kappa )}\}$ for every infinite singular cardinal. Here $\gimel$ is the gimel function. The Generalized continuum hypothesis implies this principle, but the principle only constrains the indicated singular-cardinal exponentiation.

A function $f:\beta \to \alpha$ between ordinals is cofinal when its range is unbounded in $\alpha$: for every $\gamma <\alpha$ some $\xi <\beta$ satisfies $\gamma \le f(\xi )$.

An infinite cardinal $\kappa$ is regular when its cofinality is $\kappa$.

A large cardinal property strengthens uncountability by imposing combinatorial, logical, measure-like, or elementary-embedding structure whose existence is not provable in ZFC if ZFC is consistent.

An inaccessible cardinal $\kappa$ whose inaccessible ordinals below it form a stationary set. Equivalently, every predicate expansion of $V_{\kappa }$ has an inaccessible elementary rank level below $\kappa$.

If $\kappa$ is Mahlo in $V$, then it is Mahlo in $L$. Inaccessibility is downward absolute, and every club in $L$ remains a club in $V$, where it meets a $V$-inaccessible ordinal.

A weakly inaccessible cardinal is an uncountable regular cardinal that is a limit cardinal. It need not be a strong limit cardinal. Under the Generalized continuum hypothesis, it is a strongly inaccessible cardinal, since every smaller infinite $\lambda$ satisfies $2^{\lambda }={\lambda }^{+}<\kappa$.

A weakly inaccessible cardinal $\kappa$ is weakly Mahlo if $\{\alpha <\kappa :\alpha =\mathrm{cf}(\alpha )\}$ is a stationary set. Intersecting this set with the club set of uncountable limit cardinals shows that the weakly inaccessible cardinals below $\kappa$ are stationary, hence unbounded.

Consistency of ZFC implies consistency of ZFC with the Generalized continuum hypothesis and no weakly inaccessible cardinals. Pass to the constructible universe. If it has an inaccessible, cut at its least one; that rank segment still models ZFC and the Generalized continuum hypothesis, but has no inaccessibles. In this model the singular cardinal enumeration is continuous at every nonzero limit ordinal index. This is a relative-consistency construction, not a deduction of a transitive model from bare consistency.

A cardinal $\kappa$ is a strong limit when $2^{\lambda }<\kappa$ for every cardinal $\lambda <\kappa$.

A strongly inaccessible cardinal is an uncountable regular strong limit cardinal.

An inaccessible cardinal $\iota$ is an inaccessible limit of inaccessibles if the inaccessible cardinals below it are unbounded in $\iota$. A rank cutoff at the first inaccessible limit of inaccessibles shows that existence of unboundedly many inaccessibles does not prove existence of such a limit, provided the former theory is consistent.

If $\iota$ is the least inaccessible limit of inaccessibles, $V_{\iota }$ models ZFC and internally has unboundedly many inaccessible cardinals, while none of its ordinals is an inaccessible limit of inaccessibles. Rank agreement makes inaccessibility below $\iota$ absolute. If a model of unboundedly many inaccessibles has no such limit in the first place, no cutoff is needed. This proves the corresponding relative-consistency nonimplication.

An inaccessible cardinal $\kappa$ has the Keisler extension property when there is a proper transitive set $X⊋V_{\kappa }$ for whichSuch a $\kappa$ is not the least inaccessible cardinal: $X$ regards $\kappa$ as inaccessible, elementarity reflects the existence of an inaccessible into $V_{\kappa }$, and strong-inaccessibility absoluteness from rank agreement makes the resulting witness genuinely inaccessible below $\kappa$.

A cardinal $\kappa$ is worldly when $V_{\kappa }\models \mathrm{ZFC}$. Every strongly inaccessible cardinal is worldly, but worldly cardinals can be singular.

Below any uncountable strongly inaccessible cardinal $\kappa$, the worldly cardinals contain a closed unbounded subset of $\kappa$ and hence have cardinality $\kappa$. The structure $V_{\kappa }$ models ZFC. Reflect each finite group from an enumeration of all first-order formulas to a closed unbounded subset of $\kappa$, using $|V_{\alpha }|<\kappa$ and regularity for the witness bounds. The countable intersection remains closed unbounded, so its ranks are elementary substructures of $V_{\kappa }$. Intersect with the closed unbounded subset of infinite cardinal numbers below $\kappa$. Uncountability is essential: the regular strong limit $\omega$ has no worldly cardinal below it.

A worldly cardinal permits a countable transitive model $M$ of ZFC and a transitive model $N$ of ZFC with $M\in N$, $|N|={\aleph }_1$, and $({\omega }_1{)}^N={\omega }_1$. First collapse a countable elementary substructure of $V_{\kappa }$. Then collapse an ${\aleph }_1$-sized Skolem hull containing every countable ordinal and every member of $M$, as well as $M$ itself. The transitive collapse fixes transitive subsets lemma preserves $M$ and those ordinals.

If $V_{\kappa }\models \mathrm{ZFC}$, it has the standard natural numbers and standard finite proofs. Every arithmetical sentence, including a formal consistency statement, therefore has the same truth value in $V_{\kappa }$ and the universe.

A theory is $\kappa$-satisfiable when each of its subtheories of cardinality less than $\kappa$ has a model.

For cardinal properties $\Phi$ and $\Psi$ that occur, let ${\iota }_{\Phi }$ and ${\iota }_{\Psi }$ be their least witnesses. Define $\Phi {<}_1\Psi$ whenThis relation need not be transitive, because the two implications can be proved under different joint existence assumptions.

Let $I,W,M$ mean inaccessible, weakly compact, and measurable, and defineThen $I{<}_{1}W$ and $W{<}_1\Theta$. Subject to the consistency of an inaccessible without a weakly compact cardinal, there is also a model in which $\Theta =I$, so $I/{<}_1\Theta$.

An uncountable cardinal $\kappa$ is weakly compact when every $\kappa$-satisfiable theory in an $L_{\kappa ,\kappa }$ language having at most $\kappa$ nonlogical symbols is satisfiable.

An uncountable cardinal $\kappa$ is measurable when it carries a nonprincipal $\kappa$-complete ultrafilter.

A cardinal is omega-measurable if it carries a countably complete ultrafilter that is a nonprincipal ultrafilter. Countable completeness rules out countable underlying sets. Such a measure is weaker than the cardinal's own full completeness requirement, but the least omega-measurable cardinal is measurable.

If $\kappa$ is the least omega-measurable cardinal and $U$ witnesses it, failure of $\kappa$-completeness partitions a member of $U$ into fewer than $\kappa$ fibres, none belonging to $U$. The pushforward ultrafilter under the fibre-index map is then a nonprincipal countably complete measure on a smaller cardinal, a contradiction. Thus $U$ is $\kappa$-complete and $\kappa$ is a measurable cardinal.

Let $U$ be a nonprincipal $\kappa$-complete ultrafilter on $\kappa$. If $\lambda <\kappa$ and $(A_{\alpha }{)}_{\alpha <\kappa }$ were distinct subsets of $\lambda$, then for every $\xi <\lambda$ choose the $U$-large side of the partition according to whether $\xi \in A_{\alpha }$. Their intersection is $U$-large by $\kappa$-completeness, but all its indices label the same subset of $\lambda$, so it has at most one member, contradicting nonprincipality. Thus $2^{\lambda }<\kappa$.

The ultrapower embedding $j:V_{\lambda }\to M$ associated with a measure on $\kappa <\lambda$ has critical point $\kappa$. For every $A\in V_{\kappa +1}$,so $V_{\kappa +1}\subseteq M$. Hence every measurable cardinal is 1-strong.

Let ${\kappa }_0<{\kappa }_1<\lambda$, where both ${\kappa }_i$ are measurable and $\lambda$ is inaccessible, and let $j_i:V_{\lambda }\to M_i$ be ultrapower embeddings by measures on ${\kappa }_i$. ThenThe second equality follows from the critical point. For the first, regularity gives continuity of $j_0$ at ${\kappa }_1$, while strong-limitness bounds $j_0(\beta )<{\kappa }_1$ for every $\beta <{\kappa }_1$.

For a measure ultrapower $j:V_{\lambda }\to M$ with critical point $\kappa$, there are at most $2^{\kappa }$ equivalence classes of functions $\kappa \to \kappa$, so $|j(\kappa )|\le 2^{\kappa }$ in $V_{\lambda }$. The target $M$ regards $j(\kappa )$ as measurable and contains $V_{\kappa +1}$, so it sees $(2^{\kappa }{)}^M<j(\kappa )$. Under the Generalized continuum hypothesis, this places $j(\kappa )$ strictly above the ambient ${\kappa }^{+}$ while its ambient cardinality is at most ${\kappa }^{+}$; hence it is not an ambient cardinal.

An uncountable cardinal $\kappa$ is strongly compact when every $\kappa$-satisfiable theory in any $L_{\kappa ,\kappa }$ language is satisfiable, with no bound on the number of nonlogical symbols.

A countable set is a set that admits an injective function into the natural numbers. It is therefore either a finite set or a countably infinite set.

Every family of pairwise disjoint nonempty open disks in the plane is countable. The density of the rational numbers gives each disk a point of the countable set ${\mathbb{Q}}^2$. Fixing an enumeration and taking the first point in each disk yields an injection from disks to labels. This argument requires no countable choice of representatives and is useful when geometric separation would otherwise produce an uncountable family.

A family of countable sets indexed by a linear order is increasing if $i\le j$ implies $X_i\subseteq X_j$. Its union has cardinality at most ${\aleph }_1$, by the cardinal bound for an increasing chain of countable sets. The index order need not be a well-order.

An increasing chain of countable sets has union of cardinality at most ${\aleph }_1$. If the union is uncountable, select ${\aleph }_1$ of its points and one containing member for each. Every countable member misses one selected point, so linear comparison puts it below that point's chosen member. The chosen subfamily is cofinal, and its union has size at most ${\aleph }_1$ by infinite cardinal arithmetic.

A finite Cartesian product of countable sets is countable. For a fixed finite exponent $m$, index tuples in ${\mathbb{N}}^m$ can be listed by increasing maximum coordinate, with each group finite. If $B$ is countably infinite and $m>0$, its power $B^m$ is also countably infinite.

Given finite lists ${\ell }_0,{\ell }_1,\dots$ in a set $X$, their union of entries has an explicit enumeration from a subset of ${\mathbb{N}}^2$: use the existing positions in each list and a Cantor pairing function. If the union is infinite, successively take the first occurrence of an entry not previously taken, in the order of its natural-number code. The well-order on natural numbers makes each step uniquely determined and yields an injection $\mathbb{N}\to X$. No axiom of choice is needed. This does not assert that an arbitrary countable family of unordered finite sets has a countable union in ZF without the axiom of choice.

If every sequence of distinct elements of a positive-real set $A$ has arithmetic averages tending to zero, then $A$ is a countable set. For each positive integer $n$, the threshold set $\{a\in A:a\ge 1/n\}$ must be finite: an infinite sequence inside it would have averages at least $1/n$. The Archimedean property makes $A$ their union, so the countable union of countable sets theorem applies. The hypothesis concerns every distinct-element sequence, not merely one enumeration.

A countably infinite set admits a bijection with the natural numbers.

For an infinite subset $A\subseteq \mathbb{N}$, repeatedly selecting the least element not yet used gives a bijection $f:\mathbb{N}\to A$. The well-order ensures each minimum exists, infinitude ensures the remaining set is nonempty, and strict increase gives injectivity. If $a\in A$ were omitted forever, all selected values would be at most $a$, impossible inside the finite set $\{0,\dots ,a\}$.

A countable union of countable sets is countable, using a diagonal enumeration.

A parabola parametrized by $(t,t^2)$ is in bijection with $\mathbb{R}$ and is an uncountable set. Every affine line meets it in at most two points. A countable family of affine lines could therefore cover only countably many points of this parabola, and cannot cover the plane. More generally, an uncountable curve with finite intersection with every permitted member obstructs a countable covering by those members.

The Cantor pairing function is an explicit bijection between ${\mathbb{N}}^2$ and $\mathbb{N}$, obtained by enumerating lattice points along successive diagonals.

Cantor's diagonal argument proves that the infinite binary sequences form an uncountable set: a sequence obtained by changing the $n$th digit of the $n$th listed sequence differs from every sequence in the list.

An uncountable set is a set for which no bijection with a subset of the natural numbers exists.

The bijections of a countably infinite set form an uncountable set. Partition an enumeration into disjoint pairs and encode an infinite binary sequence by independently fixing or swapping each pair.

If $B$ is a countably infinite set and $A$ is a finite set with at least two elements, the set of surjective functions $B\to A$ is uncountable. Fix finitely many values to cover $A$, then encode an arbitrary infinite binary sequence using two values of $A$ on the remaining inputs.

An initial ordinal is an ordinal not equinumerous with any smaller ordinal. It is therefore the canonical ordinal representative of a cardinal.

The alephs enumerate the infinite initial ordinals: ${\aleph }_0=\omega$, successor indices select the next initial ordinal, and limit indices select the least initial ordinal above all earlier values.

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

Cardinal sums are cardinalities of disjoint unions, products are cardinalities of Cartesian products, and exponentials ${\kappa }^{\lambda }$ count functions from a set of size $\lambda$ to one of size $\kappa$.

For an infinite cardinal number, $\gimel (\kappa )={\kappa }^{\mathrm{cf}(\kappa )}$. The singular cardinals hypothesis predicts its value when $\kappa$ is a singular cardinal and $2^{\mathrm{cf}(\kappa )}<\kappa$. For a regular cardinal, its value is $2^{\kappa }$.

The Gimel function determines all infinite cardinal powers. For a regular base, $2^{\kappa }=\gimel (\kappa )$. For a singular base, put $s={\sup }_{\rho <\kappa }{2}^{\rho }$ and $\theta =\mathrm{cf}(\kappa )$; then $2^{\kappa }=s^{\theta }$, which is $s$ if attained below $\kappa$ and $\gimel (s)$ otherwise. After these powers are known, fix an infinite exponent $\lambda$ and recurse on the base. Below $\lambda$ use $2^{\lambda }$; at successors use the Hausdorff formula for cardinal exponentiation. At a limit base greater than $\lambda$, put $a={\sup }_{\rho <\kappa }{\rho }^{\lambda }$. The answer is $a$ if $\mathrm{cf}(\kappa )>\lambda$ or the supremum is attained, and $\gimel (a)$ otherwise. In the nonattained cases, the cofinal-index argument identifies the cofinality of the supremum.

For every singular infinite cardinal number $\kappa$, the Gimel function has the smallest value permitted by König theorem for cardinal numbers and the exponent: ${\kappa }^{\mathrm{cf}(\kappa )}=\max \{{\kappa }^{+},2^{\mathrm{cf}(\kappa )}\}$. Where $2^{\mathrm{cf}(\kappa )}<\kappa$, this is the singular cardinals hypothesis. The hypothesis imposes no separate successor-power condition on regular cardinals.

The cardinal numbers defined by ${\beth }_0={\aleph }_0$, ${\beth }_{\alpha +1}=2^{{\beth }_{\alpha }}$, and ${\beth }_{\lambda }={\sup }_{\alpha <\lambda }{\beth }_{\alpha }$ at limit ordinals are the beth numbers. In particular ${\beth }_1=|\mathcal{P}(\omega )|$, the cardinality of the continuum. This notation distinguishes iterated power sets from the enumeration by Aleph numbers of well-orderable infinite cardinal numbers.

In ZF, let $K,L$ be nonempty. If $K\times L$ injects into $K\bigsqcup L$, then there is either an injection or a surjection from $K$ to $L$.

Indeed, extend the inverse of the given injection to a surjection $p:K\bigsqcup L\to K\times L$ by sending points outside its range to one fixed pair $(k_{\ast },l_{\ast })$. If the second coordinate of $p$ restricted to the $K$-summand covers $L$, it is the required surjection. Otherwise choose $l_0$ that it misses. Every $(k,l_0)$ then has its preimage in the $L$-summand. Except possibly for the default pair, that preimage is unique, so these preimages inject $K$ into $L$. In the exceptional case they inject $K\setminus \{k_{\ast }\}$ into $L$; either their image is all of $L$, yielding a surjection from $K$, or an omitted point extends the map to an injection from $K$.

For infinite cardinals, choice gives $\kappa +\kappa =\kappa \cdot \kappa =\kappa$. Exponentiation satisfies $({\kappa }^{\lambda }{)}^{\mu }={\kappa }^{\lambda \mu }$, while a countable sum of cardinals has size the maximum of ${\aleph }_0$ and their supremum.

There is a natural bijection between functions $M\to K^L$ and functions $M\times L\to K$, obtained by sending $f$ to $(m,l)\mapsto f(m)(l)$. Therefore

Assuming the axiom of choice, every infinite cardinal satisfiesOne proof takes a least counterexample $\kappa$, identifies cardinals with initial ordinals, and well-orders $\kappa \times \kappa$ first by $\max \{\alpha ,\beta \}$. Every proper initial segment then has cardinality below $\kappa$ by minimality, so the whole order has cardinality at most $\kappa$, contradicting the choice of $\kappa$.

For infinite cardinals $\kappa$ and $\lambda$, the axiom of choice and the square of an infinite cardinal giveThe maximum is a lower bound for both operations, while both are bounded above by respectively $\mu +\mu$ and ${\mu }^2$, where $\mu =\max \{\kappa ,\lambda \}$.

For finitely many infinite sets $X_1,\dots ,X_n$, choose one whose cardinality $\kappa$ is largest. Thenso the union has the same cardinality as that largest member.

Pairwise distinct cardinalities do not prevent a countable family from having a largest member. For example, take $X_1={\aleph }_{\omega }$ and $X_{n+2}={\aleph }_n$ for $n<\omega$, viewing cardinals as initial ordinals. Every later set is a subset of $X_1$, soalthough all the cardinalities are different.

If $\lambda$ is infinite and $2\le \kappa \le \lambda$, thenIndeed,

If ${\kappa }_i<{\lambda }_i$ for every $i\in I$, thenThe injection uses functions supported at one coordinate. For non-surjectivity, given any map from the disjoint union to the product, choose at coordinate $i$ a value omitted by the $i$th row; the resulting diagonal element is outside its image.

For infinite cardinals $\kappa ,\lambda$, Hausdorff's formula is

The continuum hypothesis asserts that every infinite subset of the real numbers is either countable or equinumerous with the real numbers, equivalently $2^{{\aleph }_0}={\aleph }_1$.

Every function $f:\mathbb{R}\to [\mathbb{R}{]}^{<{\omega }_1}$ has reals $x,y$ with $x\notin f(y)$ and $y\notin f(x)$. The values are countable subsets. Requiring distinct witnesses is equivalent, by first adjoining $x$ to $f(x)$. The Freiling theorem identifies this axiom with the negation of the Continuum hypothesis in ZFC.

In ZFC, the Freiling axiom of symmetry is equivalent to failure of the Continuum hypothesis. Under the hypothesis, countable initial segments of a well-order of the reals violate symmetry. When the continuum exceeds ${\aleph }_1$, the union of the countable values on an ${\aleph }_1$-sized set leaves a real outside; avoiding that real's countable value gives the two witnesses.

The generalized continuum hypothesis states that $2^{\kappa }={\kappa }^{+}$ for every infinite cardinal number $\kappa$.

If there are injections $X\to Y$ and $Y\to X$, then there is a bijection $X\cong Y$.