Argument de la diagonale de Cantor

Infos
L'argument de la diagonale, ou argument diagonal fut découvert et publié par le mathématicien allemand Georg Cantor (1845-1918) 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 1874Cantor (1874) Über eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen, Journal de Crel
Argument de la diagonale de Cantor

L'argument de la diagonale, ou argument diagonal fut découvert et publié par le mathématicien allemand Georg Cantor (1845-1918) 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 1874Cantor (1874) Über eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen, Journal de Crelle 77, p258-262 (voir sur le centre de numérisation de Göttingen , et une traduction en français, Sur une propriété du système de tous les nombres algébriques réels, Acta Math. 2 (1883), pp 305-310, sur le site de la BNF, ). On dispose de la genèse de cette démonstration grâce aux lettres des 7 décembre et 9 décembre 1873 de Georg Cantor à Dedekind, traduites in Jean Cavaillès , Philosophie mathématique, annexe "Correspondance Cantor-Dedekind", ed. Hermann, Paris. pp. 189-191 de l'édition de 1962. Pour l'article de 1891, celui qui utilise l'argument diagonal, voir la bibliographie., 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. 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. A 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 \mathbb est non dénombrable, il suffit de démontrer la non dénombrabilité du sous-ensemble de \mathbb, donc de construire, pour toute partie dénombrable D de , un élément de n'appartenant pas à D. Soit donc une partie dénombrable de énumérée à l'aide d'une suite r=(r_i)=\r_1, r_2, ..., r_i, ...\. Chaque terme de cette suite a une écriture décimale avec une infinité de chiffres après la virgule (éventuellement une infinité de 0 pour un nombre décimal), soit : :ri = 0 , ri1 ri2 ... rin ... On construit maintenant un nombre réel x dans en considérant le nième chiffre après la virgule de rn. Par exemple, pour la suite r : :r1 = 0 , 0 1 0 5 1 1 0 … :r2 = 0 , 4 1 3 2 0 4 3 … :r3 = 0 , 8 2 4 5 0 2 6 … :r4 = 0 , 2 3 3 0 1 2 6 … :r5 = 0 , 4 1 0 7 2 4 6 … :r6 = 0 , 9 9 3 7 8 1 8 … :r7 = 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 ne décimale de rn est différente de 1, alors la ne décimale de x est 1, sinon la ne 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 mais ne peut pas être dans la suite , car il n'est égal à aucun des nombres de la suite : il ne peut pas être égal à r1 car la première décimale de x est différente de celle de r1, de même pour r2 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 infinis de 0 et de 1 n'est pas dénombrable. Or celui-ci correspond à l'écriture binaire des réels dans . 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.

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 tout 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.

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. Si une suite de réels entre 0 et 1 nous est donnée effectivement, au sens où on peut calculer, étant donné un entier i, le développement décimal de ri a une précision arbitraire donnée, alors on peut 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'adapte facilement pour une suite dénombrable de réels en général : par exemple on peut utiliser que le réel diagonal de la démonstration ci-dessus, dont le développement décimal n'utilise que 1 et 2, appartient donc à ]0, 10, 1)
-Georg Cantor (1932) – Gesammelte Abhandlungen mathematischen und philosophischen inhalts. éd. par Ernst Zermelo. Catégorie:Infini Diagonale de Cantor Catégorie:Méthode de démonstration Catégorie:Georg Cantor cs:Cantorova diagonální metoda de:Cantors zweites Diagonalargument en:Cantor's diagonal argument es:Diagonalización de Cantor et:Cantori diagonaaltõestus fi:Cantorin diagonaaliargumentti he:האלכסון של קנטור hu:Átlós eljárás it:Argomento diagonale di Cantor ja:カントールの対角線論法 ka:კანტორის დიაგონალური არგუმენტი ko:대각선 논법 lmo:Argümeent da la diagunala da Cantor nl:Diagonaalbewijs van Cantor pl:Metoda przekątniowa pt:Argumento de diagonalização de Cantor sl:Cantorjev diagonalni dokaz ta:கேண்டரின் கோணல்கோடு நிறுவல்முறை th:วิธีการแนวทแยงของคันทอร์ tr:Cantor'un Köşegen Yöntemi zh:對角論證法
Sujets connexes
Argument diagonal   Calculabilité   Démonstration   Développement décimal   Ensemble   Ensemble dénombrable   Ernst Zermelo   Fraction dyadique   Georg Cantor   Hypothèse du continu   Injection (mathématiques)   Jean Cavaillès   Mathématiques   Nombre cardinal   Nombre ordinal   Nombre réel   Nombre transfini   Paradoxe de Richard   Paradoxe de Russell   Problème de l'arrêt   Richard Dedekind   Suite (mathématiques)   Surjection   Théorie des ensembles   Théorème d'incomplétude de Gödel   Théorème de Cantor   Théorème de récursion de Kleene  
#
Accident de Beaune   Amélie Mauresmo   Anisocytose   C3H6O   CA Paris   Carole Richert   Catherinettes   Chaleur massique   Championnat de Tunisie de football D2   Classement mondial des entreprises leader par secteur   Col du Bonhomme (Vosges)   De viris illustribus (Lhomond)   Dolcett   EGP  
^