The Hartog's number of a cardinal number is the number of ways to well-order a set of cardinality at most . Assuming the axiom of choice, it is the smallest ordinal number whose cardinality is greater than and therefore the successor of as a cardinal number. But even without the axiom of choice, it makes sense and is often an effective substitute for such a successor.
So let be a set. Without the axiom of choice (or more precisely, the well-ordering theorem), it may not be possible to well-order itself, but we can certainly well-order some subsets of . On the other hand, if we can well-order (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 , that is the subset of
where indicates disjoint union and indicates power set, consisting of those pairs such that 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 is this well-ordered set, the set of all order types of well-ordered subsets of . If is the cardinality of , then let be the cardinality or ordinal rank (as desired) of the Hartog's number of ; this is called the Hartog's number of .
There is no injection to from the Hartog's number of ; 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, . So if this is a total order (a statement equivalent to the axiom of choice), we can say that .
Even without choice, however, we can say this: If is an ordinal number such that , then . (Notice that we've shifted our thinking of the Hartog's number from a cardinal to an ordinal.) That is, is the smallest ordinal number whose cardinal number is not at most . This doesn't use any form of choice except for excluded middle; we only need choice to conclude that .
The axiom of choice also implies the well-ordering theorem, that any set can be well-ordered. Thus with choice, is (now as a cardinal again) the smallest cardinal number greater than ; this explains the notation .
For the cardinality of the set of all natural numbers, the Hartog's number is the smallest uncountable ordinal. Assuming the axiom of choice (countable choice and excluded middle are enough), we have as a cardinal.
In general, we get a sequence 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 . (Actually, there's no real need to begin with infinite cardinals; if we started with instead of and instead of , then absolutely every cardinality or well-orderable cardinality would appear.)