We work in the set theory NBG with the axiom of (local choice but without global (class) choice. For every class A P(A) is the class of all sets x included in the class A.

We know that P(A) is a set iff A is a set and a proper class iff P(A) is a proper class. We also know that if A is a set there is no bijection between A and P(A), and that P(P(V))=V, where V is the universal class. It is clear that if there is a bijection between A and V, then there is a bijection between A and P(A).

Question: Is it true that if there is a bijection between A and P(A) then there is a bijection between A and V?

This question is not interesting under global choice, where all proper classes are bijective.


Yes, this is provable in NBG. To see this, let $F$ be a one-one function from $\mathcal P(A)$ into $A$. By transfinite recursion on $\in$, we define a function $G$ from $V$ to $A$ such that $G(x) = F(G[x])$. A simple induction then establishes that $G$ is one-one.

  • $\begingroup$ Dear Sam, let me thank you very much, first to have remarked that Asaf's answer was not sufficient and moreover to give a definite answer to my question. As I understand it, suppose G(α) is a function from V(α) into A and let X∈ V(α+1)/V(α). $\endgroup$ Dec 6 '14 at 15:51
  • $\begingroup$ oops. I continue. We have that y∈x implies y∈V(α), so that G[x]={G(y)/y∈x} is a well-defined set with G[x]⊆V(α)⊆P(A). $\endgroup$ Dec 6 '14 at 15:58
  • $\begingroup$ @GérardLang That's right; we can also recursively define an ordinal sequence of functions -- so that $G(\alpha)$ is a one-one function from $V_\alpha$ into $A$, $G(\alpha+1)$ extends $G(\alpha)$ to $V_{\alpha+1}$ uniquely in the way I suggest, and $G(\lambda) = \bigcup_{\alpha<\lambda} G(\alpha)$ for $\lambda$ a limit. A simple induction then shows that each $G(\alpha)$ is one-one, and thus that $\bigcup_{\alpha\in On} G(\alpha)$ is a one-one function from $V$ into $A$ as required. $\endgroup$ Dec 6 '14 at 19:22

It suffices to show that for $A=\sf Ord$. Since in that case global choice holds and the rest follows.

Fix a pairing function for ordinals, namely a bijection between $\sf Ord$ and $\sf Ord\times Ord$. Now given a bijection between $\sf Ord$ and $\cal P\sf (Ord)$, pick for each $\alpha$ the least $X_\alpha\in\cal P\sf (Ord)$ such that $X_\alpha$ encodes the structure $(V_\alpha,\in)$, and $X_\alpha$ is disjoint from $\bigcup_{\beta<\alpha} X_\beta$. Namely a subset of the ordinals which, when translated using the pairing function, gives us a structure which is extensional and well-founded, and its transitive collapse is $V_\alpha$.

Now we have a bijection between the ordinals and the universe, defined by the following, given $x$ of rank $\alpha$, $x$ is mapped to the unique $\eta\in X_\alpha$ which encodes $x$.

(Alternatively, you don't need to require that the $X_\alpha$'s are disjoint, and this defines a surjection from $\sf Ord$ onto $V$ in a similar way.)

  • $\begingroup$ Dear Asaf, Thank you very much for this nice answer. If I correctly understand, the negation of the axiom of global choice is equivalent with the existence of a proper class A such that A is bijective with P(A) and not bijective with V. And by the model built by Ali Enayat, where On, P(On) and P(P(On)) are not bijective, it is possible that such A is neither bijective with On, nor with P(On). Would it be possible that the class W defined by JD Hamkins be such a class ? $\endgroup$ Dec 6 '14 at 11:08
  • $\begingroup$ You just need to notice that $\mathcal P\sf (Ord)$ can always be linearly ordered. In a model where there is a class which cannot be linearly ordered, this class cannot be put into bijection with $\mathcal P\sf (Ord)$; and if this class is such that there is no injection from $\sf Ord$ into it, then this class cannot be put into bijection with $V$ either. Joel Hamkins suggested such model in an answer to a question of mine, to which I linked in one of your recent questions. $\endgroup$
    – Asaf Karagila
    Dec 6 '14 at 11:28
  • 2
    $\begingroup$ @AsafKaragila Sorry to be dense, but how does the general claim (for all $A$, if $A$ is bijective with $\mathcal P(A)$, then $A$ is bijective with $V$) follow from the instance $A = On$ (if $On$ is bijective with $\mathcal P(On)$, then $On$ is bijective with $V$)? $\endgroup$ Dec 6 '14 at 13:49
  • 1
    $\begingroup$ @Gerard: As Sam points out, I misread the question. Please unaccept my answer. I will leave it for a while, if only to keep the comments below it visible. $\endgroup$
    – Asaf Karagila
    Dec 6 '14 at 15:08
  • 3
    $\begingroup$ @Gerard: I should have been more careful. I read the question as asking about "Every class $W$ has a bijection with $\mathcal P(W)$", which is what my answer shows. $\endgroup$
    – Asaf Karagila
    Dec 6 '14 at 15:40

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.