## [Diagonalisation de Cantor](/fr/node/59189) Définition Une méthode constructive qui, à partir d'une liste supposée (une suite) d'objets représentés par des entrées indexées, produit un nouvel objet en modifiant les éléments diagonaux de sorte que le nouvel objet diffère de chaque objet listé ; utilisée couramment pour prouver l'indénombrabilité des ensembles et exhiber des objets non capturés par une énumération effective. ## Principe Principe Si les objets sont présentés comme une suite indexée par les entiers naturels, changer la composante n-ième de l'objet n-ième donne un objet qui ne peut coïncider avec aucun membre de la suite ; par conséquent, aucune énumération ne peut être complète pour la classe visée dès lors que la modification diagonale est bien définie. ## Démonstration Démonstration Construire le nombre réel dans [0,1] dont le chiffre décimal en position n diffère du n-ième chiffre décimal du n-ième nombre d'une liste supposée (en évitant les représentations ambiguës telles que les suites finissant par des 9); l'objet obtenu ne peut égaler aucun élément listé, prouvant que l'intervalle est indénombrable. Le même schéma sert à montrer que certains langages ou fonctions ne sont pas énumérables ou que certains problèmes sont indécidables en diagonalisant sur les programmes. ## Mauvaise application Mauvaise application Appliquer la diagonale sans traiter les ambiguïtés de représentation (p. ex. développements décimaux à deux représentations) peut produire un candidat qui coïncide involontairement avec un élément de la liste. Employer la diagonale sur des objets dépourvus d'une représentation indexable uniforme ou sur des classes fermées par la modification diagonale peut échouer à donner le contre‑exemple attendu. ## Conséquence Conséquence Établit l'existence d'infinis strictement plus grands (indénombrabilité), montre les limites des méthodes d'énumération, construit des fonctions non énumérées ou non calculables, et génère des paradoxes et des preuves d'indécidabilité fondés sur l'autoréférence lorsqu'on combine la diagonale avec des encodages effectifs. ## Inversion Inversion Lister ou établir une bijection de la classe visée avec les entiers naturels (c.-à-d. démontrer une énumération complète) inverse l'argument diagonale en montrant que la construction diagonale ne peut produire d'élément nouveau ; le contraste met en évidence si la liste revendiquée est exhaustive. ## Limite Limite Nécessite une suite donnée ou une énumération effective et une notion claire de modification composante par composante ; la technique est syntaxique et dépendante de la représentation, elle ne s'applique donc pas directement aux preuves topologiques ou métriques d'indénombrabilité sans traduction en cadre séquentiel. ## Tension sémantique Tension sémantique Entre en tension avec des preuves d'existence non constructives (p. ex. arguments de mesure/compacité) et avec des preuves bijectives de cardinalité ; la diagonalisation met l'accent sur l'autoréférence constructive tandis que d'autres méthodes exploitent des propriétés structurelles ou non constructives. ## Synthèse Synthèse La diagonalisation de Cantor est une transformation constructive et sensible à la représentation qui, en modifiant les composantes diagonales d'une liste supposée, produit un objet distinct de chaque élément listé ; elle fournit un schéma simple et réplicable pour établir l'indénombrabilité et l'indécidabilité, tout en requérant une gestion attentive des représentations et des contraintes du domaine.