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


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?

  • 1
    $\begingroup$ 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$. $\endgroup$ – François G. Dorais May 30 '12 at 12:05
  • $\begingroup$ In example 1, I think you mean to say that it is a strict inequality. $\endgroup$ – Joel David Hamkins May 30 '12 at 12:55
  • $\begingroup$ Joel, what do you mean? The first example was of a set that one power set already gives us exactly the Hartogs. $\endgroup$ – Asaf Karagila May 30 '12 at 12:57
  • $\begingroup$ 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. $\endgroup$ – Joel David Hamkins May 30 '12 at 13:04
  • $\begingroup$ By the way, the usual proof that $\aleph(X)$ exists is to form the set of equivalence classes of wellorderings of subsets of $X$ (coded by whatever means available). Then observe that this is wellordered in a natural way and use replacement to show that this wellordering is isomorphic to an ordinal. You appear to have skipped the final step in this process, which is very important when working in fragments of ZF with limited replacement. $\endgroup$ – François G. Dorais May 30 '12 at 13:28

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$.

  • $\begingroup$ Very interesting. I also keep running into $\kappa$-amorphous sets lately! $\endgroup$ – Asaf Karagila May 30 '12 at 14:21
  • $\begingroup$ 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 $\endgroup$ – Asaf Karagila May 30 '12 at 14:58
  • $\begingroup$ I wonder why the requirement that $\aleph_\alpha\neq\alpha$. I can understand the case of regular cardinals, but singular fixed points? $\endgroup$ – Asaf Karagila Oct 5 '12 at 22:04
  • $\begingroup$ 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))$. $\endgroup$ – Andrés E. Caicedo Oct 5 '12 at 22:13

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.