You are here
HomeHartogs number
Primary tabs
Hartogs number
A set $A$ is said to be embeddable in another set $B$ if there is a onetoone function $f:A\to B$. For example, every subset of a set is embeddable in the set. In particular, $\varnothing$ is embeddable in every set. Clearly, given any set, there is an ordinal embeddable in it. On the other hand, is any set embeddable in an ordinal? If so, then the set is wellorderable (as it is equipollent to one), which is equivalent to the wellordering 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 $\alpha$ not embeddable in $A$.
Proof.
Let $\alpha$ be the class of all ordinals embeddable in $A$. We want to show that $\alpha$ is in fact an ordinal, not embeddable in $A$. We have the following steps:

$\alpha$ is a set.
Let $\mathcal{B}$ be the subset of $P(A)$, the powerset of $A$, consisting of all wellorderable subsets of $A$. For each element of $B\in\mathcal{B}$, let $W(B)$ be the collection of wellorderings on $B$. Each element of $W(B)$ is a subset of $B\times B$, so that $W(B)\in P(B\times B)$. For any $R\in W(B)$, the wellordered set $(B,R)$ is order isomorphic to exactly one element $\beta$ of $\alpha$. Conversely, every $\beta\in\alpha$, by definition, is embeddable in $A$, so equipollent to a subset $B$ of $A$. We may wellorder $B$ via $\beta$, and this wellordering $R\in W(B)$. Therefore, there is a surjection from $W:=\{(B,R)\mid B\in\mathcal{B},R\in W(B)\}$ onto $\alpha$. Since $W$ is a set, so is its range (by the replacement axiom), which is just $\alpha$.

$\alpha$ is an ordinal.
Since $\alpha$ is a set consisting of ordinals, $\alpha$ is wellordered. Now, suppose $\gamma\in\beta\in\alpha$. Since $\beta$ is an ordinal, $\gamma\subseteq\beta$. If $\phi:\beta\to(B,R)$ is an order isomorphism, then $\phi$ restricted to $\gamma$ is an order isomorphism onto $\phi(\gamma)\subseteq A$, whose wellordering is that induced by $R$. Therefore, $\gamma\in\alpha$, so $\alpha$ is a transitive set. This shows that $\alpha$ is an ordinal.

$\alpha$ is not embeddable in $A$.
Otherwise, $\alpha\in\alpha$, 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 choice.
Since the class of ordinals On is wellordered, 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 $\alpha$ constructed above is the Hartogs number of $A$, for if $\delta$ is another ordinal distinct from $\alpha$ that is not embeddable in $A$, then $\delta\notin\alpha$, so $\alpha\in\delta$ by trichotomy.
Remark. For every set $A$, its Hartogs number $h(A)$ is a cardinal number: it is first of all an ordinal, so $h(A)\leq h(A)$, where $\leq$ is the ordering on the ordinals, and if $h(A)<h(A)$ (meaning $h(A)\in 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 wellorderable, so that $h(A)$ is the least cardinal greater $A$, for every set $A$.
Mathematics Subject Classification
03E10 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections