# Hartogs number and the three power sets

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?

-
Your choice of ordered pairs increases rank by 2, so you only have $\langle a, b \rangle \subseteq \mathcal{P}(X)$ and $X \times X \subseteq \mathcal{P}(\mathcal{P}(X))$. However, the three powerset bound is still correct using a different coding of wellorderings, namely code the wellordering $(W,{\prec})$ with $W \subseteq X$, using the inclusion chain $\lbrace W_x : x \in W\rbrace \subseteq \mathcal{P}(X)$, where $W_x = \lbrace w \in W : w \preceq x \rbrace$. – François G. Dorais May 30 '12 at 12:05
Francois: Thanks. I will correct. – Asaf Karagila May 30 '12 at 12:44
In example 1, I think you mean to say that it is a strict inequality. – Joel David Hamkins May 30 '12 at 12:55
Joel, what do you mean? The first example was of a set that one power set already gives us exactly the Hartogs. – Asaf Karagila May 30 '12 at 12:57
Oh, I had though that you meant it was strictly less than three power sets, which gives some evidence that one might hope always to do with less than three. – Joel David Hamkins May 30 '12 at 13:04

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 for the argument that two power sets suffice unless $\aleph(X)=\aleph_\alpha$ for some infinite limit $\alpha < \aleph_\alpha$.

-
Very interesting. I also keep running into $\kappa$-amorphous sets lately! – Asaf Karagila May 30 '12 at 14:21
It took me quite some effort, but I found an online link to the article, the DOI is 10.1002/malq.19800261004 and the link is dx.doi.org/10.1002/malq.19800261004 – Asaf Karagila May 30 '12 at 14:58
I wonder why the requirement that $\aleph_\alpha\neq\alpha$. I can understand the case of regular cardinals, but singular fixed points? – Asaf Karagila Oct 5 '12 at 22:04
Hi Asaf: If $\aleph_\alpha=\alpha$, then we can map a well-orderable subset $Y$ of $X$ to $\beta$ if $|Y|=\aleph_\beta$. This is a surjection from $\mathcal P(X)$ onto $\alpha$, so $2^{\aleph_\alpha}$ injects into $\mathcal P(\mathcal P(X))$. – Andrés Caicedo Oct 5 '12 at 22:13