Argument de la diagonale de Cantor - Définition

Introduction

L'argument de la diagonale, ou argument diagonal fut découvert par le mathématicien allemand Georg Cantor (1845-1918) et publié en 1891. Il permit à ce dernier de donner une deuxième démonstration de la non-dénombrabilité de l'ensemble des nombres réels, beaucoup plus simple, selon Cantor lui-même, que la première qu'il avait publiée en 1874, et qui utilisait des arguments d'analyse, en particulier le théorème des segments emboîtés. L'argument diagonal fut exploité dans un cadre plus général par Cantor dans le même article pour son théorème sur la cardinalité de l'ensemble des parties d'un ensemble.

L'argument diagonal s'applique à une relation ou une fonction (éventuellement partielle) à deux arguments sur un même domaine E, ou, ce qui revient au même, à une fonction qui à chaque élément de E associe une fonction définie sur E. Il utilise de façon essentielle la diagonale de E × E : l'ensemble des couples (x, x) pour x dans E, d'où l'appellation.

Il a été adapté pour de nombreuses démonstrations. Des paradoxes qui ont joué un rôle dans la fondation de la théorie des ensembles comme le paradoxe de Russell (inspiré du théorème de Cantor) mais aussi le paradoxe de Richard s'appuient sur le raisonnement diagonal. Le théorème d'incomplétude de Gödel l'utilise pour un lemme essentiel. La théorie de la calculabilité en fait grand usage, à commencer par le problème de l'arrêt. L'argument diagonal est ainsi devenu un classique de la démonstration en mathématiques.

Le dénombrable et le continu

On peut s'appuyer sur le développement décimal des réels. À partir d'une énumération de réels distincts, l'extraction de la n-ième décimale du n-ième réel permet de construire un nouveau réel qui n'était pas dans l'énumération. Les décimales peuvent être présentées sous forme d'un tableau semi-infini à deux entrées dont la n-ième ligne comprend la liste des décimales du n-ième réel. La liste des décimales extraites se lit sur la diagonale, d'où l'appellation argument de la diagonale.

Un développement décimal d'un réel est une suite de chiffres. L'argument est en fait valable pour une énumération de suites d'entiers. Il est d'ailleurs légèrement plus simple dans ce dernier cas, puisque le problème de la double représentation des décimaux ne se pose pas.

La non dénombrabilité des réels

Pour démontrer que est non dénombrable, il suffit de démontrer la non dénombrabilité du sous-ensemble [0,1] de , donc de construire, pour toute partie dénombrable D de [0,1], un élément de [0,1] n'appartenant pas à D.

Soit donc une partie dénombrable de [0,1] énumérée à l'aide d'une suite r = (r₁, r₂, r₃, ... ). Chaque terme de cette suite a une écriture décimale avec une infinité de chiffres après la virgule (éventuellement une infinité de zéros pour un nombre décimal), soit :

r_i = 0 , r_i1 r_i2 ... r_in ...

On construit maintenant un nombre réel x dans [0,1] en considérant le n^ième chiffre après la virgule de r_n. Par exemple, pour la suite r :

r₁ = 0 , 0 1 0 5 1 1 0 …

r₂ = 0 , 4 1 3 2 0 4 3 …

r₃ = 0 , 8 2 4 5 0 2 6 …

r₄ = 0 , 2 3 3 0 1 2 6 …

r₅ = 0 , 4 1 0 7 2 4 6 …

r₆ = 0 , 9 9 3 7 8 1 8 …

r₇ = 0 , 0 1 0 5 1 3 0 …

…

Le nombre réel x est construit par la donnée de ses décimales suivant la règle : si la n^ième décimale de r_n est différente de 1, alors la n^ième décimale de x est 1, sinon la n^ième est 2. Par exemple avec la suite ci-dessus, la règle donne x = 0 , 1 2 1 1 1 2 1 …

Le nombre x est clairement dans l'intervalle [0, 1] mais ne peut pas être dans la suite ( r₁, r₂, r₃, ... ), car il n'est égal à aucun des nombres de la suite : il ne peut pas être égal à r₁ car la première décimale de x est différente de celle de r₁, de même pour r₂ en considérant la deuxième décimale, etc.

La non unicité de l'écriture décimale pour les décimaux non nuls (deux écritures sont possibles pour ces nombres, l'une avec toutes les décimales valant 0 sauf un nombre fini, l'autre avec toutes les décimales valant 9 sauf un nombre fini) n'est pas un écueil au raisonnement précédent car le nombre diagonal x ne peut être décimal, puisque son écriture décimale est infinie et ne comporte que les chiffres 1 et 2.

La preuve de Cantor

Dans l'article de 1891, où il introduit ce raisonnement, Georg Cantor construit à partir de toute énumération de suites de deux caractères distincts m et w une nouvelle suite, qui ne comporte également que m et w et qui n'était pas déjà énumérée. Le raisonnement est exactement celui décrit ci-dessus pour les réels, simplifié du fait que l'on n'a que deux chiffres — on peut prendre 1 et 2 pour m et w — et que cette fois-ci, comme on traite directement des suites, il n'y a plus de problème de double représentation.

La preuve se généralise de façon évidente au cas des suites d'éléments d'un ensemble à plus de deux éléments (fini ou infini).

On en déduit donc que l'ensemble des suites infinies de 0 et de 1 n'est pas dénombrable. Or celui-ci correspond à l'écriture binaire des réels dans [0,1]. Cependant l'écriture binaire des nombres dyadiques n'est pas unique, et si l'on veut adapter le raisonnement aux réels, rien n'assure que le réel diagonal construit ne soit pas dyadique : son développement binaire pourrait très bien se terminer par une infinité de 0 ou par une infinité de 1.

Cantor ne détaille pas l'argument, mais il sait par ailleurs que l'ensemble des réels dyadiques est dénombrable, et que la réunion de deux ensembles dénombrables est dénombrable. Il peut donc en déduire (de façon plus indirecte que dans le raisonnement indiqué ci-dessus) que l'ensemble des réels entre 0 et 1 n'est pas dénombrable.