Free, open-source online mathematics for students, teachers and workers

Alice and Bob are discussing how big is the set $\mathcal{P}(\mathbb{N})$, that is, the collection of all subsets of the natural numbers. The more they think about it, the more they realise this collection is really huge! Examples and examples of subsets of $\mathbb{N}$ come to their minds:

  • The even numbers: $2 \mathbb{N}=\{0,2,4,6,8,10,12,14,...\}$
  • The numbers between 50 and 83: $[50,83]=\{50, 51, 52,...,81, 82,83\}$
  • The empty subset: $\varnothing=\{\}$
  • The prime numbers: $Prime=\{2,3,5,7,11,13,17,19,23,29,31,...\}$
  • Bob's age (just one element!): $BobAge=\{14\}$
  • The nonprime numbers: $NonPrime=\{0,1,4,6,8,9,10,12,14,15,16,18,20,21,22,24,25,26,27,28,30,32,...\}$
  • The set of lucky numbers among Alice and Bob's friends: $LuckyNumbers=\{3,4,5,6,7,12,13,16,99,777,12345\}$
  • All the numbers! $\mathbb{N}=\{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,...\}$
  • The powers of $2$: $PowersTwo=\{1,2,4,8,16,32,64,128,256,512,1024,...\}$
  • ... and so on ...

Alice and Bob wonder whether this collection is countable, that is, whether one may hypothetically write down all the subsets of $\mathbb{N}$ in a list without leaving any unnoticed. Alice is somewhat prone to believe that this is not possible; Bob, on the other hand, is sure about this collection being countable and also says he conceives a strategy to achieve this ordering

"Show me then!" - says Alice

And Bob takes a piece of paper and starts to write down

$$2 \mathbb{N}=\{0,2,4,6,8,10,12,14,...\}$$
$$[50,83]=\{50, 51, 52,...,81, 82,83\}$$
$$\varnothing=\{\}$$
$$Prime=\{2,3,5,7,11,13,17,19,23,29,31,...\}$$
$$BobAge=\{14\}$$
$$NonPrime=\{0,1,4,6,8,9,10,12,14,15,16,18,20,21,22,24,25,26,27,28,30,32,...\}$$
$$LuckyNumbers=\{3,4,5,6,7,12,13,16,99,777,12345\}$$
$$\mathbb{N}=\{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,...\}$$
$$PowersTwo=\{1,2,4,8,16,32,64,128,256,512,1024,...\}$$
$$...$$
$$...$$
$$...$$

"Oh, this gonna be dull" - thinks Alice. She's not very confident about Bob being able to write down infinitely many items in a piece of paper... but even if he is able, she won't check the infinite list to ensure no subset of $\mathbb{N}$ is left. "There must be a smarter way"

And she remembers - Cantor's Theorem. How could she have overlooked it?

Yes, when trying to count the subsets of $\mathbb{N}$, Bob is building a map $g:\mathbb{N}\longrightarrow\mathcal{P}(\mathbb{N})$. He hasn't ended yet, but says that has a rule to write down everything

$a$$g(a)$
$0$$2 \mathbb{N}=\{0,2,4,6,8,10,12,14,...\}$
$1$$[50,83]=\{50, 51, 52,...,81, 82,83\}$
$2$$\varnothing=\{\}$
$3$$Prime=\{2,3,5,7,11,13,17,19,23,29,31,...\}$
$4$$BobAge=\{14\}$
$5$$NonPrime=\{0,1,4,6,8,9,10,12,14,15,16,18,20,21,22,24,25,26,27,28,30,32,...\}$
$6$$LuckyNumbers=\{3,4,5,6,7,12,13,16,99,777,12345\}$
$7$$\mathbb{N}=\{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,...\}$
$8$$PowersTwo=\{1,2,4,8,16,32,64,128,256,512,1024,...\}$
$...$$...$
$...$$...$
$...$$...$

and according to Cantor's Theorem, $g$ will never be surjective, that is, Bob won't be able to write down all subsets of $\mathbb{N}$! She's right! Come on, let's follow the argument of Cantor's proof.

Among the natural numbers, the are some that belong to its associated subset, but others not

$a$$g(a)$$a\in g(a)$
$0$$2 \mathbb{N}=\{\mathbf{\color{#00C853}{0}},2,4,6,8,10,12,14,...\}$check_box
$1$$[50,83]=\{50, 51, 52,...,81, 82,83\}$indeterminate_check_box
$2$$\varnothing=\{\}$indeterminate_check_box
$3$$Prime=\{2,\mathbf{\color{#00C853}{3}},5,7,11,13,17,19,23,29,31,...\}$check_box
$4$$BobAge=\{14\}$indeterminate_check_box
$5$$NonPrime=\{0,1,4,6,8,9,10,12,14,15,16,18,20,21,22,24,25,26,27,28,30,32,...\}$indeterminate_check_box
$6$$LuckyNumbers=\{3,4,5,\mathbf{\color{#00C853}{6}},7,12,13,16,99,777,12345\}$check_box
$7$$\mathbb{N}=\{0,1,2,3,4,5,6,\mathbf{\color{#00C853}{7}},8,9,10,11,12,13,14,15,...\}$check_box
$8$$PowersTwo=\{1,2,4,\mathbf{\color{#00C853}{8}},16,32,64,128,256,512,1024,...\}$check_box
$...$$...$check_box_outline_blank
$...$$...$check_box_outline_blank
$...$$...$check_box_outline_blank

So we have to focus on the set of "red numbers"

$$\color{#DD2C00}{B=\{1,2,4,5,...\}}$$

"Bob! I know this subset is not contained in your list!"

Bob rolled his eyes - "How do you know, if I haven't even finished writing down?"

But Alice explains her argument. "Imagine $B$ is in the list, as the image of some number $b$. Now, is $b$ a 'green number' or a 'red number'?"

$b$$B=\{1,2,4,5,...\}$check_box_outline_blank
$b$$B=\{1,2,4,5,...,\mathbf{\color{#00C853}{b}},...\}$check_box
$b$$B=\{1,2,4,5,...\}$indeterminate_check_box

"Neither makes sense, because $B$ is exactly the set of red numbers!" said Alice. "Isn't this clever?"

"Yikes, you're right!", said Bob finally...