From madore@clipper.ens.fr Tue Jul 10 18:34:42 2001
Article: 936 of ens.forum.sciences
Path: eleves!not-for-mail
From: madore@clipper.ens.fr (Gro-Tsen)
Newsgroups: ens.forum.sciences
Subject: Re: affligeant
Date: Tue, 10 Jul 2001 16:34:42 +0000 (UTC)
Organization: Forum.
Lines: 186
Sender: madore@clipper.ens.fr
Message-ID: <9ifar2$bno$1@clipper.ens.fr>
References: <9iep80$mv2$1@clipper.ens.fr> <9ies93$9br$1@clipper.ens.fr> <9ieumk$1of$1@clipper.ens.fr> <9ievsj$6do$1@clipper.ens.fr>
NNTP-Posting-Host: clipper.ens.fr
X-Trace: clipper.ens.fr 994782882 12024 129.199.129.1 (10 Jul 2001 16:34:42 GMT)
X-Complaints-To: forum@clipper.ens.fr
NNTP-Posting-Date: Tue, 10 Jul 2001 16:34:42 +0000 (UTC)
X-Newsreader: Flrn (0.5.0pre0 - 10/00)
X-Start-Date: 10 Jul 2001 15:48:23 GMT
Xref: eleves ens.forum.sciences:936

Note aux précédents vulgarisateurs : vous n'êtes pas particulièrement
doués !  Expliquer l'entropie en supposant qu'on sait ce que c'est
qu'un « système fermé », ce n'est pas top ; ni expliquer le théorème
d'incomplétude de Gödel en supposant qu'on sait ce que c'est que
« démontrer l'absurde ».

Marie-Lan in litteris <9ievsj$6do$1@clipper.ens.fr> scripsit:
> David Monniaux in litteris (sciences:923) scripsit :
>> * le Théorème d'Incomplétude de Gödel (curieusement, on ne parle jamais
>> du théorème de complétude), parfois censé démontrer la supériorité de
> 
> C'est quoi ?

Au tout début du XXe siècle, deux logiciels britanniques, Bertrand
Russell (celui-ci est connu pour plein d'autres raisons) et Alfred
North Whitehead ont entrepris l'édition d'un ouvrage monumental appelé
(en l'honneur de Newton) : « Principia Mathematica ».  L'idée, dont la
motivation vient notamment (et surtout) de David Hilbert, c'est de
codifier complètement les mathématiques.  Autrement dit, la
démonstration doit devenir une sorte de jeu formel, un peu comme les
échecs si on veut, dont la découverte dépend peut-être de l'intuition,
mais dont la vérification est totalement mécanique.  C'est-à-dire que
Russell et Whitehead codifient complètement les principes du
raisonnement mathématique, décrits en anglais mais de façon très
précise et rigoureuse, puis font un certain nombre de postulats, et
ensuite utilisent ces règles et ces postulats pour faire des
démonstrations formelles qui, en théorie, devraient être capables de
continuer jusqu'à recapturer la totalité des mathématiques connues à
ce jour.

C'est l'école « formaliste ».  De nos jours on a de meilleures
formalisations des mathématiques (notamment celle d'Ernst Zermelo et
Abraham Fraenkel, appelée ZF, qui construit la théorie des ensembles)
que celle qu'utilisaient Russell et Whitehead, mais on continue sur
cette idée fondamentale que la vérification théorique d'un
raisonnement mathématique est totalement mécanique, et ne fait appel à
aucune intuition.

Voilà qui est fort beau.  Maintenant, le problème c'est qu'on n'est
pas trop sûr de ne pas s'être trompé quelque part.  Notamment, se pose
l'épineuse question : comment être sûr que notre système formel ne
permet pas de démontrer « 1=2 » (ou n'importe quelle autre affirmation
« évidemment fausse ») ?  (Peut-être que les règles ne sont pas assez
strictes dans leur application ; peut-être que les axiomes ne
correspondent pas bien à la « réalité » platoniste ; peut-être qu'on a
fait une erreur idiote quelque part dans la description ; peut-être
que c'est quelque chose de fondamentalement impossible que de
formaliser les mathématiques sans contradiction.  En fait, personne ne
croit sérieusement à tout ceci.)

En fait, ce qu'on voudrait, c'est être sûrs que le système construit
ne permet pas de démontrer à la fois une chose et son contraire : à la
fois A et non-A.  Si tel était le cas (pour *n'importe quel* A), les
règles établies du système permettraient *ipso facto* de démontrer
*n'importe quelle affirmation*.  Autrement dit, le système n'aurait
absolument aucun intérêt, sa notion de « démonstration » étant
tautologique.

On voudrait donc, si c'est possible, pouvoir *démontrer
rigoureusement* que le système n'est pas de cette sorte.  Et pour que
la démonstration soit vraiment rigoureuse, il faudrait qu'elle fût
dans le système lui-même.

Cela implique, pour commencer, de formaliser dans le système
mathématique, le système mathématique lui-même.  C'est l'étape de
« réflexion » (ou de « codage de Gödel », parce que Gödel l'a décrit
précisément, et a eu le génie d'exploiter ça jusqu'au bout, mais
l'idée était implicite avant lui).  Alors que la description des
règles du système (par exemple, et surtout, les *Principia
Mathematica*) était donnée en anglais par Russell et Whitehead, on se
propose donc de traduire *dans les *Principia Mathematica** les règles
des *Principia Mathematica*.  Ce que fait Gödel.  À ce moment-là, le
système « parle de lui-même », de ses règles et de ses preuves.  (Ceci
dit, il ne peut pas « dire » n'importe quoi ; par exemple, la
faiblesse du formalisme ne permet pas d'y écrire l'affirmation dont le
contenu intuitif serait « si la proposition A est démontrable, alors
la proposition A est vraie » - cela est une limitation assez
fondamentale.)

On peut alors chercher à écrire dans le système formel la proposition
qui dit « le système formel ne permet pas de démontrer à la fois A et
non-A » : la consistance du système.  Puis chercher à la démontrer.
Épistémologiquement, cela serait d'un intérêt douteux même si on y
arrivait (le système dit « je ne dis pas de conneries », mais comment
sait-on qu'il ne dit pas de conneries, justement ? car après tout,
s'il en dit, le fait qu'il n'en dise pas peut très bien en être une,
etc.) ; peut-être que l'idée d'Hilbert était de trouver une
démonstration si simple qu'elle nous convainc au-delà du formalisme.
Mais de toute façon, Gödel détruit cet espoir : dans les *Principia
Mathematica* (ou dans tout système au moins assez fort pour modéliser
ce qui s'appelle les « fonctions récursives », ou, de façon
équivalente, « l'arithmétique de Peano », car c'est cela qui permet de
mettre en place le codage de Gödel), on ne peut pas démontrer la
consistance du système.

L'idée de Gödel est suffisamment simple pour être vulgarisée (d'où les
erreurs d'interprétation auxquelles elle a donné lieu) et en même
temps extraordinairement rusée (c'est l'éternel « argument diagonal de
Cantor », encore et toujours, principe fondamental du raisonnement qui
a dominé le tournant du XIXe au XXe siècles).

Il considère d'abord une proposition G dont le contenu intuitif est
« il n'y a pas de démonstration de la proposition G », soit, de façon
simplifiée, « je ne suis pas démontrable » (dans le système formel
considéré, qui, pour Gödel, est celui des *Principia Mathematica*).
Cela est un peu rusé (la proposition G parle d'elle-même !), et fait
usage d'idées dues au logicien Willard van Orman Quine, qui sont
semblables aux idées qui permettent d'écrire un programme informatique
qui affiche son propre listing (voir ma page web à ce sujet) ; mais
l'essentiel est que ce soit possible.  Dans ces conditions :

La proposition G n'est pas démontrable.  En effet, si elle l'était,
elle serait vraie (en supposant que le système soit consistant, ce
qu'on fait - hypothèse qui, soit dit au passage, n'a rien de
contradictoire avec le fait qu'on veut démontrer, justement, que cette
hypothèse n'est pas démontrable !).  Mais alors elle ne serait pas
démontrable, puisque justement elle affirme qu'elle ne l'est pas.
Contradiction.  Donc la proposition G n'est pas démontrable.  (Et
pourtant, *par conséquent*, elle est vraie, puisque c'est justement ce
qu'elle affirme.)

(Remarquons que si on avait une proposition G' qui disait « G' n'est
pas *vraie* », on serait en présence d'une véritable contradiction
dans le système.  C'est le fameux « paradoxe du Crétois
[Épiménides] ».  Mais cette proposition G' ne peut pas se formaliser
dans le codage de Gödel, ce qui sauve les meubles.  À la place, on
peut seulement parler de démontrabilité.)  Gödel a donc montré (c'est
son « premier théorème d'incomplétude ») qu'il y a une proposition G
qui, bien que vraie, n'est pas démontrable dans les *Principia
Mathematica*, ou dans *n'importe quel autre système de ce genre*.

Voilà qui est déjà fort.  Mais maintenant, si on regarde le
raisonnement fait deux paragraphes plus haut, quelle est *la seule
hypothèse* faite qui nous permet de conclure que G est vraie (n'est
pas démontrable) ?  C'est, précisément, le fait que le système est
consistant.  C'est la seule hypothèse qui « sort » du système : tout
le reste du raisonnement s'y intègre parfaitement.  C'est donc que
cette hypothèse-là n'est pas démontrable dans le système.  Autrement
dit, le système ne peut pas montrer qu'il est consistant.

C'est un truc absolument diabolique.  C'est d'un génie complètement
fulgurant.  Et d'une efficacité complète.  Et d'une simplicité
biblique.  Hilbert est terrassé.  (Et l'article de Gödel est d'une
brièveté rare.)

Ensuite, on a des interprétations pipo de ce théorème.  La plus
commune est celle-ci : « le système formel est incomplet, il ne permet
pas demontrer que G ; alors que *nous*, *nous* savons que G est
vraie ; c'est donc que nous sommes plus qu'un bête système formel ».
Ce truc se casse la gueule : c'est juste que « nous », pour démontrer
que G est vraie, on a utilisé la consistance du système.  Chose dont
on est absolument convaincu, mais simplement parce que nous sommes
très orgueilleux, et sûrs de nous.  Le système est plus prudent, lui.
On pourrait évidemment prendre les *Principia Mathematica* (PM) et y
ajouter un axiome (Consis(PM)) qui dit « les *Principia Mathematica*
sont consistants » : cela donnerait un nouveau système, PM2, qui est
capable de montrer G, et qui « sait » que Consis(PM) ; mais PM2 ne
peut pas montrer Consis(PM2), toujours par le théorème de Gödel.  Et
on peut continuer ce petit jeu très loin : il s'y pose des problèmes
assez subtils dans lesquels je ne vais pas rentrer.  Mais ce qui est
sûr, c'est que la conclusion naïve « nous sommes Plus Forts que PM »
est une connerie.

Ensuite, il faudrait mentionner le théorème de *complétude* de Gödel.
Celui-ci dit que si quelque chose n'est ni démontrable ni réfutable,
alors il y a une certaine « notion de vérité » (un « modèle ») dans
laquelle c'est vrai, et une certaine notion de vérité dans laquelle
c'est faux.  Là aussi, il y aurait beaucoup à dire (et beaucoup de
conneries racontables), mais je ne vais pas m'y lancer.  L'interaction
entre les deux théorèmes (complétude et incomplétude) fait des
étincelles particulièrement jolies à voir.

Pour en savoir plus (sur le théorème d'incomplétude, la thèse de
Church-Turing, les quines, et tout le reste), la référence
habituelle : *Gödel, Escher, Bach* de Hofstadter.

>> * le 2ème Principe de la Thermodynamique
> 
> 
> C'est quoi ?
> 
> --ML, qui bulle au bureau et qui aimerait s'instruire

Pas le temps maintenant.  Peut-être plus tard.

En attendant, j'aimerais savoir si j'ai été compréhensible.