[Math] Hartogs number and the three power sets

axiom-of-choicelo.logicset-theory

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?

Best Answer

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

Related Question