Power Sets are Equinumerous

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $x$ and $y$ be sets such that $x \sim y$.


Then:

$\mathcal P \left({ x }\right) \sim \mathcal P \left({ y }\right)$


Proof 1

Let $f : x \to y$ be a bijection.


Let $F$ send each $z \in \mathcal P \left({ x }\right) \mapsto \operatorname{Im} \left({ z }\right)$ where $\operatorname{Im} \left({ z }\right)$ denotes the image of the subset $z$ under $f$.


It follows that $F$ is a mapping whose domain is $\mathcal P \left({ x }\right)$.

Moreover, the range of $F$ is the collection of all images of $z$.

Each image is a subset of $y$ and thus:

$F : \mathcal P \left({ x }\right) \to \mathcal P \left({ y }\right)$


Suppose that $F \left({ a }\right) = F \left({ b }\right)$.

Then if $z \in a$ then $f \left({ z }\right) \in F \left({ a }\right)$.

But then, $f \left({ z }\right) = f \left({ w }\right)$ for some $w \in y$.

Thus, $z = w$ and $w \in y$.

Therefore, $z = y$ and $F$ is injective.


Suppose that $a \in \mathcal P \left({ y }\right)$.

Let $b$ be the preimage of $a$ with respect to the $f$ function.

It follows that $b$ is a subset of $x$.

$F \left({ b }\right) = a$ and $a$ is in the range of $F$.


Generalizing for all $a \in \mathcal P \left({ y }\right)$, it follows that:

$F : \mathcal P \left({ x }\right) \to \mathcal P \left({ y }\right)$ is a bijection.

$\blacksquare$


Proof using covariant power set functor

Let $\mathcal P$ denote the covariant power set functor.

Let $f : x \to y$ be a bijection.

By Covariant Functors Preserve Isomorphisms, $\mathcal P(f) : \mathcal P(x) \to \mathcal P(y)$ is a bijection.

$\blacksquare$


Proof using contravariant power set functor

Let $\overline {\mathcal P}$ denote the contravariant power set functor.

Let $f : x \to y$ be a bijection.

By Contravariant Functors Preserve Isomorphisms, $\overline {\mathcal P}(f) : \mathcal P(y) \to \mathcal P(x)$ is a bijection.

$\blacksquare$


Sources