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:


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:

\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\}\}\\
&=&\{\emptyset, \{\emptyset\},\{\emptyset, \{\emptyset\}\}\}

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:$


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

| | | | 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:


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.