3
$\begingroup$

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?

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

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.

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

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} $$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.