power set

Power set

The power set $\mathcal{P}(A)$ is the set of all subsets of $A$, i.e.:

$$\mathcal{P}(A)=\{C\mid C\subseteq A\}$$

It can also be written as $2^A$.
Why:

The power set is isomorphic to the set of all functions from $A$ to $\{0,1\}$ Proposition:

\mathcal{P}(A) \cong { 0,1 }^{A}

Let $2=\{0,1\}$. For any set $A$, the power set $\mathcal{P}(A)$ is a bijection with the set of all function $A\to 2$ (i.e. $\{0,1{\}}^A$).
Intuitively: $2$ represents a binary choice: whether to include an element in a subset or not. $A$ represents the elements we can choose from.
For example: $\{1,2\}$ has the subsets $\varnothing ,\{1\},\{2\},\{1,2\}$, which can be represented as $00,01,10,11$ in binary, i.e. $2^2=4$ subsets.

→ For any subset of $A$, we can define a function $f:A\to \{0,1\}$ that maps elements in the subset to $1$ and the rest to $0$.
→ Conversely, for any function $f:A\to \{0,1\}$, we can define a subset of $A$ that contains all elements that are mapped to $1$.
$⟹$ There is a bijection between $2^A$ and the set of all functions from $A$ to $\{0,1\}$.

(insert rigorous proof here)

$⟹$ The cardinality of the power set of a finite set $A$: $|\mathcal{P}(A)|=2^{|A|}$.

The sum of all binomial coefficients for fixed $n$ (row of Pascal’s triangle) equals $2^n$

$$\sum _{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)=2^n$$

This makes intuitive sense when thinking about sets: $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ counts the ways to choose $k$ items from $n$ items, and summing over all possible $k$ gives us the total number of possible subsets of an $n$-element set, which is $2^n$. Each element either is or isn’t in the subset, giving us two choices for each of the $n$ elements → power set.

Link to original