1
$\begingroup$

I found a problem in which I had to construct a bijection between set of all binary sequences and set of all subsets of $\mathbb N$. Is my solution correct? $\phi : 2^{\mathbb N}\to \{0,1\}^{\mathbb N}$ is defined by, $\phi(\{n_1,n_2,.....\})=$Binary sequence with $1$ only at the positions $n_k$ and $0 $ elsewhere.Is this correct?

$\endgroup$
3
  • $\begingroup$ The characteristic function of the set? Yes, that is a bijection. $\endgroup$ Nov 3, 2019 at 6:33
  • $\begingroup$ To me, $2$ is the same as $\{0,1\}$, especially when talking about sets. So $2^{\Bbb N}$ and $\{0,1\}^{\Bbb N}$ are the same too. $\endgroup$
    – Arthur
    Nov 3, 2019 at 7:09
  • $\begingroup$ By $2^{\mathbb N}$ I actually mean $P(\mathbb N)$. $\endgroup$ Nov 3, 2019 at 9:42

1 Answer 1

1
$\begingroup$

Yes, that is a bijection.

Define, for $A \subseteq \Bbb N$, $\varphi(A)=\chi_A \in \{0,1\}^{\Bbb N}$ where

$$\chi_A(n) = \begin{cases} 1 &\text{ if } n \in A\\ 0 &\text{ if } n \notin A\end{cases}$$

(Note that a binary sequence is just a function from $\Bbb N$ to $\{0,1\}$) and show $\varphi$ is a bijection:

$\chi_A = \chi_B$ (as functions) iff $A=B$ (as sets) and for any $x \in \{0,1\}^{\Bbb N}$ there is some $A \subseteq \Bbb N$ with $\varphi(A)=x$ (as functions).

Both are not hard, and exercises in the definitions. This sort of justifies the notation $2^X$ for the powerset of $X$ one sometimes sees.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .