nLab
Hartogs number

Contents

Idea

The Hartogs number of a cardinal number κ\kappa is the number of ways to well-order a set of cardinality at most κ\kappa.1

Assuming the axiom of choice, it is the smallest ordinal number whose cardinality is greater than κ\kappa and therefore the successor of κ\kappa as a cardinal number. But even without the axiom of choice, it makes sense and is often an effective substitute for such a successor.

Definition

We will define the Hartogs number as a functorial operation from sets to well-ordered sets. The operation on numbers is just a round-about way of talking about the same thing.

So let SS be a set. Without the axiom of choice (or more precisely, the well-ordering theorem), it may not be possible to well-order SS itself, but we can certainly well-order some subsets of SS. On the other hand, if we can well-order SS (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 SS, that is the subset of

A:𝒫S𝒫(A×A), \coprod_{A: \mathcal{P}S} \mathcal{P}(A \times A) ,

where \coprod indicates disjoint union and 𝒫\mathcal{P} indicates power set, consisting of those pairs (A,R)(A,R) such that RR 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-ordered by the general theory of ordinal numbers.

The Hartogs number of SS is this well-ordered set, the set of all order types of well-ordered subsets of SS. It is denoted (S)\aleph(S). If κ\kappa is the cardinality of SS, then let κ +\kappa^+ be the cardinality or ordinal rank (as desired) of the Hartogs number of SS; this is called the Hartogs number of κ\kappa.

There are other ways to encode (S)\aleph(S). A subset ASA \subseteq S with a well-ordering can be specified through the collection of its initial segments or down-sets, i.e., a suitable family of subsets of SS named by an element of PP(S)P P(S). Thus the set of well-orderings of subsets of SS can be defined as a suitable subset of PP(S)P P(S). Similarly, an equivalence class of such structures corresponding to a given order type is also definable as a subset of PP(S)P P(S), i.e., is named by a suitable element of PPP(S)P P P(S), so (S)\aleph(S) which is the set of such equivalence classes is definable as a subset of PPP(S)P P P(S).

All of the defining formulas in this description involve only bounded quantification, i.e., can be expressed in the language of BZC or in ETCS. The proof that (S)\aleph(S) is well-ordered (by existence of PP-coalgebra morphisms between representatives of order types) can be enacted in these theories without using the axiom of choice, hence the basic theory of (S)\aleph(S) can be carried out in BZ (bounded Zermelo set theory, without choice).

Properties

Theorem

There is no injection to SS from (S)\aleph(S).

This theorem is to Cantor's theorem as Burali-Forti's paradox is to Russell's paradox. This observation alone hints how the proof goes:

Proof

As observed before, (S)\aleph(S) is well-ordered. Suppose there were an injection i:(S)Si: \aleph(S) \to S; then ii gives a bijection of (S)\aleph(S) onto its image II. By transport of structure, II uniquely admits a well-ordering for which ii is an isomorphism of well-ordered sets. Using this well-ordering, there is an initial segment inclusion

j:I(S)j: I \hookrightarrow \aleph(S)

which takes xIx \in I to (the order type of) {yI:y<x}\{y \in I: y \lt x\}. Since there can be at most one initial segment inclusion between well-orders (cf. simulation), jj must coincide with the isomorphism i 1i^{-1}, which is onto. This means II itself, as an order type, must be of the form I={yI:y<x}I = \{y \in I: y \lt x\} for some xIx \in I, which in turn implies x<xx \lt x, a contradiction.

According to this theorem, using the usual ordering of cardinal numbers, κ +κ\kappa^+ \nleq \kappa. So if this \leq is a total order (a statement equivalent to the axiom of choice), we can say that κ +>κ\kappa^+ \gt \kappa.

Even without choice, however, we can say this: If α\alpha is an ordinal number such that |α|κ|\alpha| \nleq \kappa, then κ +α\kappa^+ \leq \alpha. (Notice that we've shifted our thinking of the Hartogs number from a cardinal to an ordinal.) That is, κ +\kappa^+ is the smallest ordinal number whose cardinal number is not at most κ\kappa. This doesn't use any form of choice except for excluded middle; we only need choice to conclude that |κ +|>κ|\kappa^+| \gt \kappa.

The axiom of choice also implies the well-ordering theorem, that any set can be well-ordered. Thus with choice, κ +\kappa^+ is (now as a cardinal again) the smallest cardinal number greater than κ\kappa; this explains the notation κ +\kappa^+.

GCH implies AC

In ZF (without C, the axiom of choice), a set XX can be well-ordered if there is an injection i:X(X)i: X \to \aleph(X), for any subset of a well-ordered set inherits a well-order. As an amusing illustration of this principle, we will prove an old result due to Sierpiński, following Gillman:

Theorem

If the generalized continuum hypothesis holds, then the axiom of choice holds, i.e., ZF + GCH implies AC.

(Recall the GCH as formulated in ZF: for infinite sets Y,ZY, Z, if |Y||Z||P(Y)||Y| \leq |Z| \leq |P(Y)|, then |Y|=|Z||Y| = |Z| or |Z|=|P(Y)||Z| = |P(Y)|, letting |Y||Y| denote the cardinality as usual and where |Y||Z||Y| \leq |Z| means there is a monomorphism YZY \to Z.)

Proof

In fact we will show that any set YY can be well-ordered, which implies AC (see the article Zorn's lemma). We start with a technical trick: any YY can be embedded in a set XX with the property |X|=|X+X||X| = |X + X| (consider for example X=P(+Y)X = P(\mathbb{N} + Y)), and then it suffices to well-order such XX, since we can then pull back the well-ordering along the embedding to well-order YY. Iterated power sets of XX also have that property.

Now, the Hartogs number (X)\aleph(X) can be constructed explicitly in ZF as a subset of the triple power set P 3(X)=PPP(X)P^3(X) = P P P(X). We will show for n{1,2,3}n \in \{1, 2, 3\} that under GCH, the hypothesis |(X)||P n(X)||\aleph(X)| \leq |P^n(X)|, true for n=3n = 3, leads to one of two conclusions:

  1. |X||(X)||X| \leq |\aleph(X)| (whence XX can be well-ordered), or

  2. |(X)||P n1(X)||\aleph(X)| \leq |P^{n-1}(X)|.

If we land in case 2, then we loop around and feed that conclusion back into the hypothesis and iterate. Iterating this, we cannot descend through case 2 all the way down to |(X)||P 0(X)|=|X||\aleph(X)| \leq |P^0(X)| = |X|, so after a few iterations we wind up in case 1 anyway: XX can be well-ordered.

To show this, we need a spot of cardinal arithmetic in ZF. First, we already observed that any P=P n(X)P = P^n(X) for n0n \geq 0 has the property |P|=|2P||P| = |2P|. Second, we claim

  • If P,AP, A are sets such that |P|=|2P||P| = |2P| and |A+P|=|2 P||A+P| = |2^P|, then |2 P||A||2^P| \leq |A|

whose ZF-proof we give in a moment. Granting the claim, let us continue. We have

|P n1(X)||(X)|+|P n1(X)|hypoth|P n(X)|+|P n1(X)|2|P n(X)|=|P n(X)||P^{n-1}(X)| \leq |\aleph(X)| + |P^{n-1}(X)| \stackrel{hypoth}{\leq} |P^n(X)| + |P^{n-1}(X)| \leq 2|P^n(X)| = |P^n(X)|

or just

|P n1(X)||(X)|+|P n1(X)||P n(X)|.|P^{n-1}(X)| \leq |\aleph(X)| + |P^{n-1}(X)| \leq |P^n(X)|.

By GCH, one of those two inequalities is an equality. If the first inequality is an equality, then we conclude |(X)||P n1(X)||\aleph(X)| \leq |P^{n-1}(X)|, which lands us in case 2. If the second inequality is an equality, then the claim applies and we conclude |P n(X)||(X)||P^n(X)| \leq |\aleph(X)|, in which case |X||P n(X)||(X)||X| \leq |P^n(X)| \leq |\aleph(X)| and we land in case 1.

So we are done except for the claim. Given bijections A+P2 PA + P \cong 2^P, P+PPP + P \cong P, let ff be the evident composite

PinclA+P2 P2 P+P2 P×2 Pπ 12 PP \stackrel{incl}{\to} A + P \cong 2^P \cong 2^{P + P} \cong 2^P \times 2^P \stackrel{\pi_1}{\to} 2^P

where π 1\pi_1 denotes first projection. Let CC be an element not in the image of ff, e.g., C={xP:xf(x)}C = \{x \in P: x \notin f(x)\} (Cantor's theorem). It follows that under the bijection A+P2 P×2 PA + P \cong 2^P \times 2^P, those elements of A+PA + P that map to elements of the fiber π 1 1({C})\pi_1^{-1}(\{C\}) can only belong to the summand AA. Thus it is a subset of AA that maps bijectively onto π 1 1({C})2 P\pi_1^{-1}(\{C\}) \cong 2^P, and this proves |2 P||A||2^P| \leq |A|.

Equivalent forms of AC

Methods somewhat similar to those used to prove GCH implies AC can be used to establish equivalent forms of AC.

Theorem

(Tarski) Over ZF (or ETCS), the axiom of choice holds iff every infinite set YY can be put into bijection with its square: Y 2YY^2 \cong Y.

Proof

The more interesting direction is the “if”, so we assume every infinite set can be put into bijection with its square.

It suffices to prove that every XX can be well-ordered. WLOG we prove this for (Dedekind) infinite XX, since every XX embeds in a Dedekind infinite set (such as X+X + \mathbb{N}), and we can pull back a well-order on the latter along such an embedding to one on the former.

For infinite XX, let YY be the disjoint union X+(X)X + \aleph(X), and let ϕ:Y×YY\phi: Y \times Y \to Y be a bijection. We claim that for all xXx \in X, there exist α,β(X)\alpha, \beta \in \aleph(X) such that ϕ(x,α)=β\phi(x, \alpha) = \beta. If that were not true, then there would exist xXx \in X such that for all α(X)\alpha \in \aleph(X) we have ϕ(x,α)(X)\phi(x, \alpha) \notin \aleph(X), or in other words for all α(X)\alpha \in \aleph(X) we have ϕ(x,α)X\phi(x, \alpha) \in X, so that ϕ(x,)\phi(x, -) defines an injection (X)X\aleph(X) \rightarrowtail X. This is impossible.

By the claim, for each xXx \in X there is a least pair (α x,β x)(X) 2(\alpha_x, \beta_x) \in \aleph(X)^2, considered in lexicographic order, such that ϕ(x,α x)=β x\phi(x, \alpha_x) = \beta_x. This assignment x(α x,β x)x \mapsto (\alpha_x, \beta_x) defines an embedding X(X) 2X \to \aleph(X)^2 into a well-ordered set, so that XX inherits a well-order by restriction along the embedding, and we are done.

A very similar method establishes the following claim.

Proposition

Over ZF, AC is equivalent to the statement that every inhabited set admits a group structure.

Proof

Every inhabited finite set admits a cyclic group structure, and under AC any infinite set can be put in bijection with the collection of its finite subsets, which forms a group under symmetric difference.

Conversely, suppose Y=X+(X)Y = X + \aleph(X) admits a group structure. Then for every xXx \in X, there exist α,β(X)\alpha, \beta \in \aleph(X) such that xα=βx\alpha = \beta. For if that were not true, then there exists xXx \in X such that for all α(X)\alpha \in \aleph(X), we have xα(X)x \alpha \notin \aleph(X), i.e., for all α(X)\alpha \in \aleph(X) we have xαXx\alpha \in X, which implies left multiplication by xx defines an injection (X)X\aleph(X) \rightarrowtail X, contradiction.

So for each xXx \in X, there exists a least (α x,β x)(X) 2(\alpha_x, \beta_x) \in \aleph(X)^2 in lexicographic order such that xα x=β xx \alpha_x = \beta_x. This again defines an embedding x(α x,β x)x \mapsto (\alpha_x, \beta_x) into a well-ordered set (X) 2\aleph(X)^2, and we are done.

Examples

For nn a natural number regarded as the cardinal number of a finite set, n +n^+ is the usual successor n+1n + 1. This result uses excluded middle; else we get the plump successor of nn, which may be rather larger.

For 0\aleph_0 the cardinality of the set of all natural numbers, the Hartogs number 0 +=ω 1\aleph_0^+ = \omega_1 is the smallest uncountable ordinal. Assuming the axiom of choice (countable choice and excluded middle are enough), we have 0 += 1\aleph_0^+ = \aleph_1 as a cardinal.

In general, we get a sequence ω α\omega_\alpha 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 |ω α|= α|\omega_\alpha| = \aleph_\alpha. (Actually, there's no real need to begin with infinite cardinals; if we started with ω 0=0\omega_0 = 0 instead of ω 0=N\omega_0 = \mathbf{N} and 0=0\aleph_0 = 0 instead of 0=|N|\aleph_0 = |\mathbf{N}|, then absolutely every cardinality or well-orderable cardinality would appear.)

References

  • Friedrich Hartogs, Über das Problem der Wohlordnung , Math. Ann. 76 no.4 (1915) pp.438-443. (gdz)

  • Radu Diaconescu?, On Comparability in a Topos , Proc. AMS 98 no.3 (1986) pp.389-393. (pdf)

  • Leonard Gillman, Two Classical Surprises Concerning the Axiom of Choice and the Continuum Hypothesis, Amer. Math. Monthly 109 (June-July 2002), 544-553. (pdf)

The last section of Gillman’s paper is based on Sierpiński’s 1947 proof which may be found here.


  1. The spelling Hartogs’ number, or even Hartog’s number, is also in use. The latter based presumably on a misapprehension since the concept was originally proposed by the German mathematician Friedrich Hartogs (1874-1943) in 1915.

Last revised on August 10, 2018 at 08:12:41. See the history of this page for a list of all contributions to it.