Hartogs number in nLab

Context

Foundations

• Idea
• Definition
• Properties
• GCH implies AC
• Equivalent forms of AC
• Examples
• Related page
• Related entries
• References

Theorem

There is no injection ℵ(S)→S\aleph(S) \to S.

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 x∈Ix \in I to (the order type of) I x={y∈I:y<x}I_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, representing its isomorphism class [I]∈ℵ(S)[I] \in \aleph(S), is order-isomorphic to a well-ordered set I xI_x for some x∈Ix \in I, say by ϕ:I x≅I\phi: I_x \cong I. Again, by uniqueness of initial segment inclusions, ϕ\phi coincides with the inclusion I x↪II_x \hookrightarrow I, so this inclusion is onto and so I x=II_x = I. This in turn implies x<xx \lt x, a contradiction.

Proof

Define a relation RR from κ +\kappa^+ to α\alpha where xRyx R y if κ x +\kappa_x^+ and α y\alpha_y are isomorphic as well-ordered sets. Then RR defines a monic partial function whose domain dom(R)\dom(R) is an initial segment of κ +\kappa^+. If dom(R)=κ +\dom(R) = \kappa^+, then RR witnesses κ +≤α\kappa^+ \leq \alpha. Otherwise there is a least xx such that the restriction of RR to κ x +\kappa_x^+ has no upper bound in α\alpha (implying dom(R)=κ x +\dom(R) = \kappa_x^+). By downward closure, it follows that RR is onto, hence R opR^{op} witnesses α≤κ x +\alpha \leq \kappa_x^+, where the codomain is isomorphic to a well-ordered subset of κ\kappa by definition of κ +\kappa^+, and contradicting |α|≰κ|\alpha| \nleq \kappa.

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 n−1(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 n≥0n \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 n−1(X)|≤|ℵ(X)|+|P n−1(X)|≤hypoth|P n(X)|+|P n−1(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 n−1(X)|≤|ℵ(X)|+|P n−1(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 n−1(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+P≅2 PA + P \cong 2^P, P+P≅PP + P \cong P, let ff be the evident composite

P→inclA+P≅2 P≅2 P+P≅2 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={x∈P:x∉f(x)}C = \{x \in P: x \notin f(x)\} (Cantor's theorem). It follows that under the bijection A+P≅2 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|.

Theorem

(Tarski) Over ZF (or ETCS without choice), the axiom of choice holds iff every infinite set YY can be put into bijection with its square: Y 2≅YY^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×Y→Y\phi: Y \times Y \to Y be a bijection. We claim that for all x∈Xx \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 x∈Xx \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 x∈Xx \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.

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 x∈Xx \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 x∈Xx \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 x∈Xx \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.