uncountable set

An infinite set is “uncountable” or “uncountably infinite” when there are too many elements to be labeled with the set of natural numbers (e.g. $\mathbb{R}$).

A notable example of an uncountable set is $\mathcal{P}(\mathbb{N})$. The proof of its uncountability uses the diagonalization argument. To begin, we denote each element of the power set---a subset of $\mathbb{N}$---with a bitstring of size $|\mathbb{N}|$, with each digit representing whether the corresponding natural number is in the subset, so a subset beginning with 111 and ends with zeros denotes $\{0,1,2\}$. Let’s assume that there is a bijection $b:\mathbb{N}\to S$ and $S_n=b(n)$. We can now build a list of all bit strings starting from $S_0$

For each $S_i$, we flip one bit at index $i$, leading to a diagonal of changes. We can build a new bit string $D$ by concatenating these flipped bits. This new bit string $D$ cannot be found in $S$ since for any element $S_i$, $D$ is different by one bit at the $i$-th position. This contradicts the earlier assumption that $b$ exists, indicating that $\mathcal{P}(\mathbb{N})$ is not countable.