10. Not all sets are countable

Not all sets are countable

title: Not in exam.

The power set $P(\mathbb{N})$ of $\mathbb{N}$ is not countable:

$$\neg \exists f(f\text{ is a bijection between }\mathbb{N}\text{ and }P(\mathbb{N}))$$

There are more subsets of numbers than numbers.

We can show that $\forall f(\text{if }f:\mathbb{N}\to P(\mathbb{N})\text{ then }f\text{ is not onto})$:

• Let $f:\mathbb{N}\to P(\mathbb{N})$ be an arbitrary function.
• Then, for every $n\in \mathbb{N}$, $f(n)$ is a subset of $\mathbb{N}$.
• Now take the following subset $D_f$ of $\mathbb{N}$: $\boxed{D_f=\{n\in \mathbb{N}|n\notin f(n)\}}$

We show that $D_f$ is not in the range of $f$, that is, for every $n\in \mathbb{N}$, $D_f\ne f(n)$: Take an arbitrary $n\in \mathbb{N}$, then there are two cases, either $n\in D_f$ or $n\notin D_f$.

• If $n\in D_f$, then $n$ shoudl have the property describing $D_f$, so $n\notin f(n)⇝\boxed{D_f⊈f(n)}$
• If $n\notin D_f$, then the property describing $D_f$ does not hold for $n$, so $n\in f(n)⇝\boxed{f(n)\notin D_f}$