Diagonal argument

Imaginez une liste infinie de suites de 0 et de 1, écrites ligne après ligne. Prenez le premier symbole de la première ligne, le deuxième de la deuxième, puis le troisième de la troisième, et ainsi de suite. Ces symboles forment une diagonale.

Inversez chacun d'eux : 0 devient 1 et 1 devient 0. La nouvelle suite diffère de la première ligne à la première place, de la deuxième à la deuxième place, et de toute ligne quelque part. Elle ne figurait donc pas dans la liste, même si celle-ci prétendait être complète.

Le procédé diagonal est une construction par laquelle on réfute l'exhaustivité d'une liste infinie. On suppose que des objets x₁, x₂, … sont tous rangés selon les entiers naturels et que chacun possède une suite de coordonnées. On fabrique un objet y dont la n-ième coordonnée est choisie différente de la n-ième coordonnée de x_n. Pour tout entier naturel n au moins égal à 1, y et x_n diffèrent donc à cette coordonnée. Ainsi, y n'est égal à aucun objet annoncé dans la liste.

Dans l'argument de Cantor sur les réels, les coordonnées sont des chiffres décimaux. Il faut fixer une écriture canonique, car certains réels ont deux développements décimaux. Une règle sûre choisit toujours 1 ou 2 : au rang n, on écrit 2 si le n-ième chiffre du n-ième réel vaut 1, et 1 sinon. Le réel construit ne finit pas par une suite de 9 et diffère du n-ième réel au rang n.

Le même geste sert en analyse à sélectionner une sous-suite qui conserve successivement une infinité de conditions. Chaque étape raffine la sous-suite précédente ; la sous-suite diagonale prend ensuite son n-ième terme dans le n-ième raffinement.

Supposons qu'une liste x₁, x₂, … prétende contenir toutes les suites binaires infinies. Le symbole situé au rang n de la suite x_n est noté x_n,n. On définit le symbole de rang n d'une nouvelle suite y par la règle :

Alors y diffère de x_n au rang n, quel que soit n. La liste omet donc y et ne peut pas contenir toutes les suites binaires infinies.

La construction exige une liste indexée par les entiers naturels, une coordonnée de rang n définie pour chaque objet x_n, et une règle qui choisit à ce rang une valeur autorisée mais différente. L'objet obtenu doit encore appartenir à l'ensemble étudié. Ces points sont vérifiables avant de conclure que la liste n'est pas exhaustive.

Avec des écritures décimales, le choix des représentations doit aussi supprimer l'ambiguïté entre une écriture terminée et une écriture finissant par des 9. Si les objets sont seulement des mots finis, la n-ième position peut ne pas exister sur la n-ième ligne : le procédé décrit ici est alors bloqué. Il faut d'abord définir un prolongement commun ou employer un autre argument adapté aux objets finis.

Une liste prétend contenir toutes les suites infinies de 0 et de 1. Ses cinq premières lignes commencent par 01011, 11001, 00110, 10100 et 11011. Chaque ligne continue au-delà des cinq rangs affichés.

La grille surligne les symboles diagonaux et montre en rouge le début de la suite construite. Le geste se poursuit à tous les rangs.

1. On lit la diagonale : 0 sur x₁, 1 sur x₂, 1 sur x₃, 0 sur x₄, puis 1 sur x₅. Elle commence donc par 01101.

2. On inverse chaque symbole diagonal. La nouvelle suite y commence par 10010 et se poursuit en appliquant la même règle à chaque rang.

3. On compare y à chaque ligne au rang correspondant. Son premier symbole diffère de celui de x₁, son deuxième de celui de x₂, et ainsi de suite.

Le contrôle est refaisable ligne par ligne : au rang n, les deux symboles ont une somme égale à 1. La suite y diffère donc de chaque x_n et manque à la liste prétendument complète.

Pour contester qu'un ensemble soit dénombrable, on part d'une liste supposée complète. Si chaque objet possède des coordonnées successives que l'on peut modifier sans quitter l'ensemble, le procédé diagonal construit directement l'élément oublié. Une simple recherche d'un doublon ne suffirait pas : elle montrerait seulement que la liste est mal présentée.

Pour satisfaire une infinité de conditions par extraction, on choisit d'abord une sous-suite répondant à la première condition, puis une sous-suite de celle-ci répondant à la deuxième, et ainsi de suite. Prendre le n-ième terme du n-ième choix produit la sous-suite diagonale. Cette méthode intervient notamment avec des suites bornées et dans le théorème d'Arzelà-Ascoli.

La diagonale d'un tableau. Elle désigne seulement les entrées de positions correspondantes, comme x_1,1, x_2,2, x_3,3. Le procédé diagonal ajoute une opération décisive : il modifie chacune de ces entrées afin de construire un objet absent de la liste. Lire 01101 dans l'exemple donne la diagonale ; écrire 10010 applique le procédé.

Une extraction ordinaire de sous-suite. Elle sélectionne des termes selon un seul choix fixé. L'extraction diagonale traverse au contraire une chaîne de sous-suites emboîtées : son terme de rang n vient du n-ième raffinement. Le critère distinctif est donc la présence d'une infinité de sélections successives à concilier.

Deux écritures pour un même réel. Changer un chiffre ne prouve pas toujours que deux développements décimaux représentent des nombres différents : une écriture terminée peut coïncider avec une écriture finissant uniquement par des 9. Le symptôme est précisément cette queue de 9. On fixe des écritures canoniques et l'on choisit pour le réel diagonal des chiffres tels que 1 et 2.

Une construction qui sort de l'ensemble. Différer de chaque ligne ne suffit pas si l'objet fabriqué ne respecte plus la définition de l'ensemble étudié. Avant de conclure, il faut vérifier que toutes ses coordonnées sont autorisées et que leur suite définit bien un objet du même type.

Une diagonale finie. Les cinq lignes de l'exemple ne prouvent qu'une différence avec ces cinq débuts. La conclusion générale exige que la règle soit définie pour tout entier n au moins égal à 1. Une figure finie illustre ce mécanisme ; elle ne remplace pas sa poursuite à l'infini.

Dénombrable — Situez exactement la propriété que l'argument diagonal réfute lorsqu'une liste prétend épuiser tous les objets.

suite bornée — Retrouvez le cadre de suites cité dans les extractions diagonales utilisées en analyse.

Cantor Georg — Replacez l'argument de non-dénombrabilité des réels dans le parcours du mathématicien qui l'a employé.