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 of *three* iterations of taking power sets really needed? 
> 
> 
> 



Hartogs number and the three power sets
Hi Asaf,


I thought about this a while ago. Of course, the question had been asked and solved before. Digging through the FOM archives for Spring 2009, I found (April 28, 2009; I fixed a typo in what follows):



> 
> In a message dated Jan. 28, I asked whether Sierpinski's ZF result that
>  $\aleph(X) < \aleph({\mathcal P}({\mathcal P}({\mathcal P}(X))))$ for all $X$, 
>  could be improved by replacing the triple power set with a double power 
>  set.
> 
> 
> In a follow up dated Feb. 2, I indicated that one can, provided that
>  $\aleph(X)$ is not $\aleph\_\alpha$ for some infinite limit ordinal
>  $\alpha < \aleph\_\alpha$.
> 
> 
> I recently found a reference that settles the other case, and wanted to 
>  give an update for those curious about the question. In Theorem 11 of John 
>  L. Hickman, "$\Lambda$-minimal lattices", Zeitschr. f. math. Logik und 
>  Grundlagen d. Math., 26 (1980), 181-191, it is shown that for any such 
>  $\alpha$, it is consistent to have an $X$ with
>  $\aleph(X) = \aleph\_\alpha = \aleph({\mathcal P}({\mathcal P}(X)))$.
> 
> 
> 


So, yes, the triple power set is best possible in ZF. (If $\Lambda$ is an aleph (a well-ordered cardinal), a set $X$ is said to be a *$\Lambda$-set* iff $\aleph(X)=\Lambda$, and yet $X$ cannot be well ordered. In that case, $X$ is *$\Lambda$-minimal* iff for every $Y\subseteq X$, either ${}|Y|<\lambda$ or ${}|X\setminus Y|<\Lambda$.) 


Hickman's argument uses Fraenkel-Mostowski models (and the Jech-Sochor embedding theorem).


See also the appendix to [these notes](http://caicedoteaching.wordpress.com/2009/02/02/580-some-choiceless-results-5/) for the argument that two power sets suffice unless $\aleph(X)=\aleph\_\alpha$ for some infinite limit $\alpha < \aleph\_\alpha$.


