Incomplétude et complexité des démonstrations


Les théorèmes d'incomplétude de Gödel montrent que toute théorie T consistante (qui ne se contredit pas) et qui est capable de mener un minimum d'arithmétique (c'est le cas de toutes les théories utilisées par les mathématiciens, et c'est le cas en particulier de la théorie des ensembles) a des trous : il existe des énoncés E, nommés indécidables, tels que :

• T ne démontre pas E, et

• T ne démontre pas «non E» (la négation de E).

L'énoncé qui affirme que « T est consistante » — notons-le cons(T) — est lui même un indécidable : une théorie mathématique assez riche n'est jamais capable de démontrer qu'elle est consistante !

Ajouter un énoncé indécidable E aux axiomes d'une théorie T en diminue un peu l'incomplétude, puisque la théorie T1 qu'on obtient ainsi sait maintenant démontrer E (tout axiome est un théorème !). Malheureusement d'après les théorèmes d'incomplétude appliqué à T1, la théorie T1 possède elle-même des indécidables, dont l'énoncé cons(T1) affirmant que T1 est consistante. Répéter l'opération d'ajout d'indécidables comme axiomes donnent des théories T1, T2, T3, ... qui restent chacune incomplète. On peut tenter de répéter l'opération une infinité de fois, mais alors deux cas se présentent.

- Soit on le fait d'une manière systématique assez régulière, et on disposera alors au final d'une méthode algorithmique permettant de reconnaître les axiomes de la théorie T à laquelle on sera arrivé. Le théorème d'incomplétude s'appliquera à T. Il restera des indécidables.

- Soit on le fait d'une manière non algorithmique (par exemple en ajoutant l'indécidable le plus court à l'étape n), et alors, l'ensemble d'axiomes ajoutés n'est plus assez bien défini pour être acceptable comme ensembles d'axiomes. Même si la « théorie » T  obtenue n'a plus d'indécidables (c'est le cas avec la méthode de « l'indécidable le plus court ») ce n'est plus une théorie acceptable, car la vérification qu'une démonstration est correcte ne peut plus se faire par algorithme (si c'était le cas le théorème d'incomplétude s'appliquerait !).

On ne se débarrassera jamais vraiment de l'incomplétude en ajoutant des indécidables comme axiomes. La complexité des théories utiles en mathématiques a cet effet étonnant qu'elle rend inévitable la présence de trous.

Raccourcir les démonstrations

Il se trouve qu'il est quand même utile d'ajouter des indécidables comme axiomes : cela a un effet de réduction de la longueur des démonstrations. Ajouter des indécidables comme axiomes raccourcit les démonstrations, et c'est un phénomène général. Ce phénomène remarquable a été noté et démontré en 1971 par les mathématiciens Andrzej Ehrenfeucht, Jan Mycielski (voir la bibliographie à la fin de l'article). En voici l'énoncé (légèrement simplifié) :

Théorème. Pour tout système formel assez puissant T et consistant, et pour tout système formel T1  obtenu en ajoutant à T un énoncé indécidable comme nouvel axiome, il existe des théorèmes dont la démonstration la plus courte dans T1 est un milliard de fois plus petite que la démonstration la plus courte dans T. Bien sûr un milliard peut être remplacé par n'importe quel entier.

La démonstration de ce résultat n'est pas très difficile puisque l'article de Ehrenfeucht et Mycielski tient sur deux pages ! Elle est basée sur une version renforcée du théorème de Church.

Ce résultat vient s'opposer à l'idée qu'il y a une notion naturelle et raisonnable de longueur de démonstration. En effet, si pour avoir une notion bien définie de longueur de démonstration nous décidons de prendre (par exemple) la théorie des ensembles comme système formel de référence, c'est que nous avons de bonnes raisons de croire en sa consistance. Deux types d'arguments sont possibles pour justifier une telle conviction : (1) jamais en utilisant ce système formel nous n'avons trouvé de contradiction ; (2) ce système formel est basé sur des idées intuitives qui apparaissent de toute évidence non contradictoires. Si nous avons de bonnes raisons de croire à la consistance de la théorie des ensembles, autant utiliser comme système formel de référence, un système qui comporte l'affirmation de cette consistance. Mais alors d'après le résultat de Ehrenfeucht et Mycielski, la longueur de certaines démonstrations sera réduite d'un facteur aussi grand qu'on veut. Et donc la notion de longueur d'une démonstration n'a pas de sens absolu. Cela est d'autant plus vrai que, si on a trouvé naturel de passer de T à T1, on trouvera tout aussi naturel de passer de T1 à T2 (obtenu en ajoutant l'axiome cons(T1)), mais aussi à T3, etc., ce qui provoque à chaque fois des raccourcissements de démonstrations.

D'autres résultats du même type que celui de Ehrenfeucht et Mycielski (on les nomme « théorèmes de speed-up ») ont été prouvés en théorie de la démonstration (voir la bibliographie).

Impossible longueur

L'association du théorème d'incomplétude de Gödel et des résultats de Ehrenfeucht et Mycielski nous conduit à devoir admettre qu'aucun système formel ne peut être choisi pour déterminer une notion naturelle de longueur de démonstration : dès qu'on en tient un qu'on croit satisfaisant, tout de suite un autre, meilleur, se présente à l'esprit, dans lequel certaines démonstrations sont considérablement écourtées.

Doit-on vraiment en conclure qu'il n'y a aucune notion intrinsèque et absolue de longueur de démonstration, et donc que parler de complexité d'une démonstration n'a jamais vraiment de sens ? Ce serait très gênant car alors toutes les remarques que les mathématiciens font entre eux, sur la difficulté des théorèmes ne seraient qu'illusions et non-sens.

Une solution consiste peut-être à regarder les indécidables de Gödel comme des énoncés particuliers (y compris ceux affirmant la consistance du système qu'on utilise), et à ne pas leur attribuer la même évidence intuitive qu'aux autres énoncés mathématiques choisis comme axiomes, et donc à ne pas considérer comme allant de soi le système T1 (T auquel on ajoute l'axiome cons(T)) dès qu'on a accepté T. En un mot, il faut résister à la tentation d'ajouter des énoncés de consistance (ou d'autres énoncés du même type). Le logicien philosophe Daniel Isaacson a défendu ce genre d'arguments à propos de l'arithmétique élémentaire (voir la bibliographie). Certains de ses arguments pourraient sans doute être repris à propos de la théorie des ensembles, en particulier l'idée que dans les énoncés indécidables de Gödel, il y a toujours une codification et qu'accepter l'énoncé affirmant la non-contradiction de T, nécessite d'en accepter le contenu mais nécessite aussi d'accepter que la traduction au sein même de T de l'affirmation de non-contradiction est correctement menée, ce qui ne va pas de soi car cette traduction est toujours assez compliquée.

D'autres arguments donnant des rôles particuliers à certains systèmes formels et conduisant donc à les faire apparaître comme des systèmes absolus dont on ne doit pas chercher à s'échapper, et sur lesquels on peut s'appuyer pour formuler une définition de la longueur des démonstrations ont été aussi proposés par Harvey Friedman, Solomon Feferman et Stephen Simpson. L'affaire n'est donc pas réglée et seuls des progrès en logique mathématique et dans l'interprétation philosophique des résultats d'incomplétude permettront d'aller plus loin.

Notons justement que, récemment, des travaux remarquables sur l'effet de l'ajout d'axiomes portant sur la complexité de Kolmogorov de séquences particulières ont conduit à un théorème de « speed-up » et suggèrent une alternative à la méthode de complétion par ajout d'axiomes de consistance. Voir la bibliographie.

L'ajout d'indécidables comme axiome ne résout pas le problème de l'incomplétude et rend plus difficile encore celui d'une notion absolue acceptable de longueur de démonstrations et donc de complexité d'une démonstration. Pourtant chaque mathématicien est persuadé que dire d'une démonstration est complexe a un sens !

 

Bibliographie

A Sur les théorèmes de « speed-up » :

  • Andrzej  Ehrenfeucht, Jan Mycielski, Abbreviating proofs by adding new axioms, Bulletin of the American Mathematical Society, 77(3), 366-367, 1971. ici
  • Stefano Cavagnetto, The Lengths of Proofs : Kreisel's Conjecture and Gödel speed-up theorem, Journal of Mathematical Sciences, V. 158-5, 2009.
  • Anahit Chubaryan,  Hovhannes Bolibekyan, On the Rabin's speed-up of proof for some systems of first order logic, Proc. of the Yerevan State Univ.  Phys. and Mathem. Sci., 2009 : ici

B Sur l'idée qu'on peut avoir de bonnes raisons de ne pas chercher à compléter une théorie par de nouveaux axiomes :

  • Daniel Isaacson, Arithmetical truth and hidden higher-order concepts, in Logic Colloquium ’85. Logic and the Foundations of Mathematics, 122, 147-169, 1987.
  • Daniel Isaacson, Some Considerations on Arithmetical Truth and the Omega-rule, In M. Detlefsen (ed.), Proof, logic and formalization, 94–138, London, Routledge, 1992.
  • Peter Smith, Ancestral Arithmetics and Isaacson's Thesis, 2007 : ici

C Sur les récents résultats suggérant d'ajouter des axiomes concernant la complexité de Kolmogorov comme axiomes :

  • Laurent Bienvenu, Andrei Romashchenko, Alexander Shen, Antoine Taveneaux, Stijn Vermeeren, The Axiomatic Power of Kolmogorov Complexity, à paraître dans Annals of Pure and Applied Logic, 2014 : ici
  • Antoine Taveneaux, Puissance logique et calculatoire de l'aléa algorithmique, Thèse, Université de Paris 7, 2013.

 

 


9 commentaires pour “Incomplétude et complexité des démonstrations”

  1. Nivuld Répondre | Permalink

    "Chaque mathématicien est persuadé que dire d'une démonstration est complexe a un sens".
    La preuve* par l'exemple :
    "La démonstration de ce résultat n'est pas très difficile puisque l'article de Ehrenfeucht et Mycielski tient sur deux pages"

    (* Je sais qu'un exemple n'est pas un preuve, pardonnez-moi cette infamie)

  2. Diziet Sma Répondre | Permalink

    Bonsoir,
    existent-ils des indécidables en géométrie euclidienne ?
    Je veux dire avec les seuls axiomes originaux,et si oui lequel par exemple.

    • Jean-Paul Delahaye Répondre | Permalink

      La question n'est pas simple car tout dépend de la façon dont on choisit les axiomes de la géométrie euclidienne.

      La géométrie euclidienne prise dans son sens le plus général (par exemple formulée au sein de la théorie des ensembles) permet de manipuler les entiers et contient donc l'arithmétique élémentaire. Elle est donc sujette à l'indécidabilité de Gödel. L'énoncé de sa consistance est donc un indécidable.

      En revanche, la théorie de la structure de corps ordonné et la géométrie euclidienne formalisée en s'appuyant sur cette structure ont été montrées décidables par Alfred Tarski.

      Voir une présentation des axiomes de cette géométrie euclidienne en :

      http://en.wikipedia.org/wiki/Tarski's_axioms

      Quelques commentaires et explications sur ces questions d'axiomatisation de la géométrie euclidienne se trouvent en :

      http://math.stackexchange.com/questions/90393/why-euclidean-geometry-cannot-be-proved-incomplete-by-godels-incompleteness-the

  3. Diziet Sma Répondre | Permalink

    Merci pour les liens et notamment celui de Tarski qui révèle toute l'importance des travaux de ce mathématicien.
    Les théorèmes d'incomplètude de Godel m'ont toujours fait penser à des OVNIS dans le paysage mathématique.On se convainc de leur importance épistémologique,mais il est beaucoup plus difficile d'entrevoir leurs conséquences (sauf peut-ètre pour Hilbert),et surtout d'envisager qu'ils pourraient imposer des limites aux développements à venir en mathématiques.
    Ces théorèmes sont-ils si "génants" en pratique ?

    • Jean-Paul Delahaye Répondre | Permalink

      Pour répondre brièvement, je ne citerai qu'un exemple. Considèrons les énoncés de la forme K(s) = n qui signifient «la suite s a une complexité de Kolmogorov qui vaut n». Gregory Chaitin a montré qu'un théorie donnée (par exemple la théorie des ensembles) ne peut en démontrer qu'un nombre fini, tous les autres sont des indécidables de la théorie.

      La complexité de Kolmogorov est la façon la plus générale de definir le contenu en information d'une suite binaire, c'est un concept de base de l'informatique. Le fait qu'une théorie donnée est toujours presque totalement aveugle à cette complexité est simple à comprendre et m'apparaît comme très grave. Il s'agit d'une limite aux développements à venir des mathématiques.

      Il y a quelques années j'ai discuté en donnant d'autres exemples de la question de l'importance des indécidables. Le texte de cette discussion est le chapitre 6 de mon livre "Information complexité et hasard". Vous le trouverez ici ;

      http://www.lifl.fr/~delahaye/dnalor/DelahayeInformationCompl1999Ch6.pdf

  4. Diziet Sma Répondre | Permalink

    Merci infiniment Jean-Paul pour cet extrait de votre livre,il est effectivement en plein dans la contexte que vous avez patiemment accepté de discuter avec moi,mème si je dois avouer que je bloque un peu sur certains concepts.
    Mais je vais m'accrocher,je viens à peine d'attaquer votre bouquin par son début.
    Ces questions me passionnent au point que j'y verrais bien les germes d'un nouveau paradigme scientifique.

  5. Axel Répondre | Permalink

    Je ne suis pas logicien mais juste amateur de logique... Je me pose une question sur le lien à faire entre le théorème d'accélération de Gödel et le concept de mesure de complexité ("longueur") ?

    Une démonstration n'est elle pas simple en terme de complexité si elle est réductible Log-space (P complète) ? Ainsi, comme la montré Chee Yap, le calcul de pi est simple car dans L (car sa mesure d’irrationalité est positive et pi est BBP like) ? J'ai toujours envisagé la relativité générale ainsi : C n'est pas une vitesse limite mais une accélération limite...

  6. gilbert chauvaux Répondre | Permalink

    à propos du livre "La logique, un aiguillon pour la pensée" page 58 "la complexité, cause de l'indécidabilité" , mesure d(E) de Calude et Jurgensen = K(E) - longueur(E)
    qui pourrait être très grand. En fait, comment la complexité peut-elle être supérieure de très peu à la longueur ? il y a toujours un programme qui se contente d'écrire E qui est stocké en mémoire et qui est d'une longueur un peu supérieure à E

    • Jean-Paul Delahaye Répondre | Permalink

      Je corrige votre question qui je crois contient une typo :
      Question : «En fait, comment la complexité peut-elle être très supérieure à la longueur ? il y a toujours un programme qui se contente d'écrire E qui est stocké en mémoire et qui est d'une longueur un peu supérieure à E»
      Réponse.
      Lorsqu'on impose aux programmes d'être autodélimités (on doit pouvoir savoir quand on lit le programme qu'on est arrivé à la fin) ce qui est le cas souvent quand on parle de complexité de Kolmogorov (car cela permet une théorie plus satisfaisante ; Gregory Chaitin par exemple se place toujours dans ce cas) alors quand on utilise des programmes de type "print s" (c'est l'idée que vous évoquez) il faut indiquer la fin de s. Si on le fait en indiquant avant s sa longueur, cela coûte ln(longueur(s)) en longueur de programme. Aucun moyen ne permet de le faire avec un accroissement indépendant de la longueur de s, et c'est pour cela que la différence K(E) - longueur(E) peut être grande.

Publier un commentaire