Proof

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

which takes $x \in I$ to (the order type of) $I_x = \{y \in I: y \lt x\}$. Since there can be at most one initial segment inclusion between well-orders (cf. simulation), $j$ must coincide with the isomorphism $i^{-1}$, which is onto. This means $I$, representing its isomorphism class $[I] \in \aleph(S)$, is order-isomorphic to a well-ordered set $I_x$ for some $x \in I$, say by $\phi: I_x \cong I$. Again, by uniqueness of initial segment inclusions, $\phi$ coincides with the inclusion $I_x \hookrightarrow I$, so this inclusion is onto and so $I_x = I$. This in turn implies $x \lt x$, a contradiction.

Proof

Define a relation $R$ from $\kappa^+$ to $\alpha$ where $x R y$ if $\kappa_x^+$ and $\alpha_y$ are isomorphic as well-ordered sets. Then $R$ defines a monic partial function whose domain $\dom(R)$ is an initial segment of $\kappa^+$. If $\dom(R) = \kappa^+$, then $R$ witnesses $\kappa^+ \leq \alpha$. Otherwise there is a least $x$ such that the restriction of $R$ to $\kappa_x^+$ has no upper bound in $\alpha$ (implying $\dom(R) = \kappa_x^+$). By downward closure, it follows that $R$ is onto, hence $R^{op}$ witnesses $\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 $Y$ can be well-ordered, which implies AC (see the article Zorn's lemma). We start with a technical trick: any $Y$ can be embedded in a set $X$ with the property $|X| = |X + X|$ (consider for example $X = P(\mathbb{N} + Y)$), and then it suffices to well-order such $X$, since we can then pull back the well-ordering along the embedding to well-order $Y$. Iterated power sets of $X$ also have that property.

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

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

2. $|\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 $|\aleph(X)| \leq |P^0(X)| = |X|$, so after a few iterations we wind up in case 1 anyway: $X$ 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)$ for $n \geq 0$ has the property $|P| = |2P|$. Second, we claim

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

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

or just

By GCH, one of those two inequalities is an equality. If the first inequality is an equality, then we conclude $|\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)| \leq |\aleph(X)|$, in which case $|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 \cong 2^P$, $P + P \cong P$, let $f$ be the evident composite

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

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 $X$ can be well-ordered. WLOG we prove this for (Dedekind) infinite $X$, since every $X$ embeds in a Dedekind infinite set (such as $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 $X$, let $Y$ be the disjoint union $X + \aleph(X)$, and let $\phi: Y \times Y \to Y$ be a bijection. We claim that for all $x \in X$, there exist $\alpha, \beta \in \aleph(X)$ such that $\phi(x, \alpha) = \beta$. If that were not true, then there would exist $x \in X$ such that for all $\alpha \in \aleph(X)$ we have $\phi(x, \alpha) \notin \aleph(X)$, or in other words for all $\alpha \in \aleph(X)$ we have $\phi(x, \alpha) \in X$, so that $\phi(x, -)$ defines an injection $\aleph(X) \rightarrowtail X$. This is impossible.

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

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 + \aleph(X)$ admits a group structure. Then for every $x \in X$, there exist $\alpha, \beta \in \aleph(X)$ such that $x\alpha = \beta$. For if that were not true, then there exists $x \in X$ such that for all $\alpha \in \aleph(X)$, we have $x \alpha \notin \aleph(X)$, i.e., for all $\alpha \in \aleph(X)$ we have $x\alpha \in X$, which implies left multiplication by $x$ defines an injection $\aleph(X) \rightarrowtail X$, contradiction.

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