## § 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)$,