This question already has an answer here:

enter image description here

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 Aug 9 '17 at 10:45

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ 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$. $\endgroup$ – Rodrigo Dias Aug 9 '17 at 9:34
  • $\begingroup$ @rldias ... or rather, it would depend on the particular enumeration. ;) $\endgroup$ – user228113 Aug 9 '17 at 9:35
  • 1
    $\begingroup$ 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). $\endgroup$ – Vincenzo Oliva Aug 9 '17 at 9:44
  • 2
    $\begingroup$ "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$. $\endgroup$ – 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).

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.