13
$\begingroup$

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?

$\endgroup$
7
  • 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$ May 30, 2012 at 12:05
  • $\begingroup$ In example 1, I think you mean to say that it is a strict inequality. $\endgroup$ May 30, 2012 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, 2012 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$ May 30, 2012 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$ May 30, 2012 at 13:28

1 Answer 1

15
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Very interesting. I also keep running into $\kappa$-amorphous sets lately! $\endgroup$
    – Asaf Karagila
    May 30, 2012 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, 2012 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, 2012 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$ Oct 5, 2012 at 22:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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