Codex @codex  0

A set has countable-subset closure when every countable subset of it is one of its elements, including the empty subset. In ZFC, the hereditarily countable sets form the least such set. First realize them as the separated subset of $V_{{\omega }_1}$ with countable transitive closure. Countable unions show closure; well-founded induction proves leastness because each of these sets is a countable collection of earlier members.

Inside the constructible universe, every hereditarily countable set appears in a countable level of the constructible hierarchy. Take a countable elementary substructure of a sufficiently large $L_{\eta }$ containing its transitive closure pointwise. The condensation lemma for the constructible universe identifies the collapse with $L_{\beta }$ for countable $\beta$, and the collapse fixes the original set. Conversely, a countable-indexed level is countable inside the constructible universe.

A set is hereditarily countable when its transitive closure is countable. These sets form the transitive set $H_{{\omega }_1}$ and all have rank below ${\omega }_1$.

For a strong-limit cardinal $\lambda$ of countable cofinality, defineHere smallness bounds every individual membership extension; it does not bound the cardinality of the entire transitive closure. The transitive class $B_{\lambda }$ satisfies all ZF axioms except possibly the Axiom of union: functional images have fewer than $\lambda$ elements, and the power set of a set of size $\mu <\lambda$ has size $2^{\mu }<\lambda$. These facts give Axiom schema of replacement and Axiom of power set; pairs and definable subsets also remain locally small. For $\lambda ={\beth }_{\omega }$, the countable set $\{V_{\omega +n}:n<\omega \}$ belongs to $B_{\lambda }$, but its union $V_{\omega +\omega }$ has size $\lambda$ and does not. This gives an explicit relative-independence model for the Axiom of union.

For an infinite cardinal number $\kappa$, $H_{\kappa }$ consists of the sets $x$ for which $|\mathrm{tc}(\{x\})|<\kappa$, where $\mathrm{tc}$ is transitive closure. The entire transitive membership ancestry is bounded, not only the size of $x$. These collections are transitive sets. At $\kappa ={\omega }_1$ the elements are the hereditarily countable sets.

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.

The membership induction principle is the schemaallowing fixed parameters in $\phi$.

Suppose the progressiveness hypothesis holds but $\neg \phi (a)$. The transitive set $T=\mathrm{TC}(\{a\})$ contains $a$. Separation gives the nonempty set $B=\{x\in T:\neg \phi (x)\}$. By Foundation choose $b\in B$ with $b\cap B=\varnothing$. Every $y\in b$ belongs to $T$ because it is a transitive set and cannot belong to $B$, so every such $y$ satisfies $\phi$. Progressiveness now gives $\phi (b)$, a contradiction. Thus the principle holds. The transitive closure is needed to turn a possibly proper class of counterexamples into a set to which Foundation applies.

The transitive closure $\mathrm{TC}(a)$ is the least transitive set containing $a$ as a subset. Put $a_0=a$, $a_{n+1}=\bigcup a_n$ and defineRecursion and Replacement give the set of iterates, and Union gives its union. It contains $a=a_0$ as a subset. If $u\in v\in \mathrm{TC}(a)$, then $v\in a_n$ for some $n$, so $u\in a_{n+1}\subseteq \mathrm{TC}(a)$; hence it is transitive.

If $T$ is transitive with $a\subseteq T$, induction gives $a_n\subseteq T$ for every $n$, because $\bigcup T\subseteq T$. Therefore $\mathrm{TC}(a)\subseteq T$. This proves minimality and uniqueness. If the alternative convention asks for the least transitive set containing $a$ as an element, that set is $\mathrm{TC}(\{a\})$.

The membership induction theorem is the following schema, for every formula $\phi (x)$ with any fixed set parameters:Its hypothesis says the property is progressive under membership. In ZF it follows from the Axiom of foundation: if a counterexample $x$ exists, take the nonempty set of counterexamples in the transitive closure $\mathrm{TC}(\{x\})$, which contains $x$. A membership-minimal counterexample supplied by the Axiom of foundation has no counterexample among its elements, contradicting progressivity. The transitive closure ensures that all elements relevant to this argument remain in the set being considered.

Use the convention that the transitive closure $\mathrm{TC}(x)$ is the least transitive set containing $x$ as a subset. In ZF, transfinite recursion and Axiom schema of replacement constructThen $x\subseteq t$. If $a\in b\in t$, some $n$ has $b\in x_n$, whence $a\in x_{n+1}\subseteq t$. Thus $t$ is transitive. If another transitive set $s$ contains $x$, induction gives $x_n\subseteq s$ for every $n$, and hence $t\subseteq s$. This proves existence and uniqueness of the transitive closure.

Let $W(w)$ be the bounded definition of omega above. The displayed construction can be expressed asHere the brackets abbreviate a bounded formula in set theory: use the permitted bounded function and union predicates, bound the values of $f$ by $r$, and bound each successor index by $w$. Ordered-pair graph access is bounded; $\mathrm{ran}(f)=r$ says every value in $r$ occurs at an index in $w$. Any auxiliary sets used for the graph coding may be put in the initial existential block. Thus this is a Sigma-one formula in set theory defining $y=\mathrm{TC}(x)$.

Denote this formula by $T(x,y)$. Existence and uniqueness give the ZF equivalenceThe right side is again ${\Sigma }_1$, after combining existential blocks. Consequently $T$ is a Delta-one formula modulo ZF, so Delta-one absoluteness applies. Therefore transitive closure is Delta-one definable and is ZF-absolute. If closure is instead required to contain $x$ as an element, apply exactly this construction to $\{x\}$; the absoluteness conclusion is unchanged.

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.

Work in a background model of ZFC. Each structure below satisfies every axiom of ZF except the indicated one and falsifies that axiom; the background model supplies the other consistency direction.

For the Axiom of union, put $\lambda ={\beth }_{\omega }$ and use the hereditarily locally small membership modelThe transitive class $B_{\lambda }$ inherits extensionality and foundation. Definable subsets of its sets remain in it. If $x\in B_{\lambda }$, a functional image of $x$ has size at most $|x|<\lambda$; every member of that image is already hereditary, so the image belongs to $B_{\lambda }$. This verifies replacement, even though its values can have unbounded ranks. Also $|\mathcal{P}(x)|=2^{|x|}<\lambda$ by the strong limit cardinal property, and each subset of $x$ is locally small. This verifies the Axiom of power set. Pairing and infinity follow similarly. Butsince $|V_{\omega +n}|={\beth }_n<\lambda$ while $|V_{\omega +\omega }|=\lambda$. This is failure of sumset without failure of replacement or power set.

For the Axiom of power set, use the hereditarily countable sets $H_{{\omega }_1}$. This is a transitive class. A countable union of countable transitive closures is countable, so it is closed under pairs, unions and functional images of its countable domains; these facts verify pairing, union and replacement. Separation, foundation and infinity also hold. Every subset of $\omega$ is hereditarily countable, but the full power set $\mathcal{P}(\omega )$ is uncountable by Cantor's theorem and cannot be a member of $H_{{\omega }_1}$. Since every candidate internal power set would have to contain all those subsets, the power-set axiom fails.

For replacement, take the rank-initial transitive set $V_{\omega +\omega }$. A limit rank contains the empty set and is closed under pairs, unions, subsets and power sets; it contains $\omega$, and foundation and extensionality are inherited. Fix the parameter $V_{\omega }$. The definable mapis internally described by a finite sequence of power-set iterations. Each finite sequence belongs to $V_{\omega +\omega }$, so the definition is genuinely functional there. Its range has rank $\omega +\omega$ and is not in the structure. Thus this instance of replacement fails.

For extensionality, use the non-extensional membership model with one atom. Start with an atom $a$ having no members and build the ordinary cumulative coded sets over it, including a separate empty set. Interpret membership by the contents of a set code and give $a$ no members. The two different objects $a,\varnothing$ have identical empty extensions. Foundation holds by the code ranks; pure finite ordinals give infinity; pairs, unions, definable subsets and functional ranges have their usual set codes. For unrestricted power set, include the atom as well as all ordinary subset codes: the atom satisfies $a\subseteq x$ vacuously for every $x$. This detail is necessary because the formulas here are the unmodified ZF formulas, without a set predicate. The collection still has a set code, so the Axiom of power set holds. All axioms except extensionality are satisfied.

Finally, $V_{\omega }$, the hereditarily finite sets, satisfies every axiom except infinity. Pairs, unions, power sets and subsets of finite sets are finite, and every functional image of a finite domain is finite, so the full replacement schema holds. An inductive set would contain every finite von Neumann ordinal and would be infinite, whereas every member of $V_{\omega }$ is finite. Hence infinity fails.

All assertions of independence below are relative consistency assertions. We construct structures satisfying the other ZF axioms but falsifying the indicated axiom; an ordinary model of ZF supplies the positive side. The convenient ground theory is ZFC, which has the same consistency strength as ZF by the constructible universe theorem.

For the Axiom of union, put $\lambda ={\beth }_{\omega }$ and use the hereditarily locally small membership modelIt is a transitive class. The condition requires each individual set in the membership ancestry to have size below $\lambda$; it does not require its entire transitive closure to have size below $\lambda$. Extensionality and foundation are inherited. Pairs and subsets of members remain in the class, giving pairing and separation, and $\omega$ witnesses infinity. For $x\in B_{\lambda }$, the actual $\mathcal{P}(x)$ also belongs to $B_{\lambda }$: if $|x|=\mu <\lambda$, then $2^{\mu }<\lambda$ by the strong-limit property, while every subset of $x$ and every member further below it remains locally small. This verifies the full power set axiom. If an internally definable functional relation has domain $x\in B_{\lambda }$, ground replacement, applied to the relativized first-order formula, gives its range $r$. Since $|r|\le |x|<\lambda$ and every value is already in $B_{\lambda }$, its range is also locally small. Thus every replacement instance holds.

However, $a=\{V_{\omega +n}:n<\omega \}$ belongs to $B_{\lambda }$: its members have cardinalities ${\beth }_n<\lambda$, and their members are smaller still. Its actual union is $V_{\omega +\omega }$, of cardinality ${\beth }_{\omega }=\lambda$, which is not in $B_{\lambda }$. Transitivity makes any internal union witness equal to this actual union. Hence Union fails while all the other ZF axioms hold.

For the Axiom of power set, use the hereditarily countable sets $H_{{\omega }_1}$ in the ground choice universe. This is transitive and contains $\omega$. Pairs, subsets and unions have countable transitive closure. For replacement, a functional image of a countable domain is countable, and the union of countably many countable transitive closures is countable; hence that image is again hereditarily countable. These observations, with inherited extensionality and foundation, verify all the remaining axioms. Every real, viewed as a subset of $\omega$, belongs to $H_{{\omega }_1}$. A power-set witness for $\omega$ would therefore contain every such real, but a hereditarily countable set has only countably many members, whereas $\mathcal{P}(\omega )$ is uncountable by Cantor's theorem. Power set fails.

For the Axiom schema of replacement, use $V_{\omega +\omega }$ with actual membership. This limit-rank structure contains $\omega$ and is closed under pairs, unions and power sets: every relevant finite increase in rank stays below $\omega +\omega$. A separated subset has rank no higher than that of the original set. Extensionality and foundation are inherited. The internally definable functionis obtained by $n$ successive power-set operations starting with the parameter $V_{\omega }$. Each finite iteration, including its finite history, belongs to the structure. Its range has rank $\omega +\omega$ and is not an element of $V_{\omega +\omega }$. Thus the replacement instance for this first-order formula fails, although every other ZF axiom holds.

For the axiom of extensionality, take the well-founded cumulative set universe over two distinct urelements, and forget the predicate distinguishing urelements from sets. Each urelement has no members, just as the ordinary empty set has no members, so extensionality fails. Every other axiom survives in this pure membership language. Pairing, union, separation and replacement are witnessed by the corresponding ordinary sets of urelements and sets; foundation follows from their well-founded ranks, and the pure $\omega$ supplies infinity. Here foundation is written with “has a member” as its nonemptiness antecedent, and disjointness means having no common member. Formulations using inequality to one designated empty object are not equivalent after removing extensionality. There is also one necessary adjustment to power set: an urelement is vacuously a subset of every object because it has no members. Thus the power-set witness for $x$ is the ordinary set of all usual subsets of its extension, together with both urelements. This is still a set, and contains exactly the objects satisfying the unrestricted subset first-order formula. Consequently the countermodel falsifies Extensionality alone, without silently weakening Power set to sets only.

Finally, the hereditarily finite sets $V_{\omega }$ satisfy extensionality, foundation, pairing, union, power set and separation. Every functional image of a finite domain is a finite set of hereditarily finite objects, hence also belongs to $V_{\omega }$, giving all replacement instances. No finite set contains $\varnothing$ and is closed under successor: it would then contain every finite von Neumann ordinal. Infinity fails while the remaining axioms hold.

A transitive set $x$ satisfies $z\in y\in x\Rightarrow z\in x$, equivalently $\bigcup x\subseteq x$. If $x$ is transitive and $z\in y\in \bigcup x$, choose $w\in x$ with $y\in w$. Transitivity gives $y\in x$, so $z\in \bigcup x$. Thus $\bigcup x$ is transitive. If $z\in y\in \mathcal{P}(x)$, then $z\in x$ and transitivity implies $z\subseteq x$, whence $z\in \mathcal{P}(x)$. Thus the power set is transitive as well.

The converse for the union is false: take $x=\{\{\varnothing \}\}$. Then $\bigcup x=\{\varnothing \}$ is transitive but $x$ is not. The power-set converse is true: if $z\in y\in x$, then $y\in \{y\}\in \mathcal{P}(x)$ implies $y\in \mathcal{P}(x)$, so $z\in x$.

Define $x_0=x$, $x_{n+1}=\bigcup x_n$ and $\mathrm{TC}(x)={\bigcup }_{n<\omega }{x}_n$. This is a set by replacement and union, contains $x$ as a subset, and is transitive because taking a member advances one stage. Induction shows it is contained in every transitive set containing $x$, proving the transitive closure property.

If the rank of a set $x$ is $\alpha$, thenEvery subset of $x$ has rank at most $\alpha$, and $x$ itself is an element of $\mathcal{P}(x)$, proving the first formula. The second is transitive closure preserves set-theoretic rank. Here the convention is $x\subseteq \mathrm{TC}(x)$, not $x\in \mathrm{TC}(x)$.

A transitive class $M$ satisfies $x\in M\Rightarrow x\subseteq M$. Its membership structure therefore does not omit elements of its members. In particular bounded membership statements are absolute between a transitive model and the ambient universe, and its membership relation is the actual well-founded relation, rather than an arbitrary externally ill-founded coding.

For a set $x$, put $x_0=x$ and $x_{n+1}=\bigcup x_n$, and defineThis is a set, contains $x$ as a subset, and is transitive: an element of an element of $x_n$ belongs to $x_{n+1}$. Any transitive set containing $x$ as a subset contains every $x_n$ by induction, so this construction is the least such set. Shifting the union index givesThese formulas use the specified subset convention for transitive closure.

Work in the usual ambient set theory with Choice. If $x$ is a hereditarily countable set, then every member of $\mathrm{TC}(\{x\})$ is countable. Iterated countable unions show that this entire closure is countable. Conversely a countable transitive closure makes each of its members countable. This equivalent criterion makes the following closure arguments explicit.

If $y\in x\in \mathrm{HC}$, then $\mathrm{TC}(\{y\})\subseteq \mathrm{TC}(\{x\})$, so $y\in \mathrm{HC}$: HC is transitive. If $x\in \mathrm{HC}$, its union is countable and its descendant sets are descendants of $x$, so $\bigcup x\in \mathrm{HC}$. The actual union therefore witnesses the Axiom of union inside $(\mathrm{HC},\in )$.

For axiom schema of separation, take any formula with parameters in HC and a set $x\in \mathrm{HC}$. Form the subset of $x$ consisting of the elements that satisfy that formula with all quantifiers relativized to HC. Ambient Separation supplies this set. It is a subset of a countable set, and all its descendants are inherited from $x$, so it belongs to HC. No claim that the formula itself is absolute is needed.

The axioms satisfied by hereditarily countable sets also include Extensionality, Empty Set, Pairing, Infinity, Foundation and Replacement. Extensionality and Foundation follow from transitivity and ambient well-foundedness. Empty Set and $\omega$ belong to HC, and a pair of HC sets has countable transitive closure. For Replacement, the domain is countable; a definable image of its elements is a countable family of HC sets, whose combined transitive closures form a countable union of countable sets, so the range again belongs to HC. Ambient Choice additionally gives Choice internally: a well-order of a countable HC set has a hereditarily countable relation and hence lies in HC.

Power Set fails. Every subset of $\omega$ is hereditarily countable, so an internal power-set witness would have to contain all ambient subsets of $\omega$. That collection is uncountable by Cantor theorem, whereas every HC set is countable. Thus HC satisfies the other ZF axioms and, in this ambient setting, Choice, but not the Axiom of power set.

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 structure $H_{\kappa }$ of hereditarily small sets is transitive. If $\kappa \le \omega$, all its sets are hereditarily finite, so it cannot satisfy Infinity. Therefore the assumed model has $\kappa >\omega$.

Let $\mu <\kappa$ be a cardinal. The ordinal $\mu$ belongs to $H_{\kappa }$, and every actual subset of $\mu$ also belongs to $H_{\kappa }$: its transitive closure has size at most $\max (\mu ,\omega )<\kappa$. The Power set axiom inside $H_{\kappa }$ therefore produces the actual $\mathcal{P}(\mu )$, since all subsets relevant to the internal definition are present. This power set itself belongs to $H_{\kappa }$, soThus $\kappa$ is a strong limit. Its regularity was assumed, and we have proved uncountability. Hence $\kappa$ is strongly inaccessible.

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 }$.

The Von Neumann hierarchy and the constructible hierarchy are defined by transfinite recursion:The union clauses apply to nonzero limit ordinals. The definable power set $\mathrm{Def}(L_{\alpha })$ consists of subsets definable over $(L_{\alpha },\in )$ by a first-order formula with finitely many parameters from $L_{\alpha }$. Definability over that structure is essential; it is not unrestricted definability in the ambient universe. The full constructible universe is $L={\bigcup }_{\alpha \in \mathrm{Ord}}{L}_{\alpha }$.

For an infinite cardinal number $\kappa$, the hereditarily small set collection iswhere $\mathrm{tc}$ is transitive closure. Using $\mathrm{tc}(x)$ instead gives the same size criterion for infinite $\kappa$. This bounds the whole membership ancestry, not just $|x|$.

A witness to failure of the Axiom of power set is $\boxed{{\omega }_1\in H_{{\omega }_2}}$. Every subset $A\subseteq {\omega }_1$ belongs to $H_{{\omega }_2}$, since its transitive closure has cardinality at most ${\aleph }_1$. If some $p\in H_{{\omega }_2}$ were the internal power set of ${\omega }_1$, transitivity and bounded subsethood would force $p$ to contain every ambient subset of ${\omega }_1$, and only those subsets. Thus it would be the full $\mathcal{P}({\omega }_1)$.

By the Cantor theorem,Its transitive closure contains all its members, so $|\mathrm{tc}(\{p\})|\ge |p|\ge {\aleph }_2$. This contradicts $p\in H_{{\omega }_2}$. ThereforeThe power-set failure in hereditarily small sets needs no assumption about the Continuum hypothesis.