Théorème de Cantor

Publié le October 5, 2019
Tags: maths, ensemble, diagonalisation, équipotence

Énoncé et preuve

Aucun ensemble n’est en bijection avec l’ensemble de ses parties

Ce théorème est trvivial dans les ensembles finis, car, si AA est in ensemble fini, 𝖼𝖺𝗋𝖽((A))=2𝖼𝖺𝗋𝖽(𝖠)𝖼𝖺𝗋𝖽(A)\mathsf{card}(\wp(A)) = 2^{\mathsf{card(A)}}\neq \mathsf{card}(A).

La démonstration dans le cas infini est elle plus amusante, car elle fait intervenir un raisonnement par l’absurde et une preuve par diagonalisation.

Si on suppose qu’il existe une ensemble AA et une bijection ϕ:A(A)\phi : A \to \wp(A), alors construisons l’ensemble BB défini par

B={aA|aϕ(a)}B = \{a\in A \vert a \notin \phi(a)\}

et posons

b=ϕ1(B)b=\phi^{-1}(B)

On alors la contradiction suivante

bBbϕ(b)=Bb\in B \Leftrightarrow b\notin \phi(b) = B

On reparlera de cette méthode de preuve par diagonalisation…

Conséquences

Ce théorème montre un moyen facile de construire une suite d’ensemble de cardinalité strictement croissante, ce qui n’est pas trivial a priori. En effet, on pourra se rappeler que des ensembles comme \mathbb{N}, \mathbb{Z} et \mathbb{Q} sont équipotents.