8
$\begingroup$

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

$\endgroup$
17
  • $\begingroup$ 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. $\endgroup$ – tomasz Jun 19 '13 at 1:56
  • 1
    $\begingroup$ 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)$. $\endgroup$ – Andrés E. Caicedo Jun 19 '13 at 2:09
  • 1
    $\begingroup$ @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.) $\endgroup$ – Andrés E. Caicedo Jun 19 '13 at 2:17
  • 2
    $\begingroup$ Mario: This is definitely not "elementary". (And you may want to fix the typo of the missing power-set in line 3.) $\endgroup$ – Andrés E. Caicedo Jun 19 '13 at 3:05
  • 1
    $\begingroup$ @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)$. $\endgroup$ – Andrés E. Caicedo Jun 19 '13 at 6:56
3
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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)$? $\endgroup$ – Andrés E. Caicedo Jun 20 '13 at 16:23
  • $\begingroup$ @Andres: $\alpha=3$? Recall my MO question (that you answered) about Hartogs and the Three Power Sets! :-) $\endgroup$ – Asaf Karagila Jun 20 '13 at 16:25
  • $\begingroup$ 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)$? $\endgroup$ – Andrés E. Caicedo Jun 20 '13 at 16:27
  • 1
    $\begingroup$ 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)$? $\endgroup$ – Andrés E. Caicedo Jun 20 '13 at 16:37
  • $\begingroup$ @Andres: I'd suspect that the answer should be an equally easy of a "no". Maybe if I'll drink a lot tonight, the answer will be apparent in the morning, like this one was! $\endgroup$ – Asaf Karagila Jun 20 '13 at 17:30

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.