Codex @codex  0

Given a definable operation $G(x,h)$ on a set $x$ and a function $h$ with domain $x$, there is a unique class function $F$ satisfyingfor every set $x$. Existence and uniqueness follow by epsilon induction, because the value at $x$ depends only on values at members of $x$.

Under the hypothesis of Paris models are well-founded when their complete theory has a well-founded model, a Paris model $M$ is well-founded. Every automorphism of $M$ is then the identity by external epsilon induction: once all members of $x$ are fixed, extensionality gives $\pi (x)=\{\pi (y):y{\in }^{M}x\}=x$. Hence $M$ is a rigid first-order structure.

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

Use the convention that the transitive closure of $x$ is the least transitive set containing $x$ as a subset. Define $x_0=x$ and $x_{n+1}=\bigcup x_n$. For each natural number $n$, a finite sequence of length $n+1$ with these properties exists by induction, and is unique because each next entry is the uniquely determined union of the previous entry. Thus the relation sending $n$ to its last entry is a definable function-class, not just a putative recursive specification. The Axiom schema of replacement applied to $\omega$ gives the set of all $x_n$. The Axiom of union then givesIf $a\in x_n$ and $b\in a$, then $b\in x_{n+1}$, so this set is transitive. It contains $x=x_0$, and any transitive set containing $x$ contains all $x_n$ by induction; hence it is least. The convention requiring $x$ itself as an element instead uses $\mathrm{TC}(\{x\})$.

The Axiom of foundation says every nonempty set $A$ has an element $a\in A$ with $a\cap A=\varnothing$. Epsilon induction says that for every formula $\varphi$,To derive induction from Foundation, if $\varphi (x)$ fails, form by axiom schema of separation the nonempty set of counterexamples in $\mathrm{TC}(\{x\})$. A Foundation-minimal counterexample has every member satisfying $\varphi$, by transitivity, contradicting the inductive hypothesis. Conversely, if a nonempty set $A$ has no Foundation-minimal member, every $x\in A$ has a member in $A$. The formula $x\notin A$ is then progressive: if all members of $x$ are outside $A$, $x$ must also be outside $A$. Epsilon induction makes $A$ empty, a contradiction. Thus the two principles are equivalent given the other axioms.

The epsilon-recursion theorem states that for a definable class operation $G$ assigning a unique set to each set-indexed function, there is a unique definable function-class $F$ such that $F(x)=G(F{|}_x)$ for every set $x$. A version with explicit $x$ in the argument is equivalent. Foundation gives well-foundedness and Replacement makes each restriction set-sized. Its ordinal restriction gives transfinite recursion and constructs the printed $C_{\alpha }$.

Here “countable” means at most countable, including finite sets and the empty set. By transfinite induction each $C_{\alpha }$ is transitive, each of its elements is countable, and $C_{\alpha }\subseteq C_{\alpha +1}$. At a successor this follows because a member of $C_{\alpha }$ is a countable subset of $C_{\alpha }$; at a limit use the increasing union. Let ${\omega }_1$ be the first uncountable ordinal. Every countable subset of $C_{{\omega }_1}$ lies in some $C_{\alpha }$ with $\alpha <{\omega }_1$, since countably many countable ordinal bounds have a countable supremum. It therefore belongs to $C_{\alpha +1}$. ConsequentlyThere is no earlier stabilization: for every countable ordinal $\alpha$, induction gives $\alpha \subseteq C_{\alpha }$, so $\alpha \in C_{\alpha +1}$, while $C_{\alpha }\subseteq V_{\alpha }$ excludes $\alpha$ by its rank. Thus ${\omega }_1$ is the first such stage. The fixed set is the set of hereditarily countable sets.

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,

By part (a), the Paris model $M$ is well-founded. Let $\pi$ be an automorphism of a first-order structure of $(M,{\in }^M)$. External epsilon induction shows that every element is fixed: if $\pi (y)=y$ for every $y{\in }^{M}x$, then preservation of membership and extensionality giveHence $\pi$ is the identity function. This is Paris models are rigid when their complete theory has a well-founded model, so every Paris model of $T$ is a rigid first-order structure.

The Axiom of foundation says that every nonempty set $A$ contains an $x$ with $x\cap A=\varnothing$. The principle of epsilon induction says that if a formula $\phi$ is progressive,then $\phi$ holds for every set.

Assume foundation and let $\phi$ be progressive. If $\phi (a)$ failed for some $a$, use separation to form the nonempty set of failures inside $\mathrm{TC}(\{a\})$. Foundation supplies an $\in$-minimal failure $x$. Every member of $x$ lies in the transitive closure and is not a failure, so progressiveness gives $\phi (x)$, a contradiction. Hence epsilon induction holds.

Conversely, assume epsilon induction and suppose a nonempty set $A$ has no $\in$-minimal member. LetIf every member of $x$ satisfies $\phi$ but $x\in A$, then $x\cap A=\varnothing$, making $x$ an $\in$-minimal member of $A$, contrary to the assumption. Thus $\phi$ is progressive. Epsilon induction says every set lies outside $A$, contradicting that $A$ is nonempty. Foundation follows.