Hady Ba's weblog

[Adleman2] Ce que fît M. Gödel

Posted in Philosophie, Science by hadyba on septembre 26, 2009

godel

« Nous devons savoir et nous saurons. »

David Hilbert

J’ai écrit assez vite le post d’hier d’avant-hier puis une fois à la maison, j’ai réalisé que c’était légèrement arrogant d’accuser d’arrogance un prix Turing sans même argumenter! Je vais donc écrire deux posts pour expliquer pourquoi je ne suis pas convaincu par le parallélisme d’Adleman entre mécanique quantique et logique mathématique. Nous parlerons de Gödel aujourd’hui et de MQ la prochaine fois.

§§§§§§§§§§§§

Comme souvent en science, c’est la faute aux grecs1. En l’occurrence, Euclide avait, dans ses Éléments, reconstruit toute la géométrie de son époque en partant de quelques postulats indémontrables et en démontrant le reste. Parmi ces postulats, il y en avait un, le cinquième, dont on soupçonnait qu’il n’était pas indémontrable. Ce postulat affirmait que:

[Ax.5] Par un point extérieur à une droite ne passe qu’une et une seule droite parallèle.2

Les mathématiciens de la fin du XIXe siècle essayeront de démontrer ce « postulat » par l’absurde. L’idée est de remplacer [Ax.5] par un postulat contradictoire puis de développer le système comme si de rien n’était. Si [Ax.5] est vraiment une vérité du système, nous aboutirons à des contradictions ce qui prouvera la fausseté de la proposition qui a remplacé [Ax.5] et par là même la vérité de [Ax.5]. Il y a deux contradictoires à [Ax.5] que nous nommerons [Ax.5bis] et [Ax.5ter]. Ce sont les propositions suivantes:

[Ax.5bis] Par un point extérieur à une droite passent une infinité de droites parallèles.

[Ax.5ter] Par un point extérieur à une droite ne passe aucune droite parallèle.

Propositions absurdes n’est-ce pas? Sauf que nos géomètres effarés construiront des systèmes géométriques totalement consistant en partant de chacun de ces postulats! Jusque là, les mathématiciens pensaient que leur discipline était un vaste système totalement cohérent dont tous les pans allaient finalement s’imbriquer3. L’idée était qu’en partant d’une poignée de postulats, et en appliquant strictement les règles de démonstration, on révélerait toutes les vérités mathématiques. La cohérence était le maitre-mot et aucune vérité ne pouvait être contradictoire avec une autre parce que le contraire d’une vérité est une fausseté. Or, avec les géométries non-euclidiennes, on avait manifestement des systèmes non contradictoires qui partaient pourtant de prémisses incompatibles. Frege résumait assez bien le désarroi de ses collègues en écrivant:

On ne peut servir deux maitres à la fois; on ne peut servir à la fois le vrai et le faux. Si la géométrie euclidienne est vraie, alors la géométrie non-euclidienne est fausse; et si la géométrie non-euclidienne est vraie, c’est la géométrie euclidienne qui doit être fausse.

Après ce premier moment de choc, les mathématiciens, sous l’impulsion de David Hilbert, redéfiniront leur discipline. Quand on y réfléchit, les mathématiques ne sont pas une science de la nature et n’ont pas à avoir des axiomes conformes au réel ou bien un système unique d’axiomes. L’important, c’est la rigueur des démonstrations et le fait que l’édifice que l’on construit soit cohérent de part en part. Le Programme de Hilbert consistera à asseoir définitivement la légitimité des mathématiques en réécrivant toutes les parties de cette discipline en s’assurant de bien séparer axiomes et théorèmes et en vérifiant que ces derniers étaient rigoureusement démontrés. Pour accomplir ce programme, il fallait:

  1. trouver un langage d’exposition qui permettrait de formaliser toutes les mathématiques

  2. s’assurer que ce langage est consistant i.e. que l’on ne démontrerait pas une chose et son contraire dans ce langage en partant des mêmes axiomes

  3. s’assurer que ce langage est complet i.e. que pour toute proposition vraie de ce langage, il existe une procédure permettant de la démontrer

Je vous épargne les détails mais en 1929 il avait déjà été démontré que l’on pouvait reconstruire toutes les mathématiques en se fondant sur l’arithmétique et que la logique du premier ordre était un langage d’exposition adéquat à l’arithmétique. Il suffisait donc de démontrer la consistance et la complétude de la logique du premier ordre pour que le programme de Hilbert fût accompli. En cette année 1929, Gödel prouvait la consistance de la logique du premier ordre. Il ne restait plus qu’à prouver la complétude de cette logique pour que le pénible chaos causé par l’apparition des géométries non-euclidiennes soit oublié.

En 1931, Gödel trouve une astuce pour démontrer la complétude de la logique du premier ordre. En gros4, son approche consiste à coder dans le langage une formule du métalangage G qui se traduirait: G« La formule G n’est pas démontrable. » puis il montre que G est démontrable dans le langage si et seulement si sa négation l’est également dans ce même langage. Étant donné qu’il avait déjà été prouvé que le langage est consistant, cela veut dire que les outils formels du langage ne permettent pas de démontrer G. Dans ce cas, soit G est faux, soit nous avons construit une formule indécidable. Gödel montre que G est une proposition arithmétique vraie. Cela veut donc dire qu’il y a une proposition dont nous savons qu’elle est vraie mais que nous ne pouvons démontrer. En fait, Gödel montre que dans tout système logique consistant et suffisant pour formaliser l’arithmétique, il y a des propositions indécidables i.e. dont nous savons qu’elles sont vraies mais que nous ne pouvons démontrer dans le système. L’on en conclut que les axiomes de l’arithmétique sont incomplets. Étant donné que dans le programme de Hilbert l’arithmétique devait servir de fondement à toutes les mathématiques, cela signifie que cette idée selon laquelle une fois défini le bon système d’axiomes et les bonnes règles de déduction, nous pouvons déployer tranquillement notre virtuosité mathématique et démontrer tous les théorèmes mathématiques est fallacieuse. Il y aura toujours dans le système des théorèmes dont nous savons qu’ils sont vrais mais que nous ne pourrons démontrer dans le système.

Il est très important de comprendre que Gödel ne montre pas simplement qu’il y a des propositions indécidables mais qu’il y a dans chaque système mathématique des propositions indécidables à l’intérieur de ce système mais dont on peut démontrer la vérité ou la fausseté en sortant du système et en utilisant un formalisme plus puissant. C’est cela qu’utilise Adleman quand il affirme que les mathématiciens ne transfèrent pas leur ignorance à la discipline mais à leur connaissance. Si vous êtes platonicien, comme le sont beaucoup de mathématiciens, vous considérerez qu’il y a là dehors un monde mathématique objectif que nous saisissons grâce aux outils mathématiques que nous développons. Dans ce monde abstrait, la proposition G est soit vraie, soit fausse et si elle est indécidable dans le formalisme que nous utilisons pour faire des maths, c’est là une limitation de nos outils formels plutôt que le reflet d’une propriété du monde mathématique. Il me semble qu’il y a une influence de ce platonisme implicite dans le parallèle que fait Adleman entre MQ et logique mathématique.

Dernière chose, cela devrait aller sans dire mais disons le quand même, Gödel ne montre pas que Dieu existe, que la télépathie et la magie fonctionnent, que nous ne pouvons pas comprendre notre propre cerveau et tutti quanti. Tout ce qu’il a prouvé, c’est qu’un système formel pouvant contenir l’arithmétique n’engendrera pas tous ses théorèmes et sera donc incomplet. Rien de mystique là dedans.

Bon next time nous parlerons de mécanique quantique et vous verrez (j’espère) que je ne suis pas aussi prétentieux que ma désinvolture le laissait penser hier.

§§§§§§§§§§§§§§§

1Ou des Égyptiens si vous préférez Cheikh Anta Diop

2Je viens juste de vérifier dans Les miscellanées de Mr. Schott et il n’a pas listé ce postulat parmi ceux qu’il donne page 47… du coup, je ne fais plus tant confiance que ça à Ben Schott!

3Accessoirement, ils pensaient que la géométrie avait vocation à révéler la structure de l’espace réel et dans le monde tel que nous le connaissons une seule droite parallèle passe par un point extérieur à une droite.

4Mais alors là, vraiment en gros. Le paragraphe qui suit n’est pas très rigoureux et je passe d’énoncés sur la logique à des énoncés sur l’arithmétique sans détailler forcément le lien. Faites-moi confiance ou lisez ce livre. Lisez-le de toute manière: c’est l’une des meilleures présentations du papier de Gödel que je connaisse. Avec un peu de concentration, vous comprendrez tout.

About these ads
Tagged with: , , ,

2 Réponses

Souscrire aux commentaires par RSS.

  1. Miguel Lerzundi said, on septembre 26, 2009 at 1:39  

    Tres eclaircissante. Toutefois, est-ce que tu sais pour de vrai que Gödel n’esperait ‘démontrer’ que Dieu existe? Est-ce qu’il a jamais fait une déclaration au propos de ça? Je me declare dans la plus complète ignorance

  2. hadyba said, on septembre 26, 2009 at 5:51  

    Hello Miguel:

    En fait Gödel avait effectivement formalisé la preuve ontologique d’Anselme mais n’avait pas publié le papier bien qu’il fut satisfait de cette formalisation parce qu’il craignait, selon Oskar Morgenstern, que l’on ne pense qu’il croyait en Dieu alors que sa seule préoccupation était logique. Il y a cette entrée dans wikipedia sur sa preuve ontologique. Pour autant que je sache, cette preuve n’a rien à voir avec ses théorèmes d’incomplétude.

    Hao Wang semble cependant dire que Gödel était vraiment croyant et il me semble qu’il est une meilleure autorité sur ce point que OM.


Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s

Suivre

Recevez les nouvelles publications par mail.

Joignez-vous à 493 followers

%d bloggers like this: