**Proof**: *(related to "Mostowski's Theorem")*

- Let $U$ be a universal set and $(V,\prec)$ with a well-founded relation $”\prec”$ and with the corresponding Mostowski function $\pi:V\to U$ with $\pi(x):=\{\pi(y)\mid y\in V\wedge y\prec x\},$ and $\pi[V]\subseteq U$ is the Mostowski collapse.
- Assume that $x\in y$ and $y\in \pi[V].$
- Since $y\in \pi[V]$, there is an $u\in V$ with $y=\pi(u).$
- By definition of the Mostowski function, $y=\pi(u)=\{\pi(v)\mid v\in V\wedge v\prec u\}$ for an $u\in V.$
- By assumption, $x\in y.$ Therefore $x=\pi(v)$ for some $v\in V$ with $v\prec u.$
- By definition of the Mostowski function, from $v\prec u$ it follows that $\pi(v)\in \pi[V].$
- Therefore, $x\in \pi[V]$.
- Altogether, we have shown that if $x\in y$ and $y\in \pi[V]$ then $x\in\pi[V]$ which means that the Mostowski collapse $\pi[V]$ is a transitive set.

- Now, assume that $”\prec”$ is well-founded and, in addition, extensional. We want to show that $\pi$ is an order embedding, i.e. fulfills the property $v_1\prec v_2\Longleftrightarrow \pi(v_1)\in\pi(v_2)$ for $v_1,v_2\in V.$ It suffices to show that $\pi$ is injective. We will assume that $\pi$ is not injective and conclude a contradiction.
- If $\pi$ is not injective, then the values $\pi(v_1)=\pi(v_2)$ are equal for some two different elements $v_1,v_2\in V$ with $v_1\neq v_2.$
- Since $”\prec”$ is well-founded, every non-empty subset $S\subseteq V$ contains a minimal element.
- In particular, the subset $S:=\{v_1,v_2\}$ contains a minimal element.
- Without loss of generalization, assume $v_1$ is minimal, which means that there is no $x\in S$ with $x\prec v_1.$
- Since $v_2\neq v_1$ and $v_1$ is minimal in $S$, we must have $v_1\prec v_2.$
- Since $”\prec”$ is extensional, and since $v_1\neq v_2,$ we have $V_1\neq V_2$ with $V_1:=\{z\in V\mid z\prec v_1\}$ and $V_2:=\{z\in V\mid z\prec v_2\}.$
- In particular, since $v_1\prec v_2$ we must have $V_1\subset V_2,$ $u\not\in V_1,$ $u\in V_2.$
- Thus, $v_1\preceq u\prec v_2.$
- If $u\prec v_2,$ then $\pi(u)\in\{\pi(z)\mid z\prec v_2\},$ which by definition of the Mostowski function means $\pi(u)\in\pi(v_2).$
- By assumption, $\pi(v_2)=\pi(v_1),$ thus $\pi(u)\in \pi(v_1).$
- If $v_1=u$, then $\pi(u)\in \pi(u)$, in contradiction to the axiom of foundation.
- But then $v_1\prec u$ and we have both, $\pi(u)\in \pi(v_1)$ and $\pi(v_1)\in \pi(u)$, which is again a contradiction.
- Altogether, we have shown that $\pi$ is injective.
- By definition, $\pi$ is an order embedding.

The following calculation is not needed for the proof, but we want to verify that, indeed, the property $v_1\prec v_2\Longleftrightarrow \pi(x)\in\pi(y)$ is fulfilled in the case $”\prec”$ is well-founded and, in addition, extensional:

### $”\Rightarrow”$

- If $v_1\prec v_2,$ then $\pi(v_1)\in\{\pi(z)\mid z\prec v_2\}.$
- This means $\pi(v_1)\in\pi(v_2)$ by the definition of the Mostowski function.

### $”\Leftarrow”$

- If $\pi(v_1)\in\pi(v_2),$ then by the definition of the Mostowski function $\pi(v_1)\in\{\pi(z)\mid z\prec v_2\}.$
- This means $\pi(v_1)=\pi(z)$ for some $z\in V$ with $z\prec u_2.$
- Since $\pi$ is injective, this means $v_1=z$ for some $z\in V$ with $z\prec u_2.$
- This means $v_1\prec u_2.$

q.e.d

| | | | created: 2019-03-03 12:11:00 | modified: 2019-03-07 15:05:41 | by: *bookofproofs* | references: [8055]

(none)

[8055] **Hoffmann, D.**: “Forcing, Eine EinfÃ¼hrung in die Mathematik der UnabhÃ¤ngigkeitsbeweise”, Hoffmann, D., 2018

FeedsAcknowledgmentsTerms of UsePrivacy PolicyImprint

© 2018 Powered by BooOfProofs, All rights reserved.

© 2018 Powered by BooOfProofs, All rights reserved.