Enderton defines the rank of a set $A$ to be the least ordinal $\alpha$ such that $A \subseteq V_{\alpha}$ (equivalently, $A \in V_{\alpha^+}$). He the derives the following identity: $rank(A) = \bigcup \{ (rank(x))^+ : x \in A \}$ for all sets $A$.

In Exercise 30 of Chapter 7, the reader is asked to prove several identities involving rank. For instance, that $rank\{a,b\} = max(rank(a),rank(b))^+$. I am having trouble proving the second identity, that $rank(\wp(x)) = rank(x)^+$ for all sets $x$. I am not sure whether I am missing some elementary identity that would let me prove the identity, or whether I am misunderstanding the definition of rank.

Clearly, $z \in rank(\wp(x)) \Leftrightarrow (\exists y)(y \subseteq x \wedge (z \in rank(y) \vee z = rank(y))$. On the other hand $z \in (rank(x))^+ \Leftrightarrow (\exists y)(y \in x \wedge z \in (rank(y))^+) \vee z = rank(x)$. I'm not sure why the first statement should imply the second, and conversely, however.


I assume $\alpha^+$ just means $\alpha+1$, the immediate successor of $\alpha$. (Typically, we use $\alpha^+$ for a different notion.)

The point is this: Suppose that $x\subseteq y$. Then $rank(x)\le rank(y)$. This is immediate from the identity at the end of your first paragraph. It follows that all subsets of $x$ have rank at most $rank(x)$. Say $\beta$ is least such that $x\in V_\beta$. Then ${\mathcal P}(x)\subseteq V_\beta$ (since all subsets of $x$ are also elements of $V_\beta$) and therefore ${\mathcal P}(x)\in V_{\beta+1}$. This shows that $rank({\mathcal P}(x))\le rank(x)^+$.

For the converse: If $rank({\mathcal P}(x))< rank(x)^+$ then $rank({\mathcal P}(x))\le rank(x)$. Use the identity at the end of your first paragraph to conclude that all elements of ${\mathcal P}(x)$ have rank strictly less than $rank(x)$. But then $x$ itself would have rank strictly less than $rank(x)$. This is a contradiction, and we are done.

| cite | improve this answer | |
  • $\begingroup$ Thank you, Andres. I was certainly approaching this problem incorrectly. Your explanation is very clear, and the method helpful. $\endgroup$ – danportin May 27 '11 at 6:46
  • $\begingroup$ Out of curiosity, what does $\alpha^+$ mean? My lecturer used $\alpha^+$ for the successor of $\alpha$ as well... $\endgroup$ – Zhen Lin May 27 '11 at 9:00
  • $\begingroup$ The standard notation is that if $\kappa$ is an infinite cardinal (i.e., an infinite ordinal that is not in bijection with any smaller ordinal; sometimes one says: $\kappa$ is an infinite initial ordinal), then $\kappa^+$ is the successor cardinal of $\kappa$, which is an ordinal much much larger than $\kappa+1$. If $\alpha$ is an ordinal then $|\alpha|$ is its cardinality (the initial ordinal in bijection with $\alpha$), and $\alpha^+$ means $|\alpha|^+$. For $\alpha$ finite sometimes people mean $\alpha^+=\alpha+1$ and sometimes they mean $\alpha^+=\omega$. $\endgroup$ – Andrés E. Caicedo May 27 '11 at 14:58

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.