Power Set

set-theory

Definition

Power Set

A power set $\mathcal{P}(S)$ is a set of all subsets of a set $S$ and defined as:

$$\mathcal{P}(S)=\{X\mid X\subseteq S\}$$

Examples

$\mathcal{P}(\{1,2,3\})$

$$\mathcal{P}(\{1,2,3\})=\{\varnothing ,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}$$

$2^S$

Let $2=\{0,1\}$. Then

$$2^S=\{f\mid f:S\to 2\}=\{f\mid f\text{ is a function from }S\text{ to }\{0,1\}\}$$

Each function $f:S\to 2$ is the indicator function of a unique subset $X\subseteq S$, so $2^S$ and $\mathcal{P}(S)$ are in bijection.