Hartogs number

A set A is said to be embeddable in another set B if there is a one-to-one function f:AB. For example, every subset of a set is embeddable in the set. In particular, is embeddable in every set. Clearly, given any set, there is an ordinalMathworldPlanetmathPlanetmath embeddable in it. On the other hand, is any set embeddable in an ordinal? If so, then the set is well-orderable (as it is equipollentMathworldPlanetmath to one), which is equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath to the well-ordering principle. In other words, in ZF, AC is equivalent to saying that every set is embeddable in an ordinal. Without AC, how much can one deduce? In 1915, Hartogs proved the following:

Theorem 1.

Given any set A, there is an ordinal α not embeddable in A.


Let α be the class of all ordinals embeddable in A. We want to show that α is in fact an ordinal, not embeddable in A. We have the following steps:

  • α is a set.

    Let be the subset of P(A), the powerset of A, consisting of all well-orderable subsets of A. For each element of B, let W(B) be the collectionMathworldPlanetmath of well-orderings on B. Each element of W(B) is a subset of B×B, so that W(B)P(B×B). For any RW(B), the well-ordered set (B,R) is order isomorphic to exactly one element β of α. Conversely, every βα, by definition, is embeddable in A, so equipollent to a subset B of A. We may well-order B via β, and this well-ordering RW(B). Therefore, there is a surjection from W:={(B,R)B,RW(B)} onto α. Since W is a set, so is its range (by the replacement axiom), which is just α.

  • α is an ordinal.

    Since α is a set consisting of ordinals, α is well-ordered. Now, suppose γβα. Since β is an ordinal, γβ. If ϕ:β(B,R) is an order isomorphism, then ϕ restricted to γ is an order isomorphism onto ϕ(γ)A, whose well-ordering is that induced by R. Therefore, γα, so α is a transitive set. This shows that α is an ordinal.

  • α is not embeddable in A.

    Otherwise, αα, contradicting the fact that an ordinal can never be a member of itself.

The proof is done within ZF, without the aid of the axiom of choiceMathworldPlanetmath.

Since the class of ordinals On is well-ordered, so is the subclass C of all ordinals not embeddable in A. The least element in C is called the Hartogs number of A, and is denoted by h(A).

In fact, the α constructed above is the Hartogs number of A, for if δ is another ordinal distinct from α that is not embeddable in A, then δα, so αδ by trichotomy.

Remark. For every set A, its Hartogs number h(A) is a cardinal numberMathworldPlanetmath: it is first of all an ordinal, so |h(A)|h(A), where is the orderingMathworldPlanetmath on the ordinals, and if |h(A)|<h(A) (meaning |h(A)|h(A)), then |h(A)| is embeddable in A. Since h(A) is equipollent to |h(A)|, h(A) is embeddable in A, contradicting the definition of h(A). Hence h(A)=|h(A)|. From the discussion so far, we see that h can be thought of as a class function from the class V of all sets onto the class Cn of all cardinal numbers. In addition, assuming AC, every set is well-orderable, so that h(A) is the least cardinal greater |A|, for every set A.

Title Hartogs number
Canonical name HartogsNumber
Date of creation 2013-03-22 18:49:48
Last modified on 2013-03-22 18:49:48
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 10
Author CWoo (3771)
Entry type Definition
Classification msc 03E10