# Set is Equivalent to Proper Subset of Power Set

## Theorem

Every set is equivalent to a proper subset of its power set:

- $\forall S: \exists T \subset \mathcal P \left({S}\right): S \sim T$

## Proof

To show equivalence between two sets, we need to demonstrate that a bijection exists between them.

We will now define such a bijection.

Let $T = \left\{{\left\{{x}\right\}: x \in S}\right\}$.

\(\displaystyle \forall x \in S: \ \ \) | \(\displaystyle \left\{ {x}\right\}\) | \(\subseteq\) | \(\displaystyle S\) | Definition of Subset | |||||||||

\(\displaystyle \implies \ \ \) | \(\displaystyle \left\{ {x}\right\}\) | \(\in\) | \(\displaystyle \mathcal P \left({S}\right)\) | Definition of Power Set | |||||||||

\(\displaystyle \implies \ \ \) | \(\displaystyle T\) | \(\subseteq\) | \(\displaystyle \mathcal P \left({S}\right)\) | Definition of Subset |

Now we define the mapping $\phi: S \to T$:

- $\phi: S \to T: \forall x \in S: \phi \left({x}\right) = \left\{{x}\right\}$

$\phi$ is an injection:

- $\forall x, y \in S: \left\{{x}\right\} = \left\{{y}\right\} \implies x = y$ by definition of set equality

$\phi$ is a surjection:

- $\forall \left\{{x}\right\} \in T: \exists x \in S: \phi \left({x}\right) = \left\{{x}\right\}$

So $\phi$, being both an injection and a surjection, is a bijection by definition.

To show that $T \subset \mathcal P \left({S}\right)$, that is, is a proper subset of $\mathcal P \left({S}\right)$, we merely note that $\varnothing \in \mathcal P \left({S}\right)$ by Empty Set is Element of Power Set, but $\varnothing \notin T$.

Thus $T \subseteq \mathcal P \left({S}\right)$ but $\mathcal P \left({S}\right) \not \subseteq T$.

Hence the result.

$\blacksquare$