One of the most important constructions in ZF+$\lnot$AC is Hartogs number, defined as:

$$\aleph(X)=\min\lbrace\alpha:|\alpha|\nleq|X|\rbrace$$

We can prove that this ordinal always exists in the following way:

Consider every well-ordered subset of $X$, $\langle W,\prec\rangle$, for every $x\in W$ we can take $W_x=\lbrace y\in W: y\preceq x\rbrace$, then $W_x\subseteq W_y$ if and only if $x\preceq y$. This gives us an embedding of $(W,\prec)$ into $\mathcal{P}(X)$. We can therefore view $\langle W,\prec\rangle$ as an element of $\mathcal{P(P}(X))$. Now consider the equivalence relation of order isomorphism between the different subsets and their orders. Sending $\alpha<\aleph(X)$ to the equivalence class of all $\langle W,\prec\rangle\cong\langle \alpha,\in\rangle$ is an injective function from $\aleph(X)$ into $\mathcal{P(P(P}(X)))$.

So while $\aleph(X)$ is never smaller than $X$ it is always less or equal than *third* iteration of a power set.

**Example 1:** Suppose that $|\mathbb R|=\aleph_1$, then indeed $\aleph(\mathbb N)=2^{\aleph_0}=\aleph_1$ and we have the Hartogs is less or equal (in fact equal) to a single power set operation.

**Example 2:** Suppose that $D\subseteq\mathbb R$ is an infinite Dedekind-finite (e.g. Cohen's first model). We know that $\aleph(D)=\aleph_0$ for every infinite Dedekind-finite set. However since such $D$ can be mapped *onto* $\mathbb N$ we have that $\aleph_0<\mathcal P(D)$. We do not have equality since $\mathcal P(D)$ cannot be well-ordered so it cannot be equal to an ordinal.

**Example 3:** Suppose that $A$ is an amorphous set, that is an infinite set that every subset is finite or co-finite. It is immediate that $A$ is Dedekind-finite and therefore $\aleph(A)=\aleph_0$; however we also have that $\mathcal P(A)$ is Dedekind-finite, so we have to go another level and to only then we have $\aleph_0<\mathcal{P(P}(A))$.

The last example, using amorphous sets, is pretty much the "least well-orderable" set I can think of. In fact when looking for counterexamples amorphous sets are often a good place to begin with (they cannot be linearly ordered, for example).

Question:Is the bound ofthreeiterations of taking power sets really needed?

inequality. $\endgroup$ – Joel David Hamkins May 30 '12 at 12:552more comments