◀ ▲ ▶Branches / Set-theory / Proof

Proof

(related to Theorem: 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.$
  ∎

Thank you to the contributors under CC BY-SA 4.0!

Github:

References

Bibliography

1. Hoffmann, D.: "Forcing, Eine Einführung in die Mathematik der Unabhängigkeitsbeweise", Hoffmann, D., 2018