There is no surjective function from a set in the Hartogs number of its power set

Question

I'm trying to prove an equivalent state of the Axiom of Choice :

Given two non-empty sets, there is a surjective function from one of them into the other one.

If we prove that for any non-empty set $X$ cannot exist a surjective function from $X$ onto the Hartogs number $ H(\mathcal{P}(X))$, then we can invert the other function the statement gives us and we obtain a well-order on $X$.

Is what I want to prove true without AC? It seems reasonable to me.

Answer 1

In short: Yes.

I will give a somewhat broad answer that includes some things that you probably already know, but I introduce the concepts anyway for some uniformity.

The following are equivalent:

1. The axiom of choice.
2. For all $X,Y$, either $|X|\leq|Y|$ or $|Y|\leq|X|$, where $|X|\leq|Y|$ means that there is an injection $X\to Y$.
3. For all $X,Y$, either $|X|\leq^*|Y|$ or $|Y|\leq^*|X|$, where $|X|\leq^*|Y|$ means that there is a surjection $Y\to X$.

(This is standard notation).

For any $X$, the Hartogs number of $X$, $H(X)$ is the least ordinal $\alpha$ such that there is no injection $\alpha\to X$. The Lindenbaum number of $X$, $H^*(X)$ is the least ordinal $\alpha$ such that there is no surjection $X\to\alpha$.

(I have not seen this notation, I would say $\aleph(X)$ and $\aleph^*(X)$ for the Hartogs/Lindenbaum number of $X$).

With some thinking, we can see that $H(X)$ and $H^*(X)$ are always cardinal numbers (if they exist), and $\mathsf{ZF}\vdash(\forall X)H(X)\leq H^*(X)$ (if they exist).

As you seem to allude to, the proof that (2) implies (1) follows proving that Hartogs numbers exist, and to prove that (3) implies (1) you can follow a similar path by proving that Lindenbaum numbers exist (this is, in essense, what you have asked in your question).

One strategy would be to let $Z=\{\alpha\mid|\alpha|\leq^*|X|\}$. We note that $Z$ is an initial segment of the ordinals, and if we can prove that $Z$ is not all of the ordinals then there must be $\alpha$ such that $|\alpha|\nleq^*|X|$. Your strategy is to show that $|H(P(X))|\nleq^*|X|$, and this will in fact work. Now let us prove this.

Suppose that $|\alpha|\leq^*|X|$. Then we wish to show that $|\alpha|\leq |P(X)|$. If we do this, then we see that essentially by definition $|H(P(X))|\nleq^*|X|$. However, $|Y|\leq^*|X|\implies|Y|\leq|P(X)|$ is true for all sets! Let $f\colon X\to Y$ be a surjection. Then define $g\colon Y\to P(X)$ by $g(y)=f^{-1}(y)$. Since $f$ is a surjection, for all $y\in Y$, $g(y)\neq\emptyset$, and therefore if $g(y)=g(y')$ we must have $x\in g(y)$, so $y=f(x)=y'$. Hence, $g$ is an injection.