Well-Founded Relations, Rank, and the Cumulative Hierarchy

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

Let $X$ be a definable class and $R$ a definable binary relation on $X$, with fixed set parameters. Write ${\mathrm{pred}}_R(x)=\{y\in X:yRx\}$. The relation is setlike if this predecessor collection is a set for every $x\in X$. It is well-founded if every nonempty set $A\subseteq X$ has an $R$-minimal member $x$, meaning ${\mathrm{pred}}_R(x)\cap A=\mathrm{\varnothing }$. These are schemes in first-order set theory: a class is notation for a defining formula. No transitivity or totality of $R$ is required. Every relation on a set is setlike. An ordinal carries a well-founded membership relation by its definition; ambient Foundation does not make every arbitrary relation well-founded. All results concerning a supplied well-founded setlike relation are valid in ZF without Foundation unless stated otherwise. Conventions and prerequisites: def-ordinal. (Well-founded and setlike relations)

Let $(W,<)$ be a well-order (def-well-order) and let $G$ be a class function: a rule, given by a formula in the language of set theory, that assigns a set $G(h)$ to every function $h$ whose domain is a proper initial segment of $W$ (def-initial-segment). Then there is exactly one function $F$ with domain $W$ such that $F(a)=G(F\upharpoonright W_{<a})\text{for every }a\in W\mathrm{.}$ Here $F\upharpoonright W_{<a}$ is the restriction of $F$ to the initial segment determined by $a$, so the value of $F$ at $a$ is prescribed in terms of all its earlier values at once. Because $G$ is a class function rather than a set, this is a theorem schema of ZF: one theorem for each formula defining $G$. It uses Replacement, and it uses no form of the Axiom of Choice. (Transfinite recursion)

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

For every setlike relation $R$ on a definable class $X$ and $x\in X$, there is a least predecessor-closed set $C(x)\subseteq X$ containing $x$. It consists exactly of nodes reachable from $x$ by a finite sequence of predecessor steps. Well-foundedness is not needed. (Finite predecessor closures are sets)

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

Let $R$ be well-founded and setlike on a definable class $X$. If a definable property $P$ is progressive, meaning that for every $x\in X$, $[\mathrm{\forall }yRxP(y)]\Rightarrow P(x)$, then $P(x)$ holds for all $x\in X$. Set parameters in $P$ are allowed. This holds without Foundation. (Induction on well-founded setlike relations)

For every setlike relation $R$ on a definable class $X$ and $x\in X$, there is a least predecessor-closed set $C(x)\subseteq X$ containing $x$. It consists exactly of nodes reachable from $x$ by a finite sequence of predecessor steps. Well-foundedness is not needed. (Finite predecessor closures are sets)

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

Let $R$ be well-founded and setlike on $X$, and let a definable rule $G(x,h)$ assign a unique set whenever $x\in X$ and $h$ is a set function on ${\mathrm{pred}}_R(x)$. An attempt is a set function $f$ on a predecessor-closed set $D\subseteq X$ satisfying $f(z)=G(z,f\upharpoonright {\mathrm{pred}}_R(z))$ for every $z\in D$. Any two attempts agree on the intersection of their domains. If for every $yRx$ an attempt exists on the canonical cone $C(y)$, there is a unique attempt on $C(x)$. (Compatible recursion attempts)

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

For a set $a$, form $a_0=a$ and $a_{n+1}=a_n\cup \bigcup a_n$ by recursion on $\omega$. Set $\mathrm{TC}(a)={\bigcup }_{n\in \omega }{a}_n\mathrm{.}$ This is a set by the same recursion, Replacement and Union construction as finite predecessor closure, now starting from $a$ rather than a singleton and using membership as the setlike relation. The convention is the least transitive superset of $a$; to include $a$ itself as an element, use $\mathrm{TC}(\{a\})$. This construction does not assume Foundation. Conventions and prerequisites: lem-finite-predecessor-closure-is-a-set. (Transitive closure of a set)

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

For a well-founded setlike relation $R$ on $X$, its ordinal rank is the definable function determined by ${\rho }_R(x)=\sup \{{\rho }_R(y)+1:yRx\}=\bigcup \{{\rho }_R(y)\cup \{{\rho }_R(y)\}:yRx\}\mathrm{.}$ To justify the definition, apply well-founded recursion to the total rule which returns this union if every value of its input function is an ordinal and returns $0$ otherwise. Well-founded induction shows that every actual value is an ordinal: predecessor values are ordinals by the induction hypothesis, their successors are ordinals, Replacement collects them, and their union is an ordinal, including the empty union $0$. Thus the default case never occurs. For $yRx$ the rank equation gives ${\rho }_R(y)<{\rho }_R(x)$. The definition requires no ambient Foundation for a supplied well-founded $R$. Conventions and prerequisites: thm-recursion-on-well-founded-setlike-relations, lem-ordinal-basics. (Ordinal rank of a well-founded relation)

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

Let $(W,<)$ be a well-order (def-well-order) and let $G$ be a class function: a rule, given by a formula in the language of set theory, that assigns a set $G(h)$ to every function $h$ whose domain is a proper initial segment of $W$ (def-initial-segment). Then there is exactly one function $F$ with domain $W$ such that $F(a)=G(F\upharpoonright W_{<a})\text{for every }a\in W\mathrm{.}$ Here $F\upharpoonright W_{<a}$ is the restriction of $F$ to the initial segment determined by $a$, so the value of $F$ at $a$ is prescribed in terms of all its earlier values at once. Because $G$ is a class function rather than a set, this is a theorem schema of ZF: one theorem for each formula defining $G$. It uses Replacement, and it uses no form of the Axiom of Choice. (Transfinite recursion)

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

In ZF without Foundation define the cumulative hierarchy by $V_0=\mathrm{\varnothing },V_{\alpha +1}=\mathcal{P}(V_{\alpha }),V_{\lambda }={\bigcup }_{\beta <\lambda }{V}_{\beta }(\lambda \text{ a nonzero limit ordinal})\mathrm{.}$ For each ordinal $\theta$, use the set well-order recursion schema on $\theta +1$. On histories of domain $0$ return $\mathrm{\varnothing }$; on domain $\beta +1$ return the power set of the last value; on nonzero limit domains return the union of the range. Each is a unique set. Recursions on different ordinal intervals agree on overlaps by the uniqueness clause applied to the smaller interval. Hence the definition of $V_{\alpha }$ as the value at $\alpha$ is uniform and independent of the chosen interval. Power Set is used at successors and Replacement and Union at limits. The notation $⟨V_{\alpha }:\alpha \in \mathrm{Ord}⟩$ denotes a definable class function, not a set sequence. Conventions and prerequisites: thm-transfinite-recursion, lem-ordinal-basics, def-limit-ordinal. (The cumulative hierarchy)

Let $(W,<)$ be a well-order (def-well-order) and let $S\subseteq W$ satisfy the following: for every $a\in W$, if $W_{<a}\subseteq S$ then $a\in S$ (def-initial-segment). Then $S=W$. In property form: if a property $P$ of elements of $W$ satisfies "whenever $P(x)$ holds for every $x<a$, it holds at $a$", then $P(a)$ holds for every $a\in W$. This is a theorem of ZF. No form of the Axiom of Choice is used. Choice is perfectly available at this point in the library, since Zorn's lemma is proved from it on the previous page; the claim made here is about this proof, which never invokes it. (Transfinite induction)

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

In ZF without Foundation, every $V_{\alpha }$ is transitive and $\alpha \le \beta$ implies $V_{\alpha }\subseteq V_{\beta }$. Also $V_{\alpha }\cap \mathrm{Ord}=\alpha$, and both $\alpha$ and $V_{\alpha }$ belong to $V_{\alpha +1}\setminus V_{\alpha }$. (Transitivity and growth of hierarchy stages)

For every set $a$, $\mathrm{TC}(a)$ is transitive, contains $a$ as a subset, and is contained in every transitive set $T$ with $a\subseteq T$. Moreover $a\subseteq b$ implies $\mathrm{TC}(a)\subseteq \mathrm{TC}(b)$, and $\mathrm{TC}(\mathrm{TC}(a))=\mathrm{TC}(a)$. In particular $a\in \mathrm{TC}(\{a\})$. (Minimality and closure laws of TC)

Let $R$ be well-founded and setlike on a definable class $X$. If a definable property $P$ is progressive, meaning that for every $x\in X$, $[\mathrm{\forall }yRxP(y)]\Rightarrow P(x)$, then $P(x)$ holds for all $x\in X$. Set parameters in $P$ are allowed. This holds without Foundation. (Induction on well-founded setlike relations)

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

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)

In ZF without Foundation, every $V_{\alpha }$ is transitive and $\alpha \le \beta$ implies $V_{\alpha }\subseteq V_{\beta }$. Also $V_{\alpha }\cap \mathrm{Ord}=\alpha$, and both $\alpha$ and $V_{\alpha }$ belong to $V_{\alpha +1}\setminus V_{\alpha }$. (Transitivity and growth of hierarchy stages)

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

In ZF, for every set $x$ and ordinal $\alpha$, $x\in V_{\alpha }⟺\mathrm{rank}(x)<\alpha ,x\subseteq V_{\alpha }⟺\mathrm{rank}(x)\le \alpha \mathrm{.}$ Thus $\mathrm{rank}(x)$ is the least $\alpha$ with $x\subseteq V_{\alpha }$, and $\mathrm{rank}(x)=\alpha$ iff $x\in V_{\alpha +1}\setminus V_{\alpha }$. (Rank characterizes hierarchy membership)

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

In ZF, for every set $x$ and ordinal $\alpha$, $x\in V_{\alpha }⟺\mathrm{rank}(x)<\alpha ,x\subseteq V_{\alpha }⟺\mathrm{rank}(x)\le \alpha \mathrm{.}$ Thus $\mathrm{rank}(x)$ is the least $\alpha$ with $x\subseteq V_{\alpha }$, and $\mathrm{rank}(x)=\alpha$ iff $x\in V_{\alpha +1}\setminus V_{\alpha }$. (Rank characterizes hierarchy membership)

In ZF without Foundation, every $V_{\alpha }$ is transitive and $\alpha \le \beta$ implies $V_{\alpha }\subseteq V_{\beta }$. Also $V_{\alpha }\cap \mathrm{Ord}=\alpha$, and both $\alpha$ and $V_{\alpha }$ belong to $V_{\alpha +1}\setminus V_{\alpha }$. (Transitivity and growth of hierarchy stages)

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

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)

For a well-founded setlike relation $R$ on $X$, its ordinal rank is the definable function determined by ${\rho }_R(x)=\sup \{{\rho }_R(y)+1:yRx\}=\bigcup \{{\rho }_R(y)\cup \{{\rho }_R(y)\}:yRx\}\mathrm{.}$ To justify the definition, apply well-founded recursion to the total rule which returns this union if every value of its input function is an ordinal and returns $0$ otherwise. Well-founded induction shows that every actual value is an ordinal: predecessor values are ordinals by the induction hypothesis, their successors are ordinals, Replacement collects them, and their union is an ordinal, including the empty union $0$. Thus the default case never occurs. For $yRx$ the rank equation gives ${\rho }_R(y)<{\rho }_R(x)$. The definition requires no ambient Foundation for a supplied well-founded $R$. Conventions and prerequisites: thm-recursion-on-well-founded-setlike-relations, lem-ordinal-basics. (Ordinal rank of a well-founded relation)

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

For a well-founded setlike extensional relation $R$ on a definable class $X$, its collapse map $\pi$ is injective. (An extensional collapse is injective)

For a well-founded setlike relation $R$ on $X$, the collapse map is the unique definable function satisfying $\pi (x)=\{\pi (y):yRx\}$. Its existence and uniqueness follow from well-founded recursion. (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.

An accessible pointed graph consists of a set $X$ of nodes, a root $r\in X$, and a relation $R\subseteq X^2$. Draw an arrow $x\to y$ precisely when $yRx$. Accessibility means that for every $x\in X$ there are $n\in \omega$ and a function $p:n+1\to X$ with $p(0)=r$, $p(n)=x$, and $p(i+1)Rp(i)$ for $i<n$. The path of length zero reaches the root. A decoration is a set function $d$ on $X$ such that $d(x)=\{d(y):yRx\}$ for each node. A well-founded graph means that $R$ has the minimal-element property, not an unqualified no-infinite-path characterization. Extensionality is not part of the graph definition. No axiom of anti-foundation is assumed. Conventions and prerequisites: def-well-founded-setlike-relations. (Accessible pointed membership graphs)

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)

For every set $a$, $\mathrm{TC}(a)$ is transitive, contains $a$ as a subset, and is contained in every transitive set $T$ with $a\subseteq T$. Moreover $a\subseteq b$ implies $\mathrm{TC}(a)\subseteq \mathrm{TC}(b)$, and $\mathrm{TC}(\mathrm{TC}(a))=\mathrm{TC}(a)$. In particular $a\in \mathrm{TC}(\{a\})$. (Minimality and closure laws of TC)

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.

In ZF, for every set $x$ and ordinal $\alpha$, $x\in V_{\alpha }⟺\mathrm{rank}(x)<\alpha ,x\subseteq V_{\alpha }⟺\mathrm{rank}(x)\le \alpha \mathrm{.}$ Thus $\mathrm{rank}(x)$ is the least $\alpha$ with $x\subseteq V_{\alpha }$, and $\mathrm{rank}(x)=\alpha$ iff $x\in V_{\alpha +1}\setminus V_{\alpha }$. (Rank characterizes hierarchy membership)

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)