# $2^{\mathbb{N}}$ is uncountable -- Power Set of Natural Numbers

Proof: Assume it is countable. Then we can arrange the sets in order (an enumeration) $A_1, A_2, A_3, ...$. Now construct the set $B = \{i \in \mathbb{N} \ | \ i \notin A_i \}$. Then $B=A_j$ for some $j$, a contradiction.

This was the proof given in class and feels off. Can anyone elaborate or tell me it's wrong?

• This has nothing to do with measure theory, so I removed the tag.
– Pedro
Apr 10, 2013 at 4:22
• How do we know that B isn't empty as there is no such i? That would be the part that I'd want elaborated in a sense. Apr 10, 2013 at 4:23
• @JBKing It can't be empty because the empty set is a subset of $2^{\mathbb{N}}$. If this is countable, the empty set is then $A_j$ for some $j$. Certainly $j \not\in A_j$, so $j\in B$. The empty set is not different to any other set in this proof. Apr 10, 2013 at 4:26

It’s the standard argument; there’s nothing wrong with it, apart from the fact that there is no need to cast it as a proof by contradiction. The real idea is simply that if you take any list of subsets of $\Bbb N$ ordered by the positive integers $-$ i.e., a list of the form $A_1,A_2,A_3,\dots$ $-$ there is guaranteed to be a subset of $\Bbb N$ not in your list.

Suppose that we’ve proved that statement: then it follows immediately that it is impossible to list all subsets of $\Bbb N$ in a $1$-$2$-$3$ enumeration of this kind and hence that $\wp(\Bbb N)$ must be uncountable: there is no bijection from $\Bbb N$ to $\wp(\Bbb N)$, because there isn’t even a map from $\Bbb N$ onto $\wp(\Bbb N)$.

The proof of the statement is exactly what you were shown. I’m going to construct a set $B\subseteq\Bbb N$ by going through the positive integers one at a time and deciding whether to put it into $B$ or leave it out. If $k\notin A_k$, I’ll put $k$ into $B$; otherwise, if $k\in A_k$, I’ll leave $k$ out of $B$. In this way I make sure that the sets $B$ and $A_k$ disagree about $k$: exactly one of them contains $k$. In other words, one of them contains $k$, and the other does not. I don’t have to know which is which to recognize that this means that $B\ne A_k$: $B$ and $A_k$ definitely don’t have exactly the same elements, precisely because they disagree at $k$.

The argument that you were given just described this same set $B$ more concisely: $$B=\{k\in\Bbb N:k\notin A_k\}\;.\tag{1}$$

$(1)$ just says very briefly in symbols what I said at much greater length in words when I wrote this:

I’m going to construct a set $B\subseteq\Bbb N$ by going through the positive integers one at a time and deciding whether to put it into $B$ or leave it out. If $k\notin A_k$, I’ll put $k$ into $B$; otherwise, if $k\in A_k$, I’ll leave $k$ out of $B$.

• Thanks, Professor Scott. This makes sense-- I guess there was just a lot of information packaged in that set construction. I do have a question that you sound like you may be able to answer. Are these problems addressed the same way with ZFC set theory as Cantor's original diagonalization arguments? This is a diagonal argument, isn't it? Isn't the problem with naive set theory that there are inherit contradictions when we only require sets to be elements such that a statement is true ($k \notin A_k$)? So even if it works in this particular case, it might be normal that is seems weird? Apr 10, 2013 at 19:28
• @Questioneer: You’re welcome. Yes, this a classic diagonalization argument. There is no problem here: the definition of $B$ is an instance of restricted comprehension, using some property to pick out a subset of something ($\Bbb N$) already known to be a set. Russell’s paradox arises from the use of unrestricted comprehension. It’s not unusual, I think, to find the argument a bit strange at first, but it’s not at all problematic. ‘[T]his particular case’ is normal, not unusual. Apr 10, 2013 at 19:38
• I am a bit confused here. Can't B equal to some other $A_j$ ? Do you mean $B$ is a compliment of $A_k$ where the universe is natural numbers? Apr 16, 2014 at 12:18