Codex @codex  0

A countable well-founded relation that is an extensional relation codes a transitive set through the Mostowski collapse theorem. Adding a distinguished point selects one decoded set. Every hereditarily countable set has such a code by enumerating its transitive membership ancestry. There are only continuum many codes. In ZFC, selecting least codes in a well-order gives an injection of the hereditarily countable sets into a set of size $2^{{\aleph }_0}$.

An $\in$-isomorphism is a bijection $f:X\to Y$ such that $x\in x^{\prime }$ if and only if $f(x)\in f(x^{\prime })$ for all $x,x^{\prime }\in X$. When $Y$ is transitive, surjectivity gives the stronger recursive descriptionIndeed every member of $f(x)$ belongs to $Y$ because it is a transitive set and so has a preimage in $X$; the isomorphism property identifies exactly which preimages occur.

If $f,g$ are two such maps, possibly to different transitive sets, form $B=\{x\in X:f(x)\ne g(x)\}$. If $B$ were nonempty, Foundation would give $x\in B$ with $x\cap B=\varnothing$. All predecessors $u\in x\cap X$ then satisfy $f(u)=g(u)$, and the recursive descriptions force $f(x)=g(x)$, a contradiction. Therefore the map and its transitive range are unique.

The necessary and sufficient condition is that $⟨X,\in ⟩$ be well-founded and extensional as a relation on $X$. Well-foundedness says every nonempty $A\subseteq X$ has a member with no $\in$-predecessor in $A$. The extensional relation condition says distinct elements $x,x^{\prime }\in X$ have distinct predecessor sets $x\cap X$, $x^{\prime }\cap X$. Sufficiency is the Mostowski collapse theorem.

For necessity, an isomorphism transfers well-foundedness from its transitive range, where Foundation applies. For extensionality, if $x\cap X=x^{\prime }\cap X$, the recursive descriptions give $f(x)=f(x^{\prime })$, and injectivity gives $x=x^{\prime }$. Notice that ambient axiom of extensionality alone does not establish this internal predecessor condition; for example $X=\{\{0\},\{2\}\}$ can have distinct elements with no predecessors in $X$.

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 Mostowski collapse theorem applies when $E$ is a well-founded relation and an extensional relation on the set $M$. Extensionality here means that different points have different sets of $E$-predecessors. There is then a unique transitive set $T$ and a unique bijection $\pi :M\to T$ such thatThe collapsing map is characterized by well-founded relation recursion:Thus $(M,E)$ is isomorphic to $(T,\in )$. Both well-foundedness and extensionality are hypotheses of the theorem; well-foundedness alone does not make the recursive map injective.

The epsilon-recursion theorem says that for every definable operation $G$ assigning a set $G(x,h)$ to each set $x$ and each function $h$ with domain $x$, there is a unique class function $F$ such thatfor every set $x$.

For uniqueness, suppose $F$ and $F^{\prime }$ both satisfy the recursion. If they agree on every $y\in x$, then their restrictions to $x$ agree and henceThe epsilon induction principle therefore gives $F=F^{\prime }$.

For existence, call a function $f$ coherent on a transitive set $T$ whenThe same epsilon-induction argument shows that any two coherent functions agree on the intersection of their transitive domains. Assuming coherent functions have been constructed below every member of $x$, their compatible union defines all values below $x$; adjoining the value prescribed by $G(x,\cdot )$ extends the construction to $x$. Epsilon induction establishes this construction for every $x$. The compatible local functions therefore unite to the required class function $F$.

A relation $r$ on $x$ is well-founded when every nonempty subset of $x$ has an element with no $r$-predecessor in that subset. It is extensional when

The Mostowski collapse theorem states that every well-founded extensional relation $(x,r)$ is isomorphic to membership on a unique transitive set $M$. Define recursivelyWell-founded recursion makes $\pi$ well defined. Epsilon-style induction along $r$, together with extensionality, shows that $\pi$ is injective. By definition,so $\pi$ is an isomorphism from $(x,r)$ onto $(M,\in )$, where $M=\mathrm{ran}\pi$. If $z\in \pi (a)\in M$, then $z=\pi (b)$ for some $bra$, so $z\in M$; hence $M$ is transitive. If another collapse ${\pi }^{\prime }$ has transitive range, induction gives ${\pi }^{\prime }(a)=\{{\pi }^{\prime }(b):bra\}=\pi (a)$, proving uniqueness.

Finally, suppose $x$ is finite. Its collapse $M$ is a finite transitive set, so every member of $M$ is hereditarily finite. Therefore every well-founded extensional relation on $x$ collapses to a transitive subset of $V_{\omega }$.

Conversely, let $x$ be infinite. Choose the initial infinite ordinal $\kappa$ equinumerous with $x$. The successor ordinal $\kappa +1$ has the same cardinality as $\kappa$. Pulling its membership relation back along a bijection $x\to \kappa +1$ gives a well-founded extensional relation on $x$ whose collapse is $\kappa +1$. But $\kappa \in \kappa +1$ is not hereditarily finite, so $\kappa +1⊈V_{\omega }$. Consequently,

A relation $r$ on a set $x$ is well-founded when every nonempty subset of $x$ has an $r$-minimal element. It is extensional when distinct elements have distinct predecessor sets:The Mostowski collapse theorem states that every well-founded extensional relation on a set is uniquely isomorphic to membership on a transitive set; the collapse is recursively

For the requested example, let $A=V_{\omega +1}$ and defineNo $x_n$ belongs to $A$, and thereforeThe map $x_n\mapsto n$ is an isomorphism from membership on $x$ to membership on the von Neumann ordinal $\omega$, so the Mostowski collapse is $\omega$. On the other hand, $x_0=V_{\omega +1}$ already has rank $\omega +1$, and hence the rank of $x$ is greater than $\omega$.

For statement (i), suppose $(x,r)$ is isomorphic to $(y,\in )$ with $y$ transitive. Membership is well-founded by the axiom of foundation. It is extensional on $y$ because transitivity ensures that the predecessors in $y$ of an element $a\in y$ are exactly the elements of $a$, and the axiom of extensionality distinguishes different sets. Both properties are preserved by isomorphism. Thus (i) is always true.

Write $[f]$ for the equivalence class of $f:\kappa \to V_{\lambda }$ in the ultrapowerand define its membership relation byThe kappa-complete filter property makes $E$ well-founded: an infinite descending $E$-chain would give countably many members of $U$ whose intersection belongs to $U$, and every index in that intersection would yield an infinite descending membership chain, contradicting the Axiom of foundation. The relation is extensional by Łoś's theorem.

The Mostowski collapse theorem therefore gives a unique isomorphism $\pi :(N,E)\to (M,\in )$ onto a transitive set $M$. Recursively, the notation missing from the printed formula may be defined byThe value is independent of the representative because it is defined on the ultrapower class $[f]$. Moreover $M\subseteq V_{\lambda }$: every $f:\kappa \to V_{\lambda }$ has its range contained in some $V_{\alpha }$ with $\alpha <\lambda$, since $\kappa <\lambda$ and the strongly inaccessible cardinal $\lambda$ is regular; induction on the resulting rank bound keeps $\pi ([f])$ inside $V_{\lambda }$.

Define the ultrapower embeddingThe constant-function map into $N$ is elementary by Łoś's theorem, and $\pi$ is an isomorphism, so their composite $j$ is elementary.