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? Because it represents all possible binary choices for the elements in $A$.
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.

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

$$

{ 0,1 }^{A} \mapsto 2^{A}

$\{0,1\}^A$ represents the set of all functions from set $A$ to the set $\{ 0,1 \}$. $2^{A}$ represents the [[power set]] – the set of all subsets of $A$ → 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$. $\implies$ There is a [[bijective|bijection]] between $2^{A}$ and the set of all functions from $A$ to $\{ 0,1 \}$.

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