In mathematics, specifically in axiomatic set theory, the Hartogs number of a set X is the least ordinal number α such that there is no injection from α into X. In other words, α is the least ordinal such that | α | ≰ | X | {\displaystyle |\alpha |\not \leq |X|} (where |A| denotes the cardinality of a set A). The existence of the Hartogs number of any X can be proved in Zermelo–Fraenkel set theory (ZF) without relying on the axiom of choice. The map taking X to α is sometimes called Hartogs's function. If X can be well-ordered, then |α| > |X|, since the cardinalities of two well-ordered sets are always comparable. In fact, |α| is the successor cardinal of |X|. Hartogs's function thus plays a role in constructing the aleph numbers, which are all the cardinal numbers of infinite well-orderable sets. If X cannot be well-ordered, then there cannot be an injection from X to α, so |α| > |X| cannot be true, and thus |α| is incomparable to |X|. Conversely, trichotomy for cardinal numbers (the statement that any two cardinal numbers are comparable) 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 (that is, without using the axiom of choice or the later-introduced replacement schema of ZF). 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 X, there exists an ordinal α such that | α | ≰ | X | {\displaystyle |\alpha |\not \leq |X|} ; that is, such that there is no injection from α to X as sets. As ordinals are well-ordered, this immediately implies the existence of a Hartogs number for any set X, namely the least ordinal with that property. Furthermore, the proof is constructive and yields the Hartogs number of X. Intuitively, the Hartogs number of X is exactly the order type of all ordinals β such that there is an injection from β to X, so it suffices to show that such β form a set (as opposed to a proper class). Importantly, an injection from β to X is also a bijection from β to a subset of X, 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 X 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 Goldrei 1996. Let α = { β ∈ Ord ∣ ∃ i : β ↪ X } {\displaystyle \alpha =\{\beta \in {\textrm {Ord}}\mid \exists i:\beta \hookrightarrow X\}} be the class of all ordinal numbers β for which an injective function exists from β into X. First, we verify that α is a set.
X × X is a set, as can be seen in the article Axiom of power set. The power set of X × X is a set, by the axiom of power set. 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. 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 (then 11 year old) well-ordering theorem (and, hence, the axiom of choice).
See also Successor cardinal Aleph number
References
