# Binary sequences and ${2}^{\mathbb{N}}$ have the same cardinality

I recently got the book "selected problems in real analysis", and I'm stuck solving the very first problem

$(u_n)$ is a binary sequence iff it only contains $0$ and $1$ in the sequence

Let $A$ be the set of all binary sequences

I have to prove that $A$ and ${2}^{\mathbb{N}}$ have the same cardinality, that is to say there exists a 1-1 function from one set to another

I've thought about maybe considering integers as base-2 numbers

• This has nothing to do with base two numbers. Imagine you are given a subset $S$ of $\mathbb N$. What 0-1 sequence (i.e. map $\mathbb N\to\{0,1\}$) can you define by making use of $S$ in the most natural way? – Hagen von Eitzen Apr 21 '13 at 12:59
• $0$ if n is even, $1$ if n is odd ? – Gabriel Romon Apr 21 '13 at 13:02
• @Gabriel: That has nothing in particular to do with $S$, though. – Cameron Buie Apr 21 '13 at 13:10

Hint: By $2^{\Bbb N}$ I presume you mean the power set of $\Bbb N$, rather than the set of functions $\Bbb N\to\mathbf{2},$ where $\mathbf{2}:=\{0,1\}$, as these are precisely the binary sequences, and there's nothing to prove. Have you heard of indicator functions?
• thanks, the function that to a subset $S$ associates the indicator of every integer toward $S$ should do. – Gabriel Romon Apr 21 '13 at 13:32
• If I understand you correctly, that will indeed be a bijection from $2^{\Bbb N}$ to the set of functions $\Bbb N\to\mathbf{2}.$ – Cameron Buie Apr 21 '13 at 15:51
• I don't know what you mean by "the indicator of every integer toward $S$." For any $S\subseteq\Bbb N$, the indicator function of $S$ is the function $\mathbf{1}_S:\Bbb N\to\{0,1\},$ given by $$\mathbf{1}_S(n)=\begin{cases}0 & n\notin S\\1 & n\in S.\end{cases}$$ that is, $\langle\mathbf{1}_S(n)\rangle_{n\in\Bbb N}$ is a binary sequence for each $S\in2^{\Bbb N}$. Your job is to show that the map $S\mapsto\langle\mathbf{1}_S(n)\rangle_{n\in\Bbb N}$ is a bijection from $2^{\Bbb N}$ to the set of binary sequences. – Cameron Buie Apr 21 '13 at 19:41
• Let $S$ be a subset of $\mathbb {N}$ Let $f:P(\mathbb {N}) \rightarrow A$ where $A$ is set of all binary sequences such that: $\forall i\in \mathbb {N}, (f(S)_i=0$ if $i\in S$ or$f(S)_i=1$ if $i\notin S$) – Gabriel Romon Apr 22 '13 at 15:29