Consider $S=\mathbb {N}$. We wish to show that $|\mathbb {N}|<|\mathcal {P}(\mathbb {N})|$. Proceed as follows: Seeking a contradiction, suppose that they are equinumerous and imagine a bijection between every element of $\mathbb {N}$ and $\mathcal {P}(\mathbb {N})$. Call a natural number selfish if by your bijection it is pared with a set containing itself. Call a natural number nonselfish if it is paired with a set not containing itself.

We know that $\mathbb {N}$ is countable and that $\mathcal {P}(\mathbb {N})$ is uncountable. Define:

On the other hand there are also aleph numbers. Here $$\aleph _0 := |\mathbb {N}|$$ but $\aleph _1$ is defined to be the smallest infinite cardinal number larger than $\aleph _0$. In general, $\aleph _n$ is the smallest infinite cardinal number larger than $\aleph _{n-1}$. So from this definition we find: $$\aleph _0 \le \aleph _1 \le \aleph _2 \le \aleph _3 \le \cdots$$

Hilbert’s first problem

In 1900 Hilbert made a list of problems to guide the mathematicians of the 20th Century. Here is the first problem on the list:

What is this so-called continuum hypothesis? It states $$\aleph _1 = \beth _1 = |\mathbb {R}|.$$

Hilbert’s second problem

I speculate that finding the “holes” in Euclid’s arguments led Hilbert to question the validity of our own proofs. This speculation is supported by the fact that in 1900 the second problem in Hilbert’s list of problems was:

With Hilbert’s second problem in mind, in 1901 Bertrand Russell showed that the naive set theory of Cantor cannot be used to answer Hilbert’s second problem. Russell proposed that one consider the set of all sets that do not contain themselves.

The reader should rest assured that the foundations of mathematics will not come collapsing upon our heads. Russell himself has a resolution based on something called type theory, though we cannot discuss this at the moment.

(In)completeness

Now we will turn our attention to Kurt Gödel. In 1931, Gödel proved his (first) incompleteness theorem. To paraphrase:

In 1940, Gödel proved that the continuum hypothesis cannot be disproved using the standard axioms of set theory. Around 1964, Paul Cohen showed that the continuum hypothesis cannot be proved using the standard axioms of set theory. To use the language of vector-spaces,

Hence the continuum hypothesis is one of these unprovable statements. There are in fact, many others. Once upon a time, mathematical statements were either true or false. Now we have a third option, the statement could be undecidable. We have matured much since the birth of numbers.