Notation for a power set?

Question

I am confused by the notation in a homework problem. I think it relates to Cantor Diagonalisation but want to know I am working with a power set first. Does this notation describe a power set?

{0,1}^A

Thank you.

Answer 1

Yes, it does, the idea is that whenever $A,B$ are sets, the notation $B^A$ is used to describe the set of all functions from $A$ to $B$. Now, in your case $B=\{0,1\}$, so every element of $B^A$ is a function with codomain $\{0,1\}$.

Now, I claim that there is a natural bijection between $\mathcal P(A)$ and ${\{0,1\}}^A$. Namely, given a subset $F$ of $A$, consider the function $\chi_F:A\to\{0,1\}$ (called the characteristic function of $F$) given by $$ \chi_F(x)=\begin{cases}1 \quad\text{if }x\in F,\\0\quad\text{if }x\not\in F.\end{cases}$$ Conversely, given a function $g\in {\{0,1\}}^A$, consider the set $D_g=\{x\in A\mid g(x)=1\}$.

You can then check that in fact for any $F\in\mathcal P(A)$, we have $D_{\chi_F}=F$ (i.e., given $F$, you construct the function $\chi_F$ and then the set $D_{\chi_F}$, and given any $g\in {\{0,1\}}^A$, we have $\chi_{D_g}=g$, so that the maps $F\mapsto\chi_F$ and $g\mapsto D_g$ are in fact inverses of each other, thus bijections.

In practice however, one often identifies $F$ with $\chi_F$, its characteristic function. Also, the set $\{0,1\}$ is equal to $2$, so that you can also write $2^A$ for $\{0,1\}^A$.