# Cardinality of power set and binary sequence

Let $$A$$ be a set and $$P(A)$$ be the power set of $$A$$. Define $$B(A)$$ as the set of all functions $$F:A\rightarrow\{0,1\}$$. For example, $$B(\mathbb{N})$$ is the set of all binary sequences. Prove that $$P(A)$$ has the same cardinality as $$B(A)$$.

When $$A$$ is finite, this is easy to prove. I am interested in other cases; for instance when $$A$$ is countably infinite or uncountable. I am also a bit confused with the definition of $$B(A)$$. Could anyone help me with this one please?

• You need to find a bijection between these two sets.... – dmtri Oct 4 '19 at 4:59
• If $S$ is a subset of $A$ then an obvious map $F$ can be defined concerning the elements of $S$, ... – dmtri Oct 4 '19 at 5:02

The bijection is given by defining the function $$F_X:A\to\{0,1\}$$ with $$X\subseteq A$$ as: \begin{align} F_X(a)=\begin{cases} 1&\text{if a\in X}\\ 0&\text{if a\notin X} \end{cases} \end{align}

The things you have to show is that $$G:\mathcal P(A)\to B(A)$$ with $$G(X)=F_X$$ is a bijection.

• Small typo: it should be $a\in X$ instead of $a\in A$. – Niki Di Giano Oct 4 '19 at 6:06
• @NikiDiGiano Thanks, I had the roles of $X$ and $A$ reversed initially, seems I missed one – Vsotvep Oct 4 '19 at 9:06

Hint. Consider, for each subset $$B$$ of $$A$$, its characteristic function $$\chi_B$$ defined by $$\chi_B(x)= \begin{cases}1&\text{if x \in B}\\ 0&\text{otherwise}\end{cases}$$