ArithmétiqueThéorème · Glossaire
paradoxe de Richard
Le paradoxe de Richard naît quand on énumère toutes les définitions finies de nombres réels, puis qu’on construit par diagonalisation un réel différent du n-ième nombre à sa n-ième décimale. Ce réel semble à la fois défini par une phrase finie et absent de la liste, puisqu’il diffère de chacun de ses éléments. La contradiction disparaît lorsqu’on distingue langage et métalangage : la description diagonale dépend de la liste entière, elle-même non définissable par une expression finie au sens retenu.
Sommaire
Ce que vous allez apprendre
- Identifier le mécanisme diagonal qui construit un réel absent de la liste.
- Refaire le raisonnement ligne par ligne avec des notations introduites.
- Localiser la contradiction apparente dans le changement de niveau de langage.
- Distinguer le paradoxe sémantique de la procédure diagonale elle-même.
En clair
Prenez une liste de toutes les phrases finies censées définir un nombre réel. Rangez les nombres obtenus, puis fabriquez un nouveau nombre en changeant une décimale de chaque ligne. Ce nombre échappe à toute ligne de la liste. Pourtant, la phrase qui vient de le construire paraît elle-même assez courte pour figurer dans la liste.
Le piège porte sur les mots, non sur le calcul diagonal. La construction parle de la liste entière : sa description peut être finie dans le métalangage, sans être pour autant une définition admissible dans le langage objet qui a servi à former la liste.
Définition
Le paradoxe de Richard est un paradoxe sémantique de la théorie des ensembles. On ordonne alphabétiquement les arrangements finis de lettres et l'on conserve ceux qui définissent validement un nombre réel. La suite (en) énumère, dans l'ordre de ces définitions, les nombres ainsi définis ; plusieurs termes peuvent donc avoir la même valeur. La lettre E désigne l'ensemble des valeurs de cette suite. Comme les expressions retenues sont finies, cette suite, et donc E, est dénombrable.
On fixe pour chaque réel son écriture décimale canonique, celle qui ne se termine pas par une suite infinie de 9. On construit ensuite un réel nommé r par diagonalisation : sa n-ième décimale vaut 1 si la n-ième décimale de en n'est pas 1, et 2 sinon. L'écriture de r est elle aussi canonique et r diffère de chaque terme en sur la ligne correspondante ; il semble donc ne pas appartenir à E. Or la procédure qui vient de le décrire paraît être une expression finie : c'est la contradiction apparente.
La résolution donnée par Richard distingue deux niveaux de langage. Les phrases finies énumérées constituent le niveau des définitions candidates. La description de r parle, elle, de l'énumération tout entière : elle peut être formulée en un nombre fini de mots dans le métalangage, sans être pour autant une définition finie admissible dans le langage objet retenu. La contradiction disparaît avec cette distinction.
Le principe
Si (en) énumère, dans un ordre fixé, les nombres réels définis par des expressions finies, on fixe leurs écritures décimales canoniques, qui ne se terminent pas par une suite infinie de 9. On forme r en prenant pour n-ième décimale 1 si celle de en n'est pas 1, et 2 sinon. En notant dn(x) la n-ième décimale canonique de x, la règle est : . Elle écarte r de chaque en, mais ne prouve pas que la description de r appartient aux expressions finies énumérées.
Quand l'utiliser
Le raisonnement suppose d'abord un alphabet et des arrangements finis de ses lettres, ordonnés alphabétiquement. Il faut ensuite pouvoir reconnaître parmi eux les expressions qui sont des définitions valides de nombres réels. Chaque définition retenue fournit un terme en de la suite énumérante, même si plusieurs termes ont la même valeur. Enfin, en doit être associé à sa n-ième décimale canonique afin d'appliquer la procédure diagonale.
Le contre-cas décisif apparaît quand la prétendue définition de r dépend de l'énumération prise dans sa totalité. Cette description peut être finie dans le métalangage, mais cela ne la rend pas admissible dans la classe d'expressions du langage objet qui a été énumérée. Il faut séparer le langage des définitions énumérées du langage qui parle de cette énumération.
Un exemple, pas à pas
Considérons une suite qui énumère les réels définis par des expressions finies, avec leur écriture décimale canonique, celle qui ne se termine pas par une suite infinie de 9. Le symbole en désigne le terme de sa n-ième ligne et dn(en) la décimale située sur la diagonale de cette ligne. Le symbole r désigne le réel que l'on tente de construire.
1. Sur la première ligne, la première décimale de r vaut 1 si celle de e1 n'est pas 1, et 2 sinon.
2. Sur la deuxième ligne, on applique la même règle à la deuxième décimale de e2.
3. On poursuit : à l'étape n, on impose avec le même choix entre 1 et 2.
4. Pour chaque ligne n, les écritures canoniques de r et de en diffèrent donc au moins à la n-ième décimale, si bien que r est différent de en.
2. Sur la deuxième ligne, on applique la même règle à la deuxième décimale de e2.
3. On poursuit : à l'étape n, on impose avec le même choix entre 1 et 2.
4. Pour chaque ligne n, les écritures canoniques de r et de en diffèrent donc au moins à la n-ième décimale, si bien que r est différent de en.
Le contrôle est refaisable ligne par ligne : la case diagonale et la décimale correspondante de r ne coïncident jamais. La conclusion correcte est que r n'est aucun terme de la suite énumérante. La contradiction ne naît que si l'on ajoute, à tort, que cette construction fournit une définition finie appartenant elle-même à la liste.
En pratique
Face à une définition qui affirme parler de toutes les définitions, repérez d'abord la collection qu'elle utilise. Si la phrase dépend de la totalité de cette collection, il faut examiner son niveau de langage plutôt que la compter aussitôt parmi ses propres éléments.
Dans l'exemple du « plus petit entier non définissable par une phrase française de moins de 20 mots », comptez les mots, puis observez surtout l'autoréférence : la phrase prétend satisfaire le critère qu'elle énonce. La distinction des niveaux de langage est le bon outil.
Quand une diagonalisation produit un objet absent d'une liste, vérifiez séparément deux conclusions : l'objet diffère bien de chaque ligne, mais sa description n'appartient pas nécessairement à la classe de descriptions qui a engendré la liste.
À ne pas confondre
Avec la procédure diagonale de Cantor. La source indique que la construction de Richard lui est analogue, mais le paradoxe de Richard porte sur les définitions exprimées par des mots. Le cas tranche par le critère suivant : si le problème vient de l'appartenance de la description à la liste des descriptions, l'obstacle est sémantique.
Avec une contradiction mathématique établie. Deux conclusions incompatibles seraient une contradiction véritable. Ici, l'incompatibilité disparaît dès que l'on refuse de traiter la description globale de l'énumération comme une définition automatiquement admissible dans le langage objet : il s'agit d'une contradiction apparente.
Limites et pièges
Caractériser la liste ne suffit pas à produire une définition admissible. L'expression « tous les nombres définissables » peut caractériser l'énumération en un nombre fini de mots dans le métalangage. Le piège consiste à traiter cette caractérisation comme si elle était automatiquement une expression finie admissible dans le langage objet retenu.
Le seuil de 20 mots ne résout rien à lui seul. Dans l'exemple élémentaire, une phrase de moins de 20 mots semble définir l'entier déclaré non définissable sous ce seuil. Le signal d'alarme est la phrase qui se classe elle-même ; il faut distinguer le langage examiné de celui qui formule le classement.
La diagonale n'est pas l'étape fautive. Le contrôle dn(r) différent de dn(en) établit bien que r diffère du n-ième terme. Le saut illégitime consiste à conclure que la description globale de r est automatiquement une expression admissible dans la classe énumérée.
Pour aller plus loin
Le glossaire métalangage approfondit la séparation entre le langage étudié et celui qui sert à en parler.
La fiche Cantor Georg replace le nom associé à la procédure diagonale à laquelle le raisonnement de Richard est comparé.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres