# A difficulty in the proof that $2^{\mathbb{N}}$ is uncountable. [duplicate]

This is the explanation of the book, but for me I did not catch the idea of the set $v$, and I need a numerical example for it and the set $u_{k}$, could anyone help me please?

Is there a systematic way by which I can write $u_{k}$ so that $u_{k}$ give me all subsets of $\mathbb{N}$?

## marked as duplicate by Did, user91500, Asaf Karagila♦ set-theory StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Aug 9 '17 at 10:45

• For example, if $u_1 = \{2\}$, $u_2=\{2,4\}$, $u_3=\{2,4,6\}$ and so on, we can define $v=\{1,3,5,\cdots\}$ because $1\notin u_1$,$2\in u_2$, $3\notin u_3$, etc. As the author said, the definition of $v$ depends on the particular enumeration $u_1,u_2,\cdots$. – Rodrigo Dias Aug 9 '17 at 9:34
• @rldias ... or rather, it would depend on the particular enumeration. ;) – user228113 Aug 9 '17 at 9:35
• Do note that the elements of $2^\Bbb N$ are not the $u_k$'s, but the book is implicitly using the fact that the set of all functions from $\Bbb N$ to $2=\{0,1\}$, namely $2^\Bbb N$, is in bijection with $\mathcal P(\Bbb N),$ i.e. the set of all subsets of $\Bbb N$ (the $u_k$'s). – Vincenzo Oliva Aug 9 '17 at 9:44
• "Is there a systematic way by which I can write $u_k$ so that $u_k$ give me all subsets of $\mathbb N$? " - No, that's the point. It's what the proof shows, it constructs given such a candidate a subset of $\mathbb N$ that is not one of $u_k$. – skyking Aug 10 '17 at 6:00

The idea is to construct a set which is none of $u_k$. This is done by assuring that $k \in v \leftrightarrow k\notin u_k$, this means that for any $k$ that $u_k\ne v$.

Note that the proof assumes there is an enumeration $u_k$ to start with and it shows that there is a $v\in 2^{\mathbb N}$ that is not part of the enumeration.

In fact the same argument is used to show that $2^X$ is larger than $X$. Which can be used to create an concrete example. For example assume that $X=\{0,1,2\}$ and suppose that we have an surjective mapping from $X$ to $2^X$ which would mean that we have three sets $u_0$, $u_1$ and $u_2$ which would make up $2^X$. Now take for example:

$$u_0 = \{1,2\}$$ $$u_1 = \{0,1\}$$ $$u_2 = \{0\}$$

Now we construct $v$ from this and we have $0\in v\leftrightarrow 0\notin u_0$, but $0\notin u_0$ so $0\in v$. In the same way we find that $1\notin v$ (because $1\in u_1$) and $2\in v$. So we have $v=\{0,2\}$ which is none of $u_0, u_1, u_2$.

What confuses you is possibly the appeal to contradiction, which is by no means necessary.

The book actually proves the following statement:

Suppose $u_1,u_2,\dots,u_n,\dotsc$ is a sequence of  (pairwise distinct) subsets of $N$. Then there exists a subset $v$ of $N$ such that $v\ne u_n$, for every $n$.

The subset is built from the given sequence by $$v=\{k: k\notin u_k\}$$ Indeed, let $n$ be a natural number: either $n\in v$ or $n\notin v$.

In the first case, $n\notin u_n$ by the very definition of $v$, so $v\ne u_n$; in the second case, $n\in u_n$, again by the very definition of $v$, so $v\ne u_n$. In both cases $v\ne u_n$.

In particular, no countable subset of $2^N$ can equal $2^N$, because from a countable subset we can produce an element of $2^N$ that is not in the given subset.

The more general statement that $|2^X|>|X|$, for every set $X$, can be proved similarly. Since, clearly, $|X|\le|2^X|$, the assert follows from

There is no surjective map $f\colon X\to 2^X$.

Indeed, suppose $f\colon X\to 2^X$ is any map. Define $$V=\{x\in X:x\notin f(x)\}$$ Let us show that $V\ne f(x)$, for every $x$. Indeed, for $x\in X$ there are two cases

1. $x\in V$
2. $x\notin V$

In the first case $x\notin f(x)$, so $V\ne f(x)$. In the second case, $x\in f(x)$, so $V\ne f(x)$.

Therefore $f$ is not surjective.

The idea of the proof, as you see, is the same (and goes back to Cantor himself).

• I think in the third line from below, the second statement $x \in f(x)$. – Intuition Aug 9 '17 at 16:24
• @Intuition Yes, sorry for the typo – egreg Aug 9 '17 at 16:38
• why u said that $u_{1}, u_{2},...$ are pairwise distinct? – Intuition Aug 9 '17 at 19:54
• @Intuition It's not really necessary, so you can add the clause or not, at your pleasure. – egreg Aug 9 '17 at 20:00