Proving that the powerset of $\Bbb N$ is uncountable

Question

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?

Answer 1

$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).

Answer 2

I'll answer your last question first since it will give the answer to your other questions. The basic method for establishing that 2 sets have a 1:1 correspondence is constructing a bijection i.e. a one to one and onto function between them. For example, the set of integers $\mathbb{Z}$ is in one to one correspondence with the set of all rationals $\mathbb{Q}$ via the following mapping: f: $\mathbb{Z}\rightarrow\mathbb{Q}$ where for every a,b $\in$$\mathbb{Z}$, f(a,b) = $\frac{a}{b}$ where b$\neq$0.

Now let's consider the question of how to prove the powerset P($\mathbb{N}$) i.e. set of all subsets of $\mathbb{N}$ is in one to one correspondence with the set of all infinite binary sequences. First realize that every binary sequence, whether finite or infinite,is a Cartesian product of the 2 element set {0,1}. For example, all the four digit binary sequences are subsets of {0,1} x {0,1}. Write it out if you don't believe me.Therefore, since sequences are functions from the natural numbers into nonempty sets, the set of all binary sequences C can be written as the following set of functions from $\mathbb{N}$ into {0,1}: ${0,1}^\mathbb{N}$

We now need to define a characteristic function $\chi:S\rightarrow T$ of a subset S of $\mathbb{N}$:

$\chi = \begin{cases} \ 1 & s\in S \\ 0 & otherwise \end{cases}$

Let T = $(0,1)^\mathbb{N}$. I claim this is a bijection from $P(\mathbb{N})$ onto $(0,1)^\mathbb{N}$. This is well defined function since sequences of 0's and 1's are clearly generated.Is it onto? Yes,because clearly every member of the range of $\chi$ is equal to some member of $(0,1)^\mathbb{N}$.Is it one to one? Let $\chi(x)$=$\chi(y)$ where x,y $\in S\subseteq\mathbb{N}$.Let x$\in$ U and let y$\in$V where U,V $\in $ P($\mathbb{N}$) Then by the definition of the characteristic function, $\chi(x)$=$\chi(y)$ iff x =y. So this is clearly implies $\chi(U)$=$\chi(Y)$ iff U =V. So this is indeed a bijection from the powerset of $\mathbb{N}$ onto $(0,1)^\mathbb{N}$.

So lastly-which is the part I'm going to leave for you to do yourself-how do we prove now that powerset of $\mathbb{N}$ is in one to one correspondence with [0,1]$\subset\mathbb{R}$? There are 2 ways you can do this:

1) You have to demonstrate there exists a well defined bijection between powerset of $\mathbb{N}$ and [0,1]. It turns out this is not so easy,although it can be done.Hint for one method : For any $A \subset \mathbf{N}$ there is a natural sequence $(a_n)$ such that $a_n = 1$ if $n \in A$, $a_n=0$ if $n \notin A$. Then, we can view any $x\in (0,1)$ as $\sum_{n=1}^{\infty}\frac{a_n}{2^n}$, where $a_i \in \{0,1\}$.There's one more step after that to get the bijection.

2) If you're aware of the Cantor-Bernstien theorem, then this gives a much easier way:Produce 2 one to one functions; one from $(0,1)^\mathbb{N}$ into [0,1] and one going the other way. This proves there must be a bijection between them without explicit construction.

Ain't math fun?