 # There is no greatest cardinal

We have seen in this article several sets that are infinite and countable. Namely, the set of natural numbers $$\mathbb N$$, the set of integers $$\mathbb Z$$, the set of rational numbers $$\mathbb Q$$. We have seen that the product $$\mathbb N \times \mathbb N$$ is also countable. The question then arises, “Are all infinite sets countable?”.

The answer is negative and we prove that $$\mathbb R$$ is not countable.

### The set of all reals $$\mathbb R$$ is not countable

Suppose for the sake of contradiction that $$\mathbb R$$ is countable and that $$\mathbb R = \{x_n \ | \ n \in \mathbb N\}$$, the $$x_n$$ being all distinct. We build by induction two sequences $$(a_n)_{n \in \mathbb N}$$ increasing and $$(b_n)_{n \in \mathbb N}$$ decreasing such that:

• $$a_n < b_n$$ for all $$n \in \mathbb N$$,
• $$\vert a_n – b_n \vert$$ converges to zero,
• and $$x_n \notin [a_{n+1},b_{n+1}]$$.

Let’s start with $$a_0 = 0$$ and $$b_0 = 1$$ and assume that we have built $$a_0, \dots, a_n$$ and $$b_0, \dots, b_n$$ satisfying above properties. If $$x_n \notin (a_n,b_n)$$ we take $a_{n+1}=a_n+\frac{b_n-a_n}{4}, \, b_{n+1}=b_n-\frac{b_n-a_n}{4}$ while if $$x_n \in (a_n,b_n)$$ we take $a_{n+1}=a_n+\frac{x_n-a_n}{4}, \, b_{n+1}=x_n-\frac{x_n-a_n}{4}$ One can verify that $$a_n < a_{n+1}$$, $$b_{n+1} < b_n$$, $$a_{n+1} < b_{n+1}$$, $$\vert a_{n+1} - b_{n+1}\vert \le \frac{\vert a_n - b_n \vert}{2}$$ and $$x_n \notin [a_{n+1},b_{n+1}]$$. The induction step is complete. Considering the properties of $$(a_n)$$ and $$(b_n)$$, those two sequences converge to a real number that we denote by $$\lambda$$. By hypothesis, there exists $$N \in \mathbb N$$ such that $$\lambda = x_N$$. We also have $$a_{N+1} < \lambda < b_{N+1}$$ in contradiction with $$x_N \notin [a_{N+1},b_{N+1}]$$. Finally, $$\mathbb R$$ cannot be countable.

### Cantor’s theorem

So, the cardinality of $$\mathbb R$$ is greater than the one of $$\mathbb N$$. Can one find a set with a cardinal greater than the one of $$\mathbb R$$? The answer is positive. More generally, Cantor’s theorem states that, for any set $$A$$, the set of all subsets of $$A$$ (the power set of $$A$$) has a strictly greater cardinality than $$A$$ itself. For the proof of Cantor’s theorem, suppose that $$f$$ is a surjection from $$A$$ onto the power set of $$A$$, $$\mathcal P \left({A}\right)$$ and consider $B = \{x \in A \ | \ x \notin f(x)\}$ By hypothesis, there exists $$y \in A$$ such that $$B=f(y)$$. We then have the contradiction $y \in B \Leftrightarrow y \notin f(y) \Leftrightarrow y \notin B$ Hence $$\mathcal P \left({A}\right)$$ has a cardinality strictly greater than $$A$$.

There is no greatest cardinal.