Hartog's number

The Hartog's number of a cardinal number κ\kappa is the number of ways to well-order a set of cardinality at most κ\kappa. Assuming the axiom of choice, it is the smallest ordinal number whose cardinality is greater than κ\kappa and therefore the successor of κ\kappa as a cardinal number. But even without the axiom of choice, it makes sense and is often an effective substitute for such a successor.


We will define the Hartog's number as a functorial operation from sets to well-ordered sets. The operation on numbers is just a round-about way of talking about the same thing.

So let SS be a set. Without the axiom of choice (or more precisely, the well-ordering theorem), it may not be possible to well-order SS itself, but we can certainly well-order some subsets of SS. On the other hand, if we can well-order SS (or a subset), then there may be many different ways to do so, even nonisomorphic ways. So to begin with, let us form the collection of all well-ordered subsets of SS, that is the subset of

A:𝒫S𝒫(A×A), \coprod_{A: \mathcal{P}S} \mathcal{P}(A \times A) ,

where \coprod indicates disjoint union and 𝒫\mathcal{P} indicates power set, consisting of those pairs (A,R)(A,R) such that RR is a well-ordering. Then form a quotient set by identifying all well-ordered subsets that are isomorphic as well-ordered sets. This gives a set of well-order types, or ordinal numbers, which can itself be well-orderd by the general theory of ordinal numbers.

The Hartog's number of SS is this well-ordered set, the set of all order types of well-ordered subsets of SS. If κ\kappa is the cardinality of SS, then let κ +\kappa^+ be the cardinality or ordinal rank (as desired) of the Hartog's number of SS; this is called the Hartog's number of κ\kappa.


There is no injection to SS from the Hartog's number of SS; this theorem is to Cantor's theorem as Burali-Forti's paradox is to Russell's paradox. That is, using the usual ordering of cardinal numbers, κ +κ\kappa^+ \nleq \kappa. So if this \leq is a total order (a statement equivalent to the axiom of choice), we can say that κ +>κ\kappa^+ \gt \kappa.

Even without choice, however, we can say this: If α\alpha is an ordinal number such that |α|κ|\alpha| \nleq \kappa, then κ +α\kappa^+ \leq \alpha. (Notice that we've shifted our thinking of the Hartog's number from a cardinal to an ordinal.) That is, κ +\kappa^+ is the smallest ordinal number whose cardinal number is not at most κ\kappa. This doesn't use any form of choice except for excluded middle; we only need choice to conclude that |κ +|>κ|\kappa^+| \gt \kappa.

The axiom of choice also implies the well-ordering theorem, that any set can be well-ordered. Thus with choice, κ +\kappa^+ is (now as a cardinal again) the smallest cardinal number greater than κ\kappa; this explains the notation κ +\kappa^+.


For nn a natural number regarded as the cardinal number of a finite set, n +n^+ is the usual successor n+1n + 1. This result uses excluded middle; else we get the plump successor of nn, which may be rather larger.

For 0\aleph_0 the cardinality of the set of all natural numbers, the Hartog's number 0 +=ω 1\aleph_0^+ = \omega_1 is the smallest uncountable ordinal. Assuming the axiom of choice (countable choice and excluded middle are enough), we have 0 += 1\aleph_0^+ = \aleph_1 as a cardinal.

In general, we get a sequence ω α\omega_\alpha of infinite cardinalities of well-orderable sets; assuming excluded middle, every infinite well-orderable cardinality shows up in this sequence. Assuming the axiom of choice, every infinite cardinal shows up, and we have |ω α|= α|\omega_\alpha| = \aleph_\alpha. (Actually, there's no real need to begin with infinite cardinals; if we started with ω 0=0\omega_0 = 0 instead of ω 0=N\omega_0 = \mathbf{N} and 0=0\aleph_0 = 0 instead of 0=|N|\aleph_0 = |\mathbf{N}|, then absolutely every cardinality or well-orderable cardinality would appear.)

Revised on September 20, 2012 05:37:27 by Mike Shulman (