Cardinality of Power Set is Invariant

From ProofWiki
Jump to: navigation, search

Theorem

Let $X, Y$ be sets.

Let $\left\vert{X}\right\vert = \left\vert{Y}\right\vert$

where $\left\vert{X}\right\vert$ denotes the cardinality of $X$.


Then:

$\left\vert{\mathcal P \left({X}\right)}\right\vert = \left\vert{\mathcal P \left({Y}\right)}\right\vert$

where $\mathcal P \left({X}\right)$ denotes the power set of $X$.


Proof

By definition of cardinality:

$X \sim Y$

where $\sim$ denotes the set equivalence.

Then by definition of set equivalence:

there exists a bijection $f: X \to Y$

By definition of bijection

$f$ is an injection and a surjection.

By Mapping Induced on Power Set by Injection is Injection:

the direct image mapping $f^\to:\mathcal P \left({X}\right) \to \mathcal P \left({Y}\right)$ is an injection.

By Mapping Induced on Power Set by Surjection is Surjection

$f^\to$ is a surjection.

Then by definition of bijection:

$f^\to:\mathcal P \left({X}\right) \to \mathcal P \left({Y}\right)$ is a bijection.

Hence by definition of set equivalence:

$\mathcal P \left({X}\right) \sim \mathcal P \left({Y}\right)$

Thus the result by definition of cardinality:

$\left\vert{\mathcal P \left({X}\right)}\right\vert = \left\vert{\mathcal P \left({Y}\right)}\right\vert$

$\blacksquare$


Sources