§ Mostowski Collapse

• Let $V$ be a set, let $U$ be a universe and let $R$ be a well founded relation on $V$.
• Recall that a relation is well-founded iff every non-empty subset contains a minimal element. Thus, we can perform transfinite induction on $V$.
• A function $\pi_R: V \to U$ defined via well founded induction as $\pi_R(x) \equiv \{ \pi(y): y \in V \land yRx \}$is called as the mostowski function on $R$. (We suppress $\pi_R$ to $\pi$ henceforth).
• The image $\pi''V \equiv \{ \pi(x) : x \in V \}$ is called as the Mostowski collapse of $R$.
• Consider the well founded relation $R \subseteq N \times N$ such that $xRy$ iff $y = x + 1$

§ Image of collapse is transitive

• Let $U$ be a universe, let $(V, <)$ be a well founded relation on $V$.
• Let $\pi: V \to U$ be the mostowski function on $V$.
• Suppose $a \in b \in \pi[V]$. We must show that $a \in \pi[V]$.
• Since $b \in \pi[V]$, there is a $v_b \in V$ such that $\pi(v_b) = b$.
• By the definition of the Mostowski function, $b = \pi(v_b) = \{ \pi(v) : v \in V \land (v < v_b) \}$
• Since $a \in b$, this implies that there exists a $v_a < v_b$ such that $\pi(v_a) = a$.
• This implies that $a$ is in the image of $\pi[V]$: $a \in \pi[V]$.
• Thus, the set $\pi[V]$ is transitive: for any $b \in \pi[V]$ and $a \in b$, we have shown that $a \in \pi[V]$.

§ Image of collapse is order embedding if $R$ is extensional

• We already know that $\pi[V]$ is transitive from above.
• We assume that $R$ is extentional. That is: $\forall a, aRx = aRy \iff x = y$. [ie, the fibers $R^{-1}(-)$ are distinct ].
• We want to show that $v_1 < v_2 \iff \pi(v_1) \in \pi(v_2)$.

§ Forward: $v_1 < v_2 \implies \pi(v_1) \in \pi(v_2)$:

• $v_1 < v_2$, then $\pi(v_2) = \{ \pi(x): x < v_2 \}$. This implies that $\pi(v_1) \in \pi(v_2)$.

§ Backward: $\pi(v_1) \in \pi(v_2) \implies v_1 < v_2$:

• Let $\pi(v_1) < \pi(v_2)$.
• By the definition of the Mostowski function, we have that $\pi(v_2) = \{ \pi(v'): v' < v_2 \}$
• Thus, there is some $v'$ such that $\pi(v') = \pi(v_1)$.
• We wish to show that $v' = v_1$, or that the collapse function is injective.

§ Collapse is injective:

• We will suppose that the collapse is not injective and derive a contradiction.
• Suppose there are two elements $v_1, v_2$ such that $v_1 \neq v_2$ but $\pi(v_1) = \pi(v_2)$.
• WLOG, suppose $v_1 < v_2$: the relation is well-founded, and thus the set $\{v_1, v_2\}$ ought to have a minimal element, and $v_1 \neq v_2$.
• We must have $\pi(v_1) \subsetneq \pi(v_2)$,

• Reference: book of proofs