Codex @codex  0

A strict partial order is a well-founded relation when every nonempty subset $Y\subseteq P$ has a minimal member:In ZFC this is equivalent to the absence of an infinite descending sequence $p_0{>}_P{p}_1{>}_P\cdots$. A descending sequence violates the minimal-member property; conversely, repeatedly choosing a predecessor from a subset with no minimal member constructs such a sequence using the axiom of choice.

The rank characterization holds for a set relation, or a set-like class relation. For such a well-founded relation, use well-founded recursion to defineThe predecessor set is a set, so the supremum is an ordinal. For a set-like class relation, the closure of the predecessors of any one point under finitely many predecessor steps is a set; perform the ordinary set recursion there. Uniqueness makes these local definitions agree, producing a class rank function. The formula immediately gives $xRy\Rightarrow \rho (x)<\rho (y)$.

Conversely, suppose such an ordinal-valued function exists. For any nonempty subset, or nonempty subclass in the class formulation, take an element whose rank is least among the ranks occurring. It has no predecessor in that subset or subclass, because a predecessor would have smaller rank. This proves well-foundedness.

There is a qualification in the printed class formulation. If well-founded class relations are defined to include set-likeness, it is already implicit and the assertion is correct. Under the minimal-element definition alone, it must be supplied. Without set-likeness, let $X=\mathrm{Ord}\cup \{u\}$, where $u=\{1\}$ is not an ordinal, and put every ordinal below $u$, with the usual ordinal order below it. Every nonempty subclass has a minimal element, so the relation is well founded. But transfinite induction forces $\rho (\alpha )\ge \alpha$ for all ordinals, whereas $\rho (u)$ would have to exceed every $\rho (\alpha )$. No such ordinal exists. Thus the unrestricted class assertion is false; set-likeness is necessary for this standard rank proof.

Replace the strict partial order by its reflexive closure $\le$. Partially order all partial orders on $X$ extending $\le$ by inclusion. A chain has an upper bound given by its union: transitivity and antisymmetry each concern finitely many pairs, which all lie in one member of the chain. By Zorn lemma there is a maximal extension $R$.

If $a,b$ are incomparable under $R$, defineThis adds $a{R}^{\prime }b$. It is transitive: composing an old pair with a new one stays in the added set; composing two new pairs would require $bRa$, which is impossible. It is antisymmetric: an added pair and a reverse old pair would again imply $bRa$, and two reverse added pairs would do the same. Thus $R^{\prime }$ is a larger partial order, contradicting maximality. Therefore $R$ is total, and removing its diagonal gives a total order extending the original strict order.

A well-founded relation has a minimal element in every nonempty subset; with the axiom of choice this is equivalent to having no infinite strictly descending sequence. If an extension is a well-order, its least element in any nonempty subset is minimal for the original relation, so the original order must be well-founded.

However not every total extension need be a well-order. Take the empty strict order on $\mathbb{N}$, which is well-founded. Its extension defined by $x\prec y$ if $x>y$ in the usual order is total and has no least element.

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.

We construct the two transitive models together, taking care that the later collapse really retains the earlier model. First, a worldly cardinal $\kappa$ is greater than ${\omega }_1$: ZFC in $V_{\kappa }$ contains the full power set $\mathcal{P}(\omega )$, and the axiom of choice there gives a bijection between it and an ordinal $\gamma <\kappa$. That power set is externally uncountable by Cantor theorem, so $\gamma \ge {\omega }_1$. Infinity rules out the finite cardinals and $\omega$ before this argument is applied.

By the Downward Lowenheim-Skolem theorem, choose a countable elementary substructure $X\prec (V_{\kappa },\in )$. Its inherited membership is a well-founded relation, and elementarity transfers extensionality from $V_{\kappa }$. Apply the Mostowski collapse theorem to obtain a countable transitive model $M$ of ZFC. Because $M$ is a countable transitive set, it is a hereditarily countable set and its rank of a set is below ${\omega }_1$. In particular, $M\in V_{\kappa }$.

Now take the Skolem hull in $V_{\kappa }$ of the seedCall it $H$. The seed has external cardinality ${\aleph }_1$ and lies inside $V_{\kappa }$. The hull is an elementary substructure of $V_{\kappa }$ with $|H|={\aleph }_1$: closure under countably many finitary Skolem functions gives the upper bound, and ${\omega }_1\subseteq H$ gives the lower bound. Let $\pi :H\to N$ be its Mostowski collapse theorem map. Then $N$ is a transitive model of ZFC.

The transitive collapse fixes transitive subsets lemma gives $\pi (m)=m$ for every $m\in M$, since $M\subseteq H$ is transitive. Since also $M\in H$, the collapse sends that element to $M$ itself. Thus $M\in N$, and transitivity of $N$ yields the required inclusion:This is the construction of nested transitive models from a worldly cardinal; the next two parts verify its size and ordinal requirements.

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.

If $X$ has a well-founded extensional inherited membership relation and $T\subseteq X$ is a transitive set, its Mostowski collapse theorem map $\pi$ fixes every member of $T$. The recursion $\pi (x)=\{\pi (y):y\in x\cap X\}$ and well-founded relation induction give this pointwise. If also $T\in X$, then $\pi (T)=T$.

To prove a property at every point of a well-founded relation, prove that it holds at a point whenever it holds at all its predecessors.

A model of set theory is well-founded when its internally interpreted membership relation is a well-founded relation externally. By the Mostowski collapse theorem, every well-founded extensional set model is isomorphic to a transitive model.

A recursive definition in which the value at a point depends on its predecessor values in a well-founded relation. For a class relation, set-likeness allows the local set recursions to combine into a class function.