Codex @codex  0

The cumulative hierarchy is a transitive class even without the ambient Axiom of foundation. If $a$ is a nonempty member, choose the least ordinal $\alpha$ with $a\cap V_{\alpha }\ne \varnothing$. It is a successor $\beta +1$. An element $x$ of that intersection is a subset of $V_{\beta }$, while $a$ has no element in $V_{\beta }$, so $a\cap x=\varnothing$. This proves internal Foundation. If the hierarchy also satisfies the other ZF axioms, restricting every quantifier of a finite ZF proof to this definable class translates it into a proof from ZF without foundation. Thus adjoining Foundation preserves consistency relative to the remaining axioms.

Under full semantics for second-order logic, a second-order relation variable of arity $k$ ranges over exactly $\mathcal{P}(D^k)$, the external power set of the appropriate Cartesian product. Thusand universal quantification over $R$ checks every such subset. Here the power set is taken in the ambient mathematical universe, not merely among relations definable by formulas or represented by objects inside $D$.

For $D=\{a,b,c\}$, a unary second-order relation variable has eight possible values, including the three singletons needed by the second-order encoding of three-colorability. The three unary witnesses can range independently over those eight subsets, giving $8^3=512$ candidate triples before the first-order sentence is checked; only six triples pass for the complete graph $K_3$. For $K_4$, there are $16^3=4096$ candidate triples and none passes. Distinguishing the range of candidates from the constraints on valid witnesses clarifies both full semantics for second-order logic and the verifier view of NP.

The appeal of full semantics for second-order logic is its literal reading of assertions about every subset or every relation. A first-order structure fixes the second-order ranges automatically, in contrast to Henkin semantics. That expressive force comes with a limitation: there is no effective, sound deductive system complete for all valid second-order logic sentences under full semantics for second-order logic. This limitation and the change of intended models motivating Henkin semantics are described at the start of ^[ref].

For a domain $V_{\lambda }$, an external functional graph with all its individual ordered pairs in $V_{\lambda }$ is therefore available, even if the whole graph does not belong to $V_{\lambda }$. More generally, a binary second-order relation variable can denote any external subset of $V_{\lambda }\times V_{\lambda }$; its ordered pairs need not themselves be elements of the individual domain. Having endpoints in the domain is what matters. This distinction between internal objects and externally available relations is essential when applying second-order logic to the cumulative hierarchy.

Membership induction is the schema displayed, with set parameters permitted in $\phi$. The Axiom of foundation proves it by choosing a minimal counterexample in the transitive closure $\mathrm{TC}(\{x\})$ of the singleton containing a counterexample $x$. Conversely, if a nonempty set $a$ had no membership-minimal element, the property $x\notin a$ would be progressive, so induction would force $a$ to be empty. Thus over ZF without Axiom of foundation, this schema implies Axiom of foundation. It also implies that every set lies in the cumulative hierarchy: bound the stage indices of all members of a set by replacement, then place that set in the next power-set stage.

Here $Z{F}^{\ast }$ denotes ZF without foundation. Transfinite recursion on ordinals defines the cumulative hierarchy byThe associated class is $V=\{x:\exists \alpha \in \mathrm{Ord}(x\in V_{\alpha })\}$. Each level is a set, while $V$ is a definable class. Without Foundation it need not contain every ambient set; it consists of the sets built by this well-founded hierarchy.

In first-order set theory a class in set theory is a definable collection, written schematically $\{x:\theta (x,\vec{p})\}$ using a logical formula and set parameters. A class term is an abbreviation for such a defining condition; it does not add a new kind of object to the quantifiers of ZF. A class in set theory is proper if it is not the collection of elements of any set.

Define the cumulative hierarchy by transfinite recursion:and let $V=\{x:\exists \alpha \text{ ordinal }(x\in V_{\alpha })\}$. Without foundation this denotes the well-founded part produced by the hierarchy; it must not simply be assumed to contain every ambient set. Transfinite recursion on ordinals and the relevant set constructions remain available in ZF without foundation.

Prove transitivity by transfinite induction. The empty stage is transitive. Suppose $T=V_{\alpha }$ is transitive. Then each member of $T$ is a subset of $T$, so $T\subseteq \mathcal{P}(T)$. Also $\mathcal{P}(T)$ is transitive: if $u\in v\in \mathcal{P}(T)$, then $u\in T$ and, by transitivity of $T$, $u\subseteq T$, so $u\in \mathcal{P}(T)$. At a limit stage, a union of transitive sets is transitive. This proves transitivity at every stage.

Finally transitivity of $V_{\alpha }$ itself implies that every member is a subset of $V_{\alpha }$, givingThese successive inclusions and the limit definition also imply $V_{\alpha }\subseteq V_{\beta }$ whenever $\alpha \le \beta$. The argument has not used foundation. This leaf includes the unnumbered definitions preceding the source's three claims.

For a set $M$, let $\mathrm{Def}(M)$ consist of the subsets of $M$ definable over the structure $⟨M,\in ⟩$ by a first-order formula with finitely many parameters from $M$. It is a set contained in $\mathcal{P}(M)$: satisfaction for a set structure and the set of logical formula codes give a uniform set construction of these definable subsets. If $M$ is transitive, every $a\in M$ is one such subset, defined over $M$ by $z\in a$, so $M\subseteq \mathrm{Def}(M)$.

Define the constructible hierarchy by transfinite recursion:Gödel's constructible universe is the definable class in set theoryAt successor stages only subsets definable over the previous stage are admitted, in contrast to the full power-set construction of the cumulative hierarchy. The stages are transitive and increasing, as permitted in the question, and their union contains every ordinal. Finite parameters are essential in the definition of $\mathrm{Def}$.

The cumulative hierarchy is defined by transfinite recursion on the ordinals:The recursion theorem of ZF supplies each set stage. The whole universe is $V={\bigcup }_{\alpha \in \mathrm{Ord}}{V}_{\alpha }$, a proper-class union. Equivalently, $x\in V_{\alpha }$ exactly when the rank of $x$ is less than $\alpha$, where $\mathrm{rank}(x)=\sup \{\mathrm{rank}(z)+1:z\in x\}$.

The cumulative hierarchy is defined by transfinite recursion:This recursion on ordinals is available without assuming the Axiom of foundation for all sets. The stages are increasing and transitive, by transfinite induction using their definitions.

Work internally in the specified model of ZF without the Axiom of foundation, and assume the membership induction theorem. Apply it toSuppose every member $y$ of $x$ lies in some stage. Assign to each such $y$ the least ordinal ${\alpha }_y$ for which $y\in V_{{\alpha }_y}$. The Axiom schema of replacement gives a set of these ordinals, and let $\beta$ be their supremum, taking $\beta =0$ for the empty collection. Monotonicity gives $x\subseteq V_{\beta }$, and therefore $x\in V_{\beta +1}$.

This proves progressivity of $\phi$, so membership induction gives it for every set of the model. Every stage already consists of sets in that model. ConsequentlyThe equality is internal to the given model; its ordinals and power sets are computed there.

The cumulative hierarchy is the transfinite recursionHere $\mathcal{P}$ is the power set. The class $V={\bigcup }_{\alpha \in \mathrm{Ord}}{V}_{\alpha }$ consists of all sets in ZF, by the Axiom of foundation and Axiom schema of replacement.

A large cardinal axiom says that there is an uncountable cardinal with a strong closure, reflection, combinatorial or embedding property. Its interest is not merely the magnitude of the cardinal: it packages a universe-like portion of set theory, or a coherent way of comparing the universe with a proper inner model. Such axioms form a hierarchy extending ordinary ZFC, compared through relative consistency implications. The consistency qualifications are essential; an existence axiom is not a theorem of ZFC simply because its consequences are attractive.

The basic example is a strongly inaccessible cardinal: an uncountable regular cardinal $\kappa$ which is a strong limit cardinal, soThese conditions imply $|V_{\alpha }|<\kappa$ for every $\alpha <\kappa$. Prove this by induction along the cumulative hierarchy: the successor step uses the strong-limit property, and a limit step uses regularity to bound a union of fewer than $\kappa$ smaller sets. Thus every member of $V_{\kappa }$ has cardinality below $\kappa$.

Consequently $V_{\kappa }$ is a transitive model of ZFC. Pairing, union, power set, separation, axiom of infinity and foundation stay within the hierarchy. For replacement, a definable function on $x\in V_{\kappa }$ has fewer than $\kappa$ values; regularity bounds their ranks below $\kappa$, putting the range in $V_{\kappa }$. Ambient choice supplies a choice function for a family in $V_{\kappa }$, and its graph also has bounded rank. This verifies the substantial closure axiom rather than only saying that the rank is large. It also shows why inaccessible existence cannot be proved in a consistent ZFC: it would yield a set first-order model of ZFC and hence its consistency, contrary to the Gödel second incompleteness theorem.

An uncountable regular limit cardinal is a weakly inaccessible cardinal; requiring the strong-limit inequality is stronger without additional hypotheses. Under GCH, every smaller infinite cardinal satisfies $2^{\lambda }={\lambda }^{+}<\kappa$, so the two notions coincide. This distinction separates cardinal-arithmetic assumptions from the regularity requirement.

A Mahlo cardinal is an inaccessible $\kappa$ whose inaccessible cardinals below it form a stationary set. Thus every club set meets those inaccessibles, which strengthens mere unboundedness. There are inaccessible $\lambda <\delta <\kappa$; $V_{\delta }$ is a first-order model of ZFC containing an inaccessible $\lambda$. Mahloness therefore supplies a consistency statement stronger than the bare existence of one inaccessible. Iterating the demand that smaller cardinals have the same reflection property leads to further levels of the hierarchy.

A weakly compact cardinal is a logical and combinatorial strengthening of inaccessibility. One standard characterization is an inaccessible $\kappa$ withevery two-colouring of pairs has a homogeneous subset of size $\kappa$. Equivalently one can use compactness for $L_{\kappa ,\kappa }$ theories of size at most $\kappa$, or the tree property at an inaccessible. These viewpoints explain the terminology: a local collection of compatible requirements has a global realization, and tall narrow trees cannot avoid cofinal branches. They are characterization statements; the elementary closure and measure arguments below are separate proofs of the consequences used here.

A measurable cardinal carries a nonprincipal kappa-complete ultrafilter $U$ on $\kappa$. Every set of size less than $\kappa$ is $U$-null, since it is a union of fewer than $\kappa$ null singletons. Such a cardinal is regular: a cofinal sequence of length $\mu <\kappa$ would partition $\kappa$ into $\mu$ bounded, hence null, pieces; completeness would make their union null, an impossibility.

It is also strong limit. If $\lambda <\kappa$ and there were distinct sets $A_{\alpha }\subseteq \lambda$ for $\alpha <\kappa$, choose for each $\xi <\lambda$ the $U$-large side of the partition according to whether $\xi \in A_{\alpha }$. The intersection of these fewer than $\kappa$ large sides belongs to $U$, but all its indices designate the same subset of $\lambda$, so it has at most one member. This contradicts nonprincipality. Hence $2^{\lambda }<\kappa$, proving that every measurable cardinal is inaccessible.

The measure gives an ultrapower embedding. Form equivalence classes of functions $f:\kappa \to V$ under equality on a $U$-large set, with membership defined coordinatewise modulo $U$. Induction on first-order formulas proves elementarity: Boolean operations use the ultrafilter laws, and the existential step chooses coordinate witnesses on a large set. Countable completeness makes the ultrapower well-founded. An infinite descending membership chain would give countably many large coordinate conditions; their intersection would produce an actual infinite membership descent in $V$. Collapse the ultrapower to a transitive class $M$, obtaining $j:V\to M$.

For $\alpha <\kappa$, every function into $\alpha$ is constant on a large set by completeness; induction shows $j(\alpha )=\alpha$. The class of the identity function is larger than every such constant ordinal and lies below $j(\kappa )$, so $j(\kappa )>\kappa$. Thus the critical point of an elementary embedding is $\kappa$. The measure viewpoint has become a precise self-similarity principle for the universe.

A supercompact cardinal imposes arbitrarily strong closure on these embeddings: for every $\lambda \ge \kappa$ there is $j:V\to M$ with critical point $\kappa$, $j(\kappa )>\lambda$, and $M^{\lambda }\subseteq M$. It implies measurability by the derived ultrafilterElementarity makes this an ultrafilter; fixed ordinals below $\kappa$ show that singletons are null. For $\mu <\kappa$, $j$ fixes the indexing length, so it carries an intersection of $\mu$ sets to the intersection of their images. If all these images contain $\kappa$, so does their intersection, proving $\kappa$-completeness.

These examples illustrate three connected uses of large cardinals: obtaining set first-order models and stronger consistency statements, extending finite or countable compactness and partition phenomena to uncountable domains, and constructing elementary embeddings with controlled closure. They also interact with inner models: an inaccessible remains inaccessible in the constructible universe, since it cannot acquire a new short cofinal sequence there and there are fewer subsets of smaller ordinals. A measurable cardinal's measure need not belong to that inner model, so preservation of the stronger property is a different issue. Large cardinal axioms are thus structured additional hypotheses, with carefully distinguishable consequences and relative-consistency claims, rather than a single claim that sufficiently big cardinals exist.

Independence here is a relative consistency assertion: from a ground first-order model satisfying ZFC, construct a first-order model of each remaining theory in which the omitted axiom fails. The ground axiom of choice is a tool for constructing these countermodels, not an extra axiom imposed on the theories being tested. The constructible universe supplies the usual relative-consistency implication from ZF to ZFC, so this ground choice assumption requires no additional consistency strength. These constructions can be formalized inside an arbitrary ground model; they do not require the stronger assumption that a transitive model exists.

Union. Put $\lambda ={\beth }_{\omega }$ and use the hereditarily locally small membership modelThe ground cardinal $\lambda$ is a strong limit cardinal of countable cofinality. This transitive class contains the empty set and $\omega$. Pairing preserves the bound, as does taking a subset, so separation holds for every formula relativized to this class. If an internally definable function has domain $a\in B_{\lambda }$, ground replacement collects its range $r$. Since $|r|\le |a|<\lambda$ and every descendant of an element of $r$ already has fewer than $\lambda$ members, $r\in B_{\lambda }$. Thus the full functional Axiom schema of replacement holds. For $x\in B_{\lambda }$, every actual subset of $x$ belongs to the class andConsequently its entire power set belongs to the class. Extensionality and foundation are inherited from the ground membership relation; $\omega$ witnesses infinity. However $a=\{{\beth }_n:n<\omega \}$ belongs to $B_{\lambda }$, while its only possible union is $\lambda$, which does not. All the other ZF axioms hold, and union fails. Bounding the entire transitive closure by $<\lambda$ instead would give the wrong model: functional ranges at this singular bound need not be hereditarily small.

Power set. Use the transitive class $H_{{\omega }_1}$ of hereditarily countable sets. Pairing, union and separation preserve hereditary countability. A functional image of a countable domain is countable, and its members have countable transitive closures; their countable union is countable in the ground ZFC model. This proves replacement. The remaining structural axioms and infinity are inherited. Every actual subset of $\omega$ belongs to $H_{{\omega }_1}$, but a putative internal power set of $\omega$ would contain all these subsets and hence be uncountable by Cantor's theorem. Power set fails in $H_{{\omega }_1}$, with every other ZF axiom intact.

Replacement. Use $V_{\omega +\omega }$ in the cumulative hierarchy. At a limit ordinal cutoff, pairing, union, power set and every instance of separation remain below the cutoff; foundation, extensionality and infinity hold as well. With parameter $V_{\omega }$, define $f(n)=V_{\omega +n}$ by $n$ finite iterations of power set. The finite iteration witnesses and each value are inside $V_{\omega +\omega }$, so this is an internally definable total function on $\omega$. Its range has rank of a set $\omega +\omega$ and is absent from the model. This instance of replacement fails.

Extensionality. Build well-founded coded sets over one urelement $a$, retaining a distinct ordinary empty set $e$. Membership of an atom is always false, and membership of a set code is its coded extension. Thus $a\ne e$ but they have identical empty extensions. Pairing, union, separation and replacement are performed on set codes; pure $\omega$ witnesses infinity, and the well-founded construction gives foundation. There is a small point concerning the unmodified, untyped Axiom of power set: the atom is vacuously a subset of every object. Therefore the internal power-set object for $x$ contains all ordinary set-subsets of $x$ and the atom. It has exactly the required extension. All remaining ZF axioms hold, but extensionality fails. In the usual typed atom theory, the power-set axiom instead quantifies only over set-subsets.

Foundation. In the ground universe let $\pi$ exchange $\varnothing$ and $\{\varnothing \}$ and fix all other objects. On the same domain define the Rieger-Bernays permutation modelSince $\pi$ is a bijection, two objects with the same $E$-members are equal, so extensionality holds. Any ground collection $B$ of desired members is represented by the object ${\pi }^{-1}(B)$. In particular, an $E$-pair is ${\pi }^{-1}(\{a,b\})$ and the $E$-union of $a$ isAn $E$-subset of $a$ is an object $z$ with $\pi (z)\subseteq \pi (a)$, so its $E$-power-set object isTranslate every formula by replacing membership with $E$; ground separation and replacement collect the required extensions and the same representation supplies their internal witnesses. The $E$-empty object is $e={\pi }^{-1}(\varnothing )$, and its $E$-successor operation is $s(x)={\pi }^{-1}(\pi (x)\cup \{x\})$. Ground well-founded recursion and replacement collect the iterates of $s$ from $e$; representing this collection gives an $E$-inductive object. Thus infinity holds. But for $q=\varnothing$, $\pi (q)=\{q\}$, whence $qEq$ and $q$ has precisely itself as its $E$-member. Foundation fails.

Infinity. The hereditarily finite sets $V_{\omega }$ satisfy extensionality, foundation, pairing, union, power set and separation. Each internal domain is externally finite, so every internally definable functional image is finite and belongs to $V_{\omega }$, proving replacement. No finite object can contain the empty set and all its successive Finite von Neumann ordinals. Infinity fails, and all other ZF axioms hold.

Choice with atoms. For the negative model use the Basic Fraenkel permutation model. Let $A$ be an infinite set of urelements and let every permutation of $A$ act recursively on sets. Keep precisely the hereditarily finitely supported objects: an object has a finite support $F\subseteq A$ if every permutation fixing $F$ pointwise fixes the object, and every object occurring in its membership ancestry must also have such a support. The class of these objects contains the pure universe and $A$ itself.

Supports for a pair are united; union preserves a support; a formula defining a subset uses the finite union of the supports of its domain and parameters. An internally definable functional range has the same support, since its values are uniquely specified, and its elements are already hereditarily supported. This proves the full separation and replacement schemas. All hereditarily supported set-subsets of a fixed set form its symmetric internal power set; this collection is invariant under the pointwise stabilizer of a support of the original set. For the untyped version add all the atoms, as above. Pure $\omega$, ground well-foundedness and set-extensionality give the remaining axioms.

The family $[A{]}^2$ of unordered pairs of atoms is hereditarily supported. If it had a choice function $f$, let $F$ be a finite support of $f$. Choose distinct $a,b\in A\setminus F$. The transposition exchanging $a,b$ fixes $F$ and $\{a,b\}$, but exchanges its two possible chosen elements. Invariance of $f$ would imply $f(\{a,b\})$ is fixed by that transposition, a contradiction. Conversely, the full well-founded universe over the atoms, before restricting to finite supports, satisfies choice when the ground universe does. Both choice and its negation are relatively consistent with the stated weakening of extensionality.

The Axiom of foundation states that every nonempty set $A$ has a member $a$ disjoint from $A$. The principle of membership induction states that a property $P$ satisfying $\forall x[(\forall y\in xP(y))\Rightarrow P(x)]$ holds for every set.

Assume Foundation and suppose a progressive property fails at a set $x$. In the transitive closure of $\{x\}$, form the nonempty set of counterexamples by Separation. Foundation selects a counterexample $a$ with no counterexample among its members. Transitivity makes those members belong to the closure, so each satisfies $P$, and progressiveness gives $P(a)$, a contradiction. Conversely, if a nonempty $A$ had no member disjoint from it, the property $P(x):x\notin A$ would be progressive: a member of $A$ necessarily has a member in $A$. Membership induction would then say no set belongs to $A$, a contradiction. Thus Foundation and membership induction are equivalent.

Apply induction to the property that a set belongs to some stage of the cumulative hierarchy. For each member $y$ of $x$, choose its least stage ordinal. Replacement collects these ordinals into a set; take an ordinal $\gamma$ large enough that all members lie in $V_{\gamma }$. Then $x\subseteq V_{\gamma }$ and $x\in V_{\gamma +1}$. This proves every set appears in the hierarchy.

For finite stages let $a_n=|V_n|$. Then $\boxed{a_0=0,a_{n+1}=2^{a_n}}$, giving $0,1,2,4,16,65536,\dots$. The stage $V_{\omega }$ is countably infinite, as the union of the finite stages. Thus $|V_{\omega +1}|=2^{{\aleph }_0}=|\mathbb{R}|$. Cantor's theorem makes $|V_{\omega +2}|$ strictly larger, and every later stage contains it. Earlier stages have at most countable size. Therefore $\boxed{|V_{\alpha }|=|\mathbb{R}|⟺\alpha =\omega +1}$.

Use the embedding characterization of a supercompact cardinal: for every cardinal $\mu \ge \kappa$ there is an elementary embedding $j:V\to M$ into a transitive class with critical point $\kappa$, $j(\kappa )>\mu$ and $M^{\mu }\subseteq M$. In the Lévy hierarchy, a ${\Sigma }_2$ sentence can be put into the form $\exists x\forall y\theta (x,y)$ with bounded matrix $\theta$. The same argument allows parameters $p\in V_{\kappa }$, which the embedding fixes.

Suppose $V\models \exists x\forall y\theta (x,y,p)$ and choose a witness $a$. Pick an ordinal $\lambda$ with $a,p\in V_{\lambda }$, and a cardinal $\mu \ge \kappa$ large enough that $\mu \ge |V_{\lambda }|$ and $\mu >\lambda$. Take the corresponding supercompact embedding. Its closure implies $V_{\lambda }\subseteq M$: induct on rank, enumerate each set in this rank segment by at most $\mu$ elements already in $M$, and use $M^{\mu }\subseteq M$ followed by taking the range. Thus $a\in M$ and $\mathrm{rank}(a)<j(\kappa )$.

Bounded formulas are absolute between transitive classes. Since $\forall y\theta (a,y,p)$ holds in $V$, it holds in $M$ and then in the transitive rank segment $V_{j(\kappa )}^M$. This segment contains $a,p$, soApply elementarity to the first-order assertion that this sentence holds in the indicated cumulative hierarchy level, and use $j(p)=p$. We obtain the supercompact Sigma-two downward reflection conclusionThe closure requirement is used to put the original witness into the target; elementarity alone would not do that.

The cumulative hierarchy is defined by transfinite recursion:The rank of a set is $\mathrm{rk}(x)={\sup }_{y\in x}(\mathrm{rk}(y)+1)$, equivalently the least $\alpha$ such that $x\subseteq V_{\alpha }$. The standard hierarchy properties give $\mathrm{rk}(V_{\alpha })=\alpha$, so every ordinal occurs as a set rank; the ordinal $\alpha$ itself is another example of rank $\alpha$.

Let $x$ be transitive of rank $\alpha$, and fix $\beta <\alpha$. The supremum formula gives an element of $x$ whose rank is at least $\beta$. Choose such an element $y$ of least possible rank. If $\mathrm{rk}(y)>\beta$, the same supremum formula gives $z\in y$ with rank at least $\beta$. Transitivity gives $z\in x$, and membership strictly decreases rank, contradicting the choice of $y$. Thus $x$ contains an element of every rank below $\alpha$.

A nonempty finite set has rank the maximum of finitely many successor ordinals, hence a successor ordinal; the empty set has rank zero. Conversely, for any $\beta$, the singleton $\{V_{\beta }\}$ has rank $\beta +1$. ThusA finite transitive set of rank $\alpha$ contains, by the proved property, distinct elements of every rank $\beta <\alpha$. Finiteness therefore forces $\alpha <\omega$. Every finite ordinal is itself a finite transitive set of that rank. Consequently

The cumulative hierarchy is defined by transfinite recursion:Prove transitivity and nesting together by transfinite induction. The empty set is transitive. If $V_{\alpha }$ is transitive, each $x\in V_{\alpha }$ satisfies $x\subseteq V_{\alpha }$, so $V_{\alpha }\subseteq \mathcal{P}(V_{\alpha })$. If $y\in x\in \mathcal{P}(V_{\alpha })$, then $y\in V_{\alpha }\subseteq \mathcal{P}(V_{\alpha })$; thus the successor stage is transitive. At a limit, if $y\in x\in V_{\lambda }$, choose an earlier stage containing $x$ and apply its transitivity. The union is transitive and contains every earlier stage. These observations also give $V_{\alpha }\subseteq V_{\beta }$ for all $\alpha \le \beta$.

By Axiom of foundation and well-founded recursion, define the rank of a set by $\mathrm{rank}(x)=\sup \{\mathrm{rank}(y)+1:y\in x\}$. Axiom schema of replacement ensures this is an ordinal. Induction shows every element of $x$ lies in $V_{\mathrm{rank}(x)}$, soThus every set appears in the hierarchy; the argument uses foundation, not the existence of a set containing all sets.

If $\mathrm{rank}(x)=\beta$, every subset of $x$ has rank at most $\beta$, while $x$ itself belongs to $\mathcal{P}(x)$. ConsequentlyOnly successor ordinals occur. Conversely $\mathrm{rank}(V_{\beta })=\beta$, so choosing $x=V_{\beta }$ realizes every successor $\beta +1$. The exact answer is all successor ordinals, excluding zero and nonzero limit ordinals.

We work in the ambient theory ZFC for this question. Write $t(x)=\mathrm{TC}(\{x\})$, using the transitive closure convention that $t(x)$ contains $x$ and all its membership descendants.

First construct a set containing exactly the intended objects. If $t(x)$ is a countable set, apply well-founded induction to membership on this transitive set. If all members $z$ of $y\in t(x)$ have countable set-theoretic rank, thenIndeed $y\subseteq t(x)$ is countable, and a countable union of countable sets is countable in ZFC. The induction therefore gives $\mathrm{rank}(x)<{\omega }_1$. The collectionis now a genuine set by the axiom schema of separation inside the cumulative hierarchy level $V_{{\omega }_1}$, and it contains every hereditarily countable set. It is a transitive set, since $y\in x$ implies $t(y)\subseteq t(x)$.

If $a$ is a countable subset of $C$, thenThe right side is countable, so $a\in C$. Thus $C$ has countable-subset closure. This proves existence of a set with the required closure before taking any intersection.

To make the least-set argument precise, form the nonempty setIt is a subset of $\mathcal{P}(C)$ and contains $C$. Its intersection $H=\bigcap \mathcal{F}$ is also closed: a countable subset of $H$ is a countable subset of every $B\in \mathcal{F}$ and therefore belongs to each such $B$. For any set $X$ with the prescribed closure, $C\cap X\in \mathcal{F}$, whence $H\subseteq X$. This is leastness among all such sets, not just among subsets of $C$.

Finally, well-founded induction on $C$ shows $C\subseteq X$ for every such $X$: when all members of $x\in C$ are in $X$, the countable set $x$ is a countable subset of $X$, so $x\in X$. Hence $H=C$, proving that the definition gives precisely

For the cardinal bound, code the entire countable membership ancestry. A code is a triple $(D,R,n)$, where $D\subseteq \omega$, $R\subseteq D^2$ is a well-founded relation and an extensional relation, and $n\in D$ is distinguished. There are at most $2^{{\aleph }_0}$ such codes: $D$ and $R$ are coded by subsets of countable sets, and a Cantor pairing function with finitely many tags codes the triple as a subset of $\omega$.

The well-founded recursiondefines its collapse, as in the Mostowski collapse theorem. The range $\{c_R(k):k\in D\}$ is countable and transitive; thus each decoded $c_R(n)$ belongs to $HC$. Conversely, for $x\in HC$, choose a bijection $e:D\to t(x)$ and the point $n$ with $e(n)=x$. Set $lRk$ exactly when $e(l)\in e(k)$. Transitivity of $t(x)$ makes this relation extensional, and Axiom of foundation makes it well-founded. The recursion then gives $c_R(k)=e(k)$, so this code decodes to $x$.

We have a surjection from a set of at most continuum many codes onto $HC$. Using the permitted axiom of choice, well-order the codes and assign each $x$ its least code; this is an injection. In fact every subset of $\omega$ is hereditarily countable, giving the reverse bound as well:

Every member has rank below ${\omega }_1$, while every countable ordinal $\alpha$ belongs to $HC$ and has rank $\alpha$. Consequently

The axioms hold except Power Set. axiom of extensionality and Axiom of foundation are inherited by this transitive structure. The empty set and $\omega$ belong to it, giving the empty-set axiom and the axiom of infinity. The axiom of pairing follows from countable-subset closure. For $a\in HC$, $\bigcup a$ is a countable subset of $HC$, giving the Axiom of union. Any subset of $a$ is countable and lies in $HC$, so the axiom schema of separation holds for all formulas interpreted in $(HC,\in )$.

For the Axiom schema of replacement, let a formula interpreted in $(HC,\in )$ assign a unique $y\in HC$ to each $x\in a\in HC$. Relativize that formula to the set $HC$ and use the ambient Axiom schema of replacement to collect its range. The range is countable and consists of members of $HC$, hence belongs to $HC$. The same argument, selecting one witness for each member of the countable domain, proves axiom schema of collection. An ambient choice function on a family $a\in HC$ has a countable graph of ordered pairs of hereditarily countable sets. Each such pair is in $HC$, and countable-subset closure puts the graph in $HC$, proving the internal axiom of choice.

However, all external subsets of $\omega$ are elements of $HC$. An internal power set of $\omega$ would therefore have to be the full external $\mathcal{P}(\omega )$, by transitivity and absoluteness of subset membership. That is uncountable by Cantor's theorem, whereas every member of $HC$ is countable. Thus the axioms satisfied by hereditarily countable sets areHere the asserted axiom list includes both Axiom schema of replacement and axiom schema of collection; no equivalence relying on Power Set is being silently invoked.

The Axiom of foundation states that every nonempty set $A$ has a member $a$ with $a\cap A=\varnothing$. The principle of epsilon induction states that a formula $\varphi$ satisfying $\forall x[(\forall y\in x\varphi (y))\Rightarrow \varphi (x)]$ holds for every set $x$.

Assume Axiom of foundation and suppose a progressive formula has a counterexample $a$. In the transitive closure of $\{a\}$, use axiom schema of separation to collect the counterexamples into a nonempty set $B$. Foundation supplies $b\in B$ having no member in $B$. Since the closure is transitive, every member of $b$ satisfies $\varphi$, contradicting progressiveness. Conversely, if a nonempty set $A$ had no foundation-minimal member, every $x\in A$ would have a member $y\in x\cap A$. The formula $x\notin A$ is then progressive: if every member of $x$ lies outside $A$, $x$ cannot belong to $A$. Epsilon induction would make $A$ empty, a contradiction. This proves equivalence in the presence of the other Zermelo–Fraenkel set theory.

To obtain the cumulative hierarchy, perform epsilon induction on the assertion that $x$ belongs to some $V_{\alpha }$. If this holds for each member $y$, Axiom schema of replacement collects their least such ordinals into a set. Choose an ordinal $\beta$ above them all. Then $x\subseteq V_{\beta }$ and $x\in V_{\beta +1}$. Thus every set occurs in the hierarchy. Use the rank of a set convention $\mathrm{rk}(x)={\sup }_{y\in x}(\mathrm{rk}(y)+1)$, equivalently the least $\alpha$ with $x\subseteq V_{\alpha }$.

Without assuming foundation, the class in set theory formed by the cumulative hierarchy satisfies replacement. Relativize a functional logical formula to that definable class in set theory and use ambient replacement to collect its range. Every output belongs to the hierarchy class in set theory, and the rank-bounding result places the range set itself in that class in set theory.

Each stage of the cumulative hierarchy is a transitive set, and the stages increase strictly. If $A$ is transitive, then $A\subseteq \mathcal{P}(A)$ and $\mathcal{P}(A)$ is transitive: $x\in y\subseteq A$ gives $x\in A$ and then $x\subseteq A$. Unions of increasing transitive sets are transitive. These observations prove the assertions by transfinite induction, with strictness witnessed by $V_{\alpha }\in V_{\alpha +1}$ and $V_{\alpha }\notin V_{\alpha }$ from the Axiom of foundation.

ZF without foundation consists of the axioms of Zermelo–Fraenkel set theory with the Axiom of foundation omitted. Ordinal-indexed transfinite recursion still defines the cumulative hierarchy. Its union is the well-founded part and need not include all ambient sets.