The question I'm facing off with:
(a) Consider the set $A$ defined as the set of all subsets of $\Bbb N$: $A = ${$B : B \subset \Bbb N$}. Show that $A$ is in one-to-one correspondence with the set of all (infinite) binary sequences: $C = \{ b_1, b_2, b_3,… | b_i \in \{ 0,1 \} \}$.
To do this I tried to assign each number in $\Bbb N$ a unique binary sequence (e.g. $5 = 001, 9 = 101, 59 = 001101$). Thus, any subset of $\Bbb N$ would translate to a unique sequence of binary numbers in $C$. This has a few issues, however. A subset of $\Bbb N$ could be finite, and my method would thus translate that subset to a finite binary sequence in $C$, which can't happen because $C$ is the set of all infinite binary sequences. How do I correct this? Just hints please. I'm also running into a notational issue, which I would like some clarification on.
I'm not sure I understand the notation used for $C$; are $b_1, b_2, …$ infinite sequences themselves, or do they each individually represent either a 0 or a 1?
(b) Show that $C$ is in one-to-one correspondence with $[0, 1]$. For this one I took the same approach, unfortunately to no avail. I'm confident that whatever method I use to attack the first part of the question, I can easily use to attack the second. Which leads me to my next question: Is there any general method in showing that two sets have a one-to-one correspondence with each other?
Best Answer
$C$ is the set of all infinite binary sequences - that is, an element of $C$ looks like $(b_1, b_2, b_3, . . .)$, where each $b_i$ is either $0$ or $1$. So for instance $(0, 1, 0, 1, 0, 1, . . . )$ is an element of $C$, and in this case $b_1=0, b_2=1, b_3=0, . . .$
Re: your first question, you're trying a bit too hard - there's a simpler way. Suppose I have a set $X\subseteq \mathbb{N}$, and you're trying to figure out what it is. The "brute force" approache would be to ask a series of questions:
"Is $1\in X$?"
"Is $2\in X$?"
"Is $3\in X$?"
Etc.
Each of these questions has a yes/no answer, and $X$ is determined by what my answers to each of these questions is. Do you see a way to use this idea to associate to $X$ a sequence of $0$s and $1$s?
For your second question, here's a hint: think about decimal (or other base!) expansions. This won't help you build a bijection right off, but it will help you build an injection from $C$ to $[0, 1]$, and a surjection from $C$ to $[0, 1]$, at which point you'll be able to use the Cantor-Bernstein theorem to show that there is a bijection (this theorem, I think, is the closest thing to an answer you'll get for your sub-question about whether there's a "general way" to show a bijection exists).