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

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?

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

• It seems that I'm only able to establish a surjection... Using the method you recommended, decimal expansions such as $0.001$ and $0.003$ will translate to the same infinite binary sequences. Unfortunately, I have not yet been exposed to the Cantor-Bernstein theorem. – user312437 Jun 8 '16 at 20:05
• @ColeButler Alright, here's an almost bijection: binary expansions! Send a binary sequence $(b_1, b_2, b_3, . . .)$ to the real $0.b_1b_2b_3...$ in binary. This is a bijection . . . except for those reals that have two binary expansions (e.g. $0.011111...=0.100000...$ in binary, analogously to how $0.099999...=0.100000...$ in decimal). This can be fixed, though, with a bit of effort (it doesn't take the full strength of CB). – Noah Schweber Jun 8 '16 at 20:12
• So a way of making this "almost bijection" that you proposed (surjection, right?) a bijection? (I apologize if I seem a little distant, as this question is part of the first few chapters of a probability and statistics book I'm reading.) – user312437 Jun 8 '16 at 20:39

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?

• Small quibble: "$(0,1)$" should really be "$\{0, 1\}$", especially since each appears in the OP's question. (Well, $[0, 1]$ rather than $(0, 1)$, but still.) – Noah Schweber Jun 8 '16 at 21:53
• I think I'm starting to understand this. The "fun" comes in when we are trying to determine a bijective function between two sets. In 1), a bijective function has to go both ways, and I'm having trouble understanding how a decimal expansion such as 0.6, can be generated by the sum you defined. It will certainly generate unique decimal expansions for every unique binary sequence, but I am having trouble visualizing it the other way around. – user312437 Jun 9 '16 at 1:31
• As for 2), I think I have a few ideas. A one-to-one function from $C$ into $[0, 1]$ would look something like the summation you defined. For any binary sequence $a_1 a_2 a_3...$, if $a_i = 1$, then this would generate a decimal expansion of the form $\sum^\inf_{i=1} \frac {na_n}{10^n}$. For example, $110100...$ would correspond to $0.120300...$ and so on. A one-to-one function in the reverse direction would, depending on the decimal expansion, assign each digit, let's call it $n$, a unique $n+1$ binary sequence. So $0.120300..$ would have the binary expansion $011100100100...$. – user312437 Jun 9 '16 at 1:39
• Am I looking at this correctly or am I completely off? – user312437 Jun 9 '16 at 1:41