1. ## PPPP(empty set)

So I need to find $\displaystyle \mathcal{P} \mathcal{P} \mathcal{P} \mathcal{P} (\phi)$.

I start with $\displaystyle \phi$.

$\displaystyle \mathcal{P}(\phi)=\{ \phi\}$

$\displaystyle \mathcal{P}\mathcal{P}(\phi)=\{ \phi, \{ \phi \} \}$

$\displaystyle \mathcal{P}\mathcal{P}\mathcal{P}(\phi)=\{ \phi , \{ \phi \}, \{ \phi, \{ \phi \} \} \}$

(After $\displaystyle \mathcal{P} (\phi)$, i'm just taking the union of the sets before it. Therefore (writing the elements as a list)):

$\displaystyle \mathcal{P}\mathcal{P}\mathcal{P}\mathcal{P}(\phi) = \{$

$\displaystyle \phi$
$\displaystyle \{ \phi\}$
$\displaystyle \{ \phi, \{ \phi \} \}$
$\displaystyle \{ \phi , \{ \phi \}, \{ \phi, \{ \phi \} \} \}$

$\displaystyle \}$

To me this makes sense since i'm constructing the natural numbers:

$\displaystyle \phi=0$
$\displaystyle \mathcal{P} (\phi)=\{ \phi \} =1$
$\displaystyle \mathcal{P} \mathcal {P} (\phi)=\{\phi, \{ \phi \} \}=2$ etc

However, my tutor wrote that I should have 16 elements in $\displaystyle \mathcal {P} \mathcal{P}\mathcal{P}\mathcal{P}(\phi)$. How is he getting all these extra elements?

2. Originally Posted by Showcase_22
So I need to find $\displaystyle \mathcal{P} \mathcal{P} \mathcal{P} \mathcal{P} (\phi)$.
I start with $\displaystyle \phi$.
$\displaystyle \mathcal{P}(\phi)=\{ \phi\}$
$\displaystyle \mathcal{P}\mathcal{P}(\phi)=\{ \phi, \{ \phi \} \}$
$\displaystyle \mathcal{P}\mathcal{P}\mathcal{P}(\phi)=\{ \phi , \{ \phi \}, \{ \phi, \{ \phi \} \} \}$
To me this makes sense since i'm constructing the natural numbers:
However, my tutor wrote that I should have 16 elements in
You missed a set at the third level.
$\displaystyle \mathcal{P}\mathcal{P}\mathcal{P}(\phi)=\{ \phi , \{ \phi \}, \{\{ \phi \}\},\{ \phi, \{ \phi \} \} \}$
The power set of a set of $\displaystyle n$ has $\displaystyle 2^n$ members. That what your tutor means.

That said, that is not the way the natural numbers are defined.
This is
$\displaystyle 0=\emptyset$
$\displaystyle 1=\{0\}=\{\emptyset\}$
$\displaystyle 2=\{0,1\}$
$\displaystyle 3=\{0,1,2\}$
$\displaystyle .\quad \vdots$

3. Since I have already started writing...

If $\displaystyle |A|=n$, then $\displaystyle |\mathcal{P}(A)|=2^n$. Therefore, indeed, $\displaystyle |\mathcal{P}^4(\emptyset)|=16$.

Originally Posted by Showcase_22
$\displaystyle \mathcal{P}\mathcal{P}\mathcal{P}(\phi)=\{ \phi , \{ \phi \}, \{ \phi, \{ \phi \} \} \}$
You need one more element: $\displaystyle \{\{\emptyset\}\}$.

$\displaystyle \mathcal{P}\mathcal{P}\mathcal{P}\mathcal{P}(\phi) = \{$

$\displaystyle \phi$
$\displaystyle \{ \phi\}$
$\displaystyle \{ \phi, \{ \phi \} \}$
$\displaystyle \{ \phi , \{ \phi \}, \{ \phi, \{ \phi \} \} \}$

$\displaystyle \}$
If we denote the elements of $\displaystyle \mathcal{P}^3(\emptyset)$ as follows: $\displaystyle a_1=\emptyset$, $\displaystyle a_2=\{\emptyset\}$, $\displaystyle a_3=\{\{\emptyset\}\}$, $\displaystyle a_4=\{\emptyset,\{\emptyset\}\}$, then your list can be written as follows:

$\displaystyle \emptyset$, $\displaystyle \{a_1\}$, $\displaystyle \{a_1,a_2\}$, $\displaystyle \{a_1,a_2,a_4\}$.

It is missing 12 sets, including $\displaystyle \{a_2\}$, $\displaystyle \{a_4\}$, $\displaystyle \{a_1,a_4\}$, $\displaystyle \{a_2,a_4\}$, as well sets that contain $\displaystyle a_3$.

To me this makes sense since i'm constructing the natural numbers
Though you can encode natural numbers in this way, a standard construction (von Neumann ordinals) defines the successor of $\displaystyle x$ as $\displaystyle x\cup\{x\}$, so the $\displaystyle n$th set contains $\displaystyle n$ elements.