Argument de la diagonale de Cantor - Définition

Calculabilité

Le raisonnement diagonal est constructif (on dit aussi effectif). C'est tout à fait clair dans le cas des suites, si chacune des suites de l'énumération est engendrée par un procédé calculatoire, on a un procédé pour calculer la suite diagonale. Cela signifie que l'on peut théoriquement calculer autant de termes de la suite que l'on souhaite, les seules limites sont matérielles, temps et puissance de calcul.

Le raisonnement diagonal donné pour les réels reste bien également constructif. Supposons qu'une suite (r_i) de réels entre 0 et 1 nous soit donnée effectivement par des développements décimaux : on dispose d'un algorithme qui peut calculer, étant donné deux entiers i' et n la n-ième décimale d'un même développement de r_i. Alors le procédé diagonal permet bien de calculer un réel n'appartenant pas à cette suite (et même une infinité dénombrable de réels tous distincts, en reportant à chaque étape le réel diagonal en tête de liste, ce qui décale les diagonales). On l'adapterait facilement pour une suite dénombrable de réels en général.

Le caractère effectif du raisonnement diagonal en a fait l'un des fondements de la théorie de la calculabilité, autant pour les résultats de non-existence que sont les démonstrations d'indécidabilité algorithmique, à commencer par la preuve de l'indécidabilité du problème de l'arrêt, que pour des résultats d'existence, comme les théorèmes de point fixe de Kleene.

Sous une forme très proche de ces théorèmes de point fixe, il est également un argument essentiel du premier théorème d'incomplétude de Gödel (qui est un résultat d'indécidabilité logique) : en l'occurrence le lemme qui permet de montrer l'existence d'une proposition qui entraîne sa propre non-prouvabilité, et qui est d'ailleurs souvent appelé lemme de diagonalisation.

Le théorème de Cantor

Cantor a utilisé l'argument de la diagonale pour démontrer que pour tout ensemble S (fini ou infini), l'ensemble des parties de S, noté généralement P(S), est « strictement plus grand » que S lui-même. En d'autre termes, il ne peut pas exister de surjection de S vers P(S), et donc pas non plus d'injection de P(S) dans S. Ce résultat est aujourd'hui connu sous le nom de théorème de Cantor.

Pour cela, il nous suffit de montrer que, pour toute fonction f de S dans P(S), on peut construire un ensemble qui n'est pas dans l'ensemble image de f. En effet, soit l'ensemble A des éléments x de S tels que x n'appartienne pas à f(x). S'il existait un élément a de S tel que f(a)=A, On aboutirait à une contradiction aussi bien dans le cas où a appartient à A, que dans le cas contraire. L'ensemble A n'appartient donc pas à l'image de f : celle-ci ne peut être surjective.

Voici une version plus « imagée » de cet argument, dans le cas où S est l'ensemble des entiers naturels :

«  Soit un cahier comportant autant de pages que l'on veut. On numérote chaque page, et, sur chacune d'entre elles, on écrit un ensemble d'entiers (tous différents), de telle sorte à ne jamais écrire deux fois le même ensemble.
On dit qu'un nombre N est ordinaire si l'ensemble écrit à la page N ne contient pas N ; dans le cas contraire, on dit que N est extraordinaire. Supposons que l'on ait écrit sur ce cahier tous les ensembles possibles. La question est : à quelle catégorie appartient l'entier sur la page duquel on a écrit l'ensemble des nombres ordinaires ?  »

Dans le cas dénombrable, cette dernière forme de l'argument diagonal est identique à celle du paragraphe précédent, où l'on montrait que l'ensemble des suites de deux éléments n'est pas dénombrable : il suffit de choisir un élément pour « appartient », l'autre pour « n'appartient pas ». L'argument diagonal utilisé pour le théorème de Cantor ne diffère donc de celui pour les suites que parce qu'il est utilisé pour un ensemble S quelconque, au lieu de l'ensemble des entiers naturels. On l'adapte d'ailleurs directement pour montrer que l'ensemble des fonctions de S dans un ensemble quelconque à plus de deux éléments n'a pas même cardinalité que S.