Well-Founded Relations, Rank, and the Cumulative Hierarchy: Examples and Counterexamples

Given: Work in ZF unless the statement explicitly weakens or supplements it; fix the objects and hypotheses of the statement.

In ZF, for every ordinal $\alpha$, $\mathrm{rank}(\alpha )=\alpha$ and $\mathrm{rank}(V_{\alpha })=\alpha$. (Ranks of ordinals and hierarchy stages)

Given: Work in ZF unless the statement explicitly weakens or supplements it; fix the objects and hypotheses of the statement.

Every well-founded setlike extensional relation $R$ on a definable class $X$ is isomorphic to membership on a unique transitive definable class $Y$, by a unique definable isomorphism $\pi :X\to Y$. For a set domain $X$, the isomorphism and its image are sets. This holds without ambient Foundation. (Mostowski collapse for extensional relations)

Given: Work in ZF unless the statement explicitly weakens or supplements it; fix the objects and hypotheses of the statement refuted.

A setlike relation $R$ on $X$ is extensional when ${\mathrm{pred}}_R(x)={\mathrm{pred}}_R(y)$ implies $x=y$ for $x,y\in X$. If $R$ is also well-founded, its collapse map is the unique definable function $\pi (x)=\{\pi (y):yRx\}\mathrm{.}$ Existence and uniqueness follow from well-founded recursion with $G(x,h)=\mathrm{ran}(h)$, a set by Replacement. A collapse map is defined even without extensionality; injectivity is a further conclusion requiring extensionality. The construction for a supplied well-founded relation uses no ambient Foundation. Conventions and prerequisites: thm-recursion-on-well-founded-setlike-relations. (Extensional relations and collapse maps)

Given: Work in ZF unless the statement explicitly weakens or supplements it; fix the objects and hypotheses of the statement.

Let $\kappa$ be an infinite initial ordinal. In ZF set $H_{\kappa }=\{x:\mathrm{\exists }\lambda <\kappa \mathrm{\exists }j(j:\mathrm{TC}(\{x\})\hookrightarrow \lambda )\}\mathrm{.}$ This initially defines a class. Its root-inclusive transitive closure contains $x$ as an element. When $\mathrm{TC}(\{x\})$ is well-orderable its hereditary cardinality means the least ordinal equinumerous with it; under Choice this exists for every set. The injection formulation above is used without Choice. For infinite $\kappa$, replacing $\mathrm{TC}(\{x\})$ by $\mathrm{TC}(x)$ gives the same class. Indeed $\mathrm{TC}(\{x\})=\{x\}\cup \mathrm{TC}(x)$ by the finite-stage formula. Adding one point to a set injecting into finite $\lambda$ gives an injection into $\lambda +1<\kappa$; for infinite $\lambda$, keep indices at least $\omega$, shift natural indices by one, and use index zero for the added point, obtaining an injection into $\lambda$. Restriction gives the converse. We retain the root-inclusive convention throughout. Conventions and prerequisites: prop-transitive-closure-minimality, def-cardinal. (Hereditary size and H_kappa)

In ZF, for every ordinal $\alpha$, $\mathrm{rank}(\alpha )=\alpha$ and $\mathrm{rank}(V_{\alpha })=\alpha$. (Ranks of ordinals and hierarchy stages)

Given: Work in ZF unless the statement explicitly weakens or supplements it; fix the objects and hypotheses of the statement.

In ZF every set $x$ belongs to $V_{\mathrm{rank}(x)+1}$. Consequently $V={\bigcup }_{\alpha \in \mathrm{Ord}}{V}_{\alpha }$ in the class sense: every set lies in a stage. This is not a union indexed by a set of all ordinals. (The universe is the class union of its stages)

Now assume ZF, including Foundation. Membership on the universe is well-founded and setlike, so its ordinal rank is defined for every set. Write $\mathrm{rank}(x)=\sup \{\mathrm{rank}(y)+1:y\in x\}\mathrm{.}$ The empty supremum is $0$, so $\mathrm{rank}(\mathrm{\varnothing })=0$. If $y\in x$, then $\mathrm{rank}(y)<\mathrm{rank}(x)$. This is the Foundation-dependent special case of relation rank. The earlier construction of $V_{\alpha }$ did not require Foundation. Conventions and prerequisites: def-rank-of-a-well-founded-relation, thm-foundation-equivalent-to-hierarchy-exhaustion. (Membership rank under Foundation)