Welcome guest
You're not logged in.
233 users online, thereof 0 logged in

Example: Some Other Examples Of Mostowski Functions and Collapses

The above introductory example was quite easy. Is also shows why it is important to have a well-founded to be able to calculate its Mostowski function and collapse. To get more familiar with the latter two concepts, let us take some more examples of well-founded relations and calculate their Mostowski functions and collapses.

Ad Example 2

The relation $R\subset \mathbb N\times \mathbb N$ defined by $nRm:\Leftrightarrow n+1=m$ (“successor relation” defined on natural numbers) has been identified as a well-founded relation. We calculate some first values of the Mostowski function:

$$\begin{array}{rcl}
\pi(0)&=&\emptyset\\
\pi(1)&=&\{\pi(0)\}=\{\emptyset\}\\
\pi(2)&=&\{\pi(1)\}=\{\{\emptyset\}\}\\
\pi(3)&=&\{\pi(2)\}=\{\{\{\emptyset\}\}\}\\
&\vdots&
\end{array}$$

Historically, this series of sets was used by Zermelo to define the natural numbers $\mathbb N$ and can be visualized as follows:

The Mostowski collapse here is the set containing all of the above sets as its elements:

$$\pi([\mathbb N])=\{\emptyset,\{\emptyset\},\{\{\emptyset\}\},\{\{\{\emptyset\}\}\},\ldots\}.$$

In contrast to the first example of the von Neumann series, this Mostowski collapse does not correspond to the value of the Mostowski function $\pi(n)$, as $n$ tends to infinity.

Ad Example 3

For a set $X$ and its power set $\mathcal P(X)$, the relation $R\subseteq \mathcal P(X)\times \mathcal P(X)$ defined by $xRy:\Leftrightarrow x\subset y$ ($x$ being a proper subset of $y$) has been identified as a well-founded relation. As an example, we take $X=\{a,b,c\}.$ Then $\mathcal P(X)=\{\emptyset,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}\}$. Since in this example, the set is finite, we can calculate all values of the Mostowski function:

$$\begin{array}{rcl}
\pi(\emptyset)&=&\emptyset\\
\pi(\{a\})&=&\{\pi(\emptyset)\}=\{\emptyset\}\\
\pi(\{b\})&=&\{\pi(\emptyset)\}=\{\emptyset\}\\
\pi(\{c\})&=&\{\pi(\emptyset)\}=\{\emptyset\}\\
\pi(\{a,b\})&=&\{\pi(\emptyset),\pi(\{a\}),\pi(\{b\})\}=\{\emptyset, \{\emptyset\}\}\\
\pi(\{a,c\})&=&\{\pi(\emptyset),\pi(\{a\}),\pi(\{c\})\}=\{\emptyset, \{\emptyset\}\}\\
\pi(\{b,c\})&=&\{\pi(\emptyset),\pi(\{b\}),\pi(\{c\})\}=\{\emptyset, \{\emptyset\}\}\\
\pi(\{a,b,c\})&=&\{\pi(\emptyset),\pi(\{a\}),\pi(\{b\}),\pi(\{c\}),\pi(\{a,b\}),\pi(\{a,c\}),\pi(\{b,c\})\}\\
&=&\{\emptyset, \{\emptyset\},\{\emptyset, \{\emptyset\}\}\}
\end{array}$$

The Mostowski collapse is the set $$\pi[\mathcal P(\{a,b,c\})]=\{\emptyset, \{\emptyset\}, \{\emptyset, \{\emptyset\}\}, \{\emptyset, \{\emptyset\},\{\emptyset, \{\emptyset\}\}\}\}.$$

Ad Example 4

The divisibility relation $R$ defined on the set $X_k:=\{1,2,3,\ldots,k\}$ with $nRm:\Leftrightarrow n\mid m\wedge n\neq m$ ($n$ is a divisor of $m$ which is unequal $m$) has been identified as a well-defined relation. We calculate all values of the Mostowski function for $k=10:$

$$\begin{array}{rcl}
\pi(1)&=&\emptyset\\
\pi(2)&=&\{\pi(1)\}=\{\emptyset\}\\
\pi(3)&=&\{\pi(1)\}=\{\emptyset\}\\
\pi(4)&=&\{\pi(1),\pi(2)\}=\{\emptyset,\{\emptyset\}\}\\
\pi(5)&=&\{\pi(1)\}=\{\emptyset\}\\
\pi(6)&=&\{\pi(1),\pi(2),\pi(3)\}=\{\emptyset,\{\emptyset\}\}\\
\pi(7)&=&\{\pi(1)\}=\{\emptyset\}\\
\pi(8)&=&\{\pi(1),\pi(2),\pi(4)\}=\{\emptyset,\{\emptyset\}\}\\
\pi(9)&=&\{\pi(1),\pi(3)\}=\{\emptyset,\{\emptyset\}\}\\
\pi(10)&=&\{\pi(1),\pi(2),\pi(5)\}=\{\emptyset,\{\emptyset\}\}\\
\end{array}$$

The Mostowski function equals $\emptyset$ for $1$, $\{\emptyset\}$ for all prime numbers $p\le k,$ and $\{\emptyset,\{\emptyset\}\}$ for all composite numbers $n\le k.$ The Mostowski collapse equals (for all $k$) the set
$$\pi[X_k]=\{\emptyset,\{\emptyset\},\{\emptyset,\{\emptyset\}\}\}.$$

| | | | created: 2019-03-01 08:19:27 | modified: 2019-03-02 22:32:23 | by: bookofproofs | references: [8055]


This work was contributed under CC BY-SA 3.0 by:

This work is a derivative of:

(none)

Bibliography (further reading)

[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.