Hartogs number


In mathematics, specifically in set theory">Set (mathematics)">set theory, the Hartogs number of a set is the least ordinal number such that there is no injection from into. In other words, is the least ordinal such that . The existence of the Hartogs number of any can be proved in Zermelo–Fraenkel set theory without relying on the axiom of choice. The map taking to is sometimes called Hartogs's function.
If can be well-ordered, then, since the cardinalities of two well-ordered sets are always comparable. In fact, is the successor cardinal of. Hartogs's function thus plays a role in constructing the aleph numbers, which are all the cardinal numbers of infinite well-orderable sets.
If cannot be well-ordered, then there cannot be an injection from to, so cannot be true, and thus is incomparable to. Conversely, trichotomy for cardinal numbers thus implies that every set can be well-ordered, and hence implies the axiom of choice.
The existence of the Hartogs number was proved by Friedrich Hartogs in 1915, using Zermelo set theory alone. Since Zermelo set theory does not have canonical representatives for ordinal numbers, in Hartogs's result is allowed to be any well-ordered set with the appropriate order type, and this result can be proved without the replacement schema. In the usual ZF formalization, the replacement schema is needed to convert this well-ordered set to its von Neumann ordinal.

Hartogs's theorem

Hartogs's theorem states that for any set, there exists an ordinal such that ; that is, such that there is no injection from to as sets. As ordinals are well-ordered, this immediately implies the existence of a Hartogs number for any set, namely the least ordinal with that property. Furthermore, the proof is constructive and yields the Hartogs number of.
Intuitively, the Hartogs number of is exactly the order type of all ordinals such that there is an injection from to, so it suffices to show that such form a set. Importantly, an injection to is also a bijection from to a subset of, meaning that is the order type of some well-ordering of that subset. Since a well-ordering is just a special binary relation, the set of all possible well-orderings of subsets of can be constructed with standard techniques, and the set of all can then be represented in Z as a set of equivalence classes with respect to order isomorphism, without resort to Fraenkel's Axiom schema of replacement.

Proof

See.
Let be the class of all ordinal numbers β for which an injective function exists from β into X.
First, we verify that α is a set.
  1. X × X is a set, as can be seen in the article Axiom of power set.
  2. The power set of X × X is a set, by the axiom of power set.
  3. The class W of all reflexive well-orderings of subsets of X is a definable subclass of the preceding set, so it is a set by the axiom schema of separation.
  4. The class of all order types of well-orderings in W is a set by the axiom schema of replacement, as can be described by a simple formula.
But this last set is exactly α. Now, because a transitive set of ordinals is again an ordinal, α is an ordinal. Furthermore, there is no injection from α into X, because if there were, then we would get the contradiction that α ∈ α. And finally, α is the least such ordinal with no injection into X. This is true because, since α is an ordinal, for any β < α, β ∈ α so there is an injection from β into X.

Historical remark

In 1915, Hartogs could use neither von Neumann-ordinals nor the replacement axiom, and so his result is one of Zermelo set theory and looks rather different from the modern exposition above. Instead, he considered the set of isomorphism classes of well-ordered subsets of X and the relation in which the class of A precedes that of B if A is isomorphic with a proper initial segment of B. Hartogs showed this to be a well-ordering greater than any well-ordered subset of X. However, the main purpose of his contribution was to show that trichotomy for cardinal numbers implies the well-ordering theorem.