# If $B\not\prec A$, does $A\preceq {\cal P}(B)$ or $A\preceq {\cal P}{\cal P}(B)$, etc in ${\sf ZF}$?

I've heard it said that theorems based on choice are also available in ZF "a few powersets away", and I think this is one of them, but I'm not sure how to prove it. (I'm also interested to hear of other formulas of this type. A special case: If $A\not\prec\omega$, then $\omega\preceq{\cal PP}(A)$, i.e. the double powerset of a Dedekind-finite set is infinite. This one I can prove though.)

Edit: Just to be clear, we say $A\preceq B$ if there exists an injection $f:A\to B$, and $A\prec B$ if $A\preceq B$ and $B \mathrel{\diagup\hskip{-1em}\preceq} A$.

To make the statement precise, what I am asking is if there exists an $n\in\omega$ such that

$${\sf ZF}\vdash \forall A,B[A\prec B\vee B\prec{\cal P}^n(A)],$$

and if so, what is the smallest such $n$. Andres' comment below suggests another, much weaker generalization: is the statement $\exists\alpha\in{\sf On}\,\forall A,B\,(A\prec B\vee B\prec{\cal P}^\alpha(A))$ provable? Here ${\cal P}^\alpha(A)$ is defined by transfinite recursion: ${\cal P}^0(A)=A$, ${\cal P}^{\alpha+1}(A)={\cal P(P}^\alpha(A))$, and ${\cal P}^\alpha(A)=\bigcup_{\beta<\alpha}{\cal P}^\beta(A)$ for limit ordinals $\alpha$.

• What do you mean by $\prec,\preceq$ exactly? I'm guessing the existence of an injection, but you may want to state that in clear terms. – tomasz Jun 19 '13 at 1:56
• Mario: $\omega\prec\mathcal P^2(A)$, but $\mathcal P(A)$ could still be Dedekind finite. The neat thing is that, even if $\omega\not\prec\mathcal P(A)$, we anyway have $\mathcal P(\omega)\preceq\mathcal P^2(A)$. – Andrés E. Caicedo Jun 19 '13 at 2:09
• @user14111 Yes, since $\preceq$ is a partial order, I suppose it would be natural to have $A\not\prec B$ literally mean that either $A$ does not inject into $B$, or else $A\sim B$. Sure, we should probably use $A\not\preceq B$, to avoid confusion. (And yes, I think $\prec$, etc, is standard notation.) – Andrés E. Caicedo Jun 19 '13 at 2:17
• Mario: This is definitely not "elementary". (And you may want to fix the typo of the missing power-set in line 3.) – Andrés E. Caicedo Jun 19 '13 at 3:05
• @AsafKaragila I would be happy with having a fixed $\alpha$, even if infinite, such that $B\not\preceq A$ gives $A\preceq\mathcal P^\alpha(B)$. – Andrés E. Caicedo Jun 19 '13 at 6:56

The answer is negative in $\sf ZF+\lnot AC$.
Let $A$ be a set which cannot be well-ordered, pick $\alpha\in\sf Ord$, and let $B=\aleph(\mathcal P^\alpha(A))$, then we have that $A$ and $B$ are incomparable, but also $\mathcal P^\alpha(A)$ and $B$ are incomparable.
• Yes, OK. I figured there was something like this. Let's change the question: Can we find an $\alpha$ that works whenever $A$ is non-well-orderable, and $B=\aleph(A)$? – Andrés E. Caicedo Jun 20 '13 at 16:23
• @Andres: $\alpha=3$? Recall my MO question (that you answered) about Hartogs and the Three Power Sets! :-) – Asaf Karagila Jun 20 '13 at 16:25
• Yes, that's not what I meant, sorry. I meant: Is there $\alpha$ such that for any such $A,B=\aleph(A)$, you can embed $A$ into $\mathcal P^\alpha(B)$? – Andrés E. Caicedo Jun 20 '13 at 16:27
• Also, the original question should be symmetric: Is there an $\alpha$ such that, for any incomparable $A,B$, either $A\preceq\mathcal P^\alpha(B)$, or $B\preceq\mathcal P^\alpha(A)$? – Andrés E. Caicedo Jun 20 '13 at 16:37