[proofplan] The collapse map is defined by well-founded recursion along $R$: each element is sent to the set of the already-collapsed images of its $R$-predecessors. The image $M=\pi[A]$ is automatically transitive because every member of a collapsed object is itself the collapse of a predecessor. The main point is injectivity: if two collapsed sets agree, then their predecessor classes agree by [well-founded induction](/theorems/4797), and extensionality of $R$ forces the original elements to be equal. Once injectivity is known, the equivalence between $R$ and membership follows, and uniqueness follows from the same recursive equation. [/proofplan] [step:Define the collapse map by well-founded recursion] By the well-founded recursion principle for set relations, applied to the well-founded relation $R$ on the set $A$, there exists a unique function \begin{align*} \pi:A &\to V \\ a &\mapsto \{\pi(b): bRa\}, \end{align*} where $V$ denotes the ambient universe of sets, such that for every $a \in A$, \begin{align*} \pi(a)=\{\pi(b): b \in A \text{ and } bRa\}. \end{align*} Define \begin{align*} M:=\pi[A]=\{\pi(a):a\in A\}. \end{align*} [guided] We define $\pi$ from the bottom upward along the well-founded relation $R$. Since $R$ is well-founded, there are no infinite descending $R$-chains obstructing the recursive definition. The defining rule is \begin{align*} \pi(a)=\{\pi(b): b \in A \text{ and } bRa\}. \end{align*} Thus the value of $\pi(a)$ is determined entirely by the values of $\pi$ on the $R$-predecessors of $a$. The well-founded recursion principle gives a unique function \begin{align*} \pi:A &\to V \\ a &\mapsto \{\pi(b): bRa\} \end{align*} satisfying this equation for every $a \in A$. We then define the candidate collapsed set by taking the image \begin{align*} M:=\pi[A]=\{\pi(a):a\in A\}. \end{align*} [/guided] [/step] [step:Show that the image of the collapse map is transitive] Let $x \in y$ with $y \in M$. Since $y \in M$, there exists $a \in A$ such that $y=\pi(a)$. By the recursive definition of $\pi(a)$, \begin{align*} x \in \pi(a) \implies \exists b \in A \text{ such that } bRa \text{ and } x=\pi(b). \end{align*} Hence $x=\pi(b)\in M$. Therefore every member of every element of $M$ lies in $M$, so $M$ is transitive. [guided] To prove transitivity, we must show that whenever an element of $M$ has a member, that member is again in $M$. Let $x \in y$ and $y \in M$. By the definition of $M$ as the image of $\pi$, there exists $a \in A$ such that \begin{align*} y=\pi(a). \end{align*} Since $x \in y$, we have $x \in \pi(a)$. The recursive definition says \begin{align*} \pi(a)=\{\pi(b): b \in A \text{ and } bRa\}. \end{align*} Therefore there is some $b \in A$ such that $bRa$ and \begin{align*} x=\pi(b). \end{align*} But $\pi(b)$ is an element of $\pi[A]=M$, so $x \in M$. This proves that $M$ is transitive. [/guided] [/step] [step:Prove injectivity by well-founded induction] We prove that $\pi$ is injective. Suppose not. Let \begin{align*} C:=\{a\in A:\exists a'\in A,\ a\neq a' \text{ and } \pi(a)=\pi(a')\}. \end{align*} If $C$ were nonempty, well-foundedness of $R$ would give an element $a_0 \in C$ such that no element of $C$ is an $R$-predecessor of $a_0$. Choose $a_1 \in A$ with $a_1\neq a_0$ and $\pi(a_0)=\pi(a_1)$. We claim that $a_0$ and $a_1$ have the same $R$-predecessors. Let $b \in A$ with $bRa_0$. Then \begin{align*} \pi(b)\in \pi(a_0)=\pi(a_1), \end{align*} so there exists $c \in A$ such that $cRa_1$ and $\pi(b)=\pi(c)$. Since $bRa_0$ and no $R$-predecessor of $a_0$ lies in $C$, the equality $\pi(b)=\pi(c)$ implies $b=c$. Hence $bRa_1$. Conversely, let $b \in A$ with $bRa_1$. Then \begin{align*} \pi(b)\in \pi(a_1)=\pi(a_0), \end{align*} so there exists $c \in A$ such that $cRa_0$ and $\pi(b)=\pi(c)$. Since $cRa_0$ and no $R$-predecessor of $a_0$ lies in $C$, we have $c\notin C$. The equality $\pi(c)=\pi(b)$ therefore implies $c=b$, and hence $bRa_0$. Thus \begin{align*} \forall b\in A,\quad bRa_0 \iff bRa_1. \end{align*} By extensionality of $R$ on $A$, this implies $a_0=a_1$, contradicting the choice of $a_1$. Hence $C=\varnothing$, and $\pi$ is injective. [guided] The only nonformal point is injectivity. We argue by contradiction and use well-foundedness to choose a first possible failure. Define \begin{align*} C:=\{a\in A:\exists a'\in A,\ a\neq a' \text{ and } \pi(a)=\pi(a')\}. \end{align*} Thus $C$ is the set of elements whose collapse value is shared by some distinct element of $A$. Suppose $C$ is nonempty. Since $R$ is well-founded on $A$, there is an element $a_0 \in C$ such that no $R$-predecessor of $a_0$ belongs to $C$. By the definition of $C$, choose $a_1 \in A$ with \begin{align*} a_1\neq a_0, \qquad \pi(a_1)=\pi(a_0). \end{align*} We show that $a_0$ and $a_1$ have the same $R$-predecessors. Let $b \in A$ and assume $bRa_0$. Then the recursive definition gives \begin{align*} \pi(b)\in \pi(a_0). \end{align*} Since $\pi(a_0)=\pi(a_1)$, we also have \begin{align*} \pi(b)\in \pi(a_1). \end{align*} Again using the recursive definition of $\pi(a_1)$, there exists $c \in A$ such that \begin{align*} cRa_1 \qquad\text{and}\qquad \pi(c)=\pi(b). \end{align*} Now $bRa_0$, and $a_0$ was chosen so that no $R$-predecessor of $a_0$ lies in $C$. Therefore $b\notin C$. Since $\pi(b)=\pi(c)$, the definition of $C$ forces $b=c$. Hence $bRa_1$. For the reverse implication, let $b \in A$ and assume $bRa_1$. Then the recursive definition gives \begin{align*} \pi(b)\in \pi(a_1). \end{align*} Since $\pi(a_1)=\pi(a_0)$, we have \begin{align*} \pi(b)\in \pi(a_0). \end{align*} Using the recursive definition of $\pi(a_0)$, there exists $c \in A$ such that \begin{align*} cRa_0 \qquad\text{and}\qquad \pi(c)=\pi(b). \end{align*} Now $cRa_0$, and $a_0$ was chosen so that no $R$-predecessor of $a_0$ lies in $C$. Therefore $c\notin C$. Since $\pi(c)=\pi(b)$, the definition of $C$ forces $c=b$. Hence $bRa_0$. We have proved both implications, so \begin{align*} \forall b\in A,\quad bRa_0 \iff bRa_1. \end{align*} Because $R$ is extensional on $A$, equality of predecessor classes implies \begin{align*} a_0=a_1, \end{align*} contradicting the choice of $a_1\neq a_0$. Therefore $C$ is empty, and $\pi$ is injective. [/guided] [/step] [step:Identify the relation $R$ with membership in the collapse] Since $M=\pi[A]$, the map \begin{align*} \pi:A \to M \end{align*} is surjective by definition. By the previous step it is injective, hence bijective. Let $a,b\in A$. If $aRb$, then the recursive definition gives \begin{align*} \pi(a)\in \pi(b). \end{align*} Conversely, if $\pi(a)\in\pi(b)$, then by the recursive definition there exists $c\in A$ such that $cRb$ and $\pi(c)=\pi(a)$. Injectivity of $\pi$ gives $c=a$, and therefore $aRb$. Thus \begin{align*} aRb \iff \pi(a)\in\pi(b). \end{align*} [/step] [step:Prove uniqueness of the transitive collapse] Let $N$ be a transitive set and let \begin{align*} \sigma:A \to N \end{align*} be a bijection such that for all $a,b\in A$, \begin{align*} aRb \iff \sigma(a)\in\sigma(b). \end{align*} Then for every $a\in A$, \begin{align*} \sigma(a)=\{\sigma(b):bRa\}. \end{align*} Indeed, if $x\in\sigma(a)$, then $x\in N$ by transitivity of $N$, so $x=\sigma(b)$ for some $b\in A$ because $\sigma$ is surjective. The membership equivalence gives $bRa$. The reverse inclusion follows directly from $bRa\implies \sigma(b)\in\sigma(a)$. Thus $\sigma$ satisfies the same well-founded recursive equation as $\pi$. By uniqueness in well-founded recursion, $\sigma=\pi$. Consequently, \begin{align*} N=\sigma[A]=\pi[A]=M. \end{align*} Therefore both the collapse map and the transitive collapsed set are unique. [/step]