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

Thanks for your help

  • $\begingroup$ 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? $\endgroup$ – Hagen von Eitzen Apr 21 '13 at 12:59
  • $\begingroup$ $0$ if n is even, $1$ if n is odd ? $\endgroup$ – Gabriel Romon Apr 21 '13 at 13:02
  • $\begingroup$ @Gabriel: That has nothing in particular to do with $S$, though. $\endgroup$ – 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?

  • $\begingroup$ thanks, the function that to a subset $S$ associates the indicator of every integer toward $S$ should do. $\endgroup$ – Gabriel Romon Apr 21 '13 at 13:32
  • $\begingroup$ 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}.$ $\endgroup$ – Cameron Buie Apr 21 '13 at 15:51
  • $\begingroup$ I meant the function that to a subset S associates the sequence of the values of the indicator of every integer toward S $\endgroup$ – Gabriel Romon Apr 21 '13 at 19:23
  • $\begingroup$ 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. $\endgroup$ – Cameron Buie Apr 21 '13 at 19:41
  • $\begingroup$ 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$) $\endgroup$ – Gabriel Romon Apr 22 '13 at 15:29

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.