3. Notion de méta-système
Au 2.1.3. , nous
avons déploré de devoir "tricher" pour démontrer qu'une expression du S.F. "peu"
était un non-théorème. Nous allons à présent formaliser cette tricherie.
Nous sommes sortis du S.F. "peu" pour aller
faire de l'arithmétique. Or l'arithmétique constitue elle-même un S.F., le S.F
"AF" (Arithmétique Formelle), décrit par les axiomes de Peano.
![](chap3_fichiers/fig24.gif)
Nous dirons que "AF", qui est le SF dans
lequel nous allons pour résoudre les problèmes insolubles dans "peu", est le
méta-système de "peu".
Au 2.1.5., nous
avons vu que l'interprétation, bien que non équivalente au S.F., pouvait guider
une démonstration. Si par exemple je demande si "uuuuuuuupuuueuuuuuuuuu" est un
théorème, vous allez traduire par "8+3=9", et vous dire que c'est probablement
un non-théorème, donc qu'il faut chercher une astuce, par exemple en faisant de
l'arithmétique. Si par contre je propose : "uuuuupuuuuueuuuuuuuuuu", vous
traduisez "5+5=10", et vous vous dites que ça vaut la peine de développer
l'arbre jusqu'à profondeur 11.
Formalisons cela, en nous plaçant dans le
méta-système AF, et en démontrant le méta-théorème suivant :
une expression
est un théorème de "peu" si et seulement si elle est de la forme : ux
p uy e ux+y
- R1 et R2 commutent
- partant de l'axiome upueuu, j'applique (x-1) fois R1, ce qui me
donne ux p u e ux+1
- puis j'applique (y-1) fois R2
Dorénavant donc, si on me
propose une expression,
- je compte les "u" jusqu'au "p"
- je compte les "u" jusqu'au "e"
- je fais la somme
- je compte les "u" restant
- si je trouve le nombre voulu, c'est un théorème, sinon, c'est un
non-théorème
J'ai donc une
procédure qui répond à tout coup : mon système, qui était semi-décidable, est
maintenant décidable. De plus, cette procédure est en O(n), au lieu du
O(2n/2) du développement de l'arbre. J'ai donc gagné qualitativement
et quantitativement!
Au début du XXème siècle,
Hilbert, dans son célèbre "programme", a posé, entre autres, une question que
nous pourrions reformuler ainsi : puisque le passage de "peu" à son méta-système
"AF" est si fructueux, dans quel système peut-on passer quand on a un problème
insoluble dans "AF"?
Kurt Gödel a répondu en 1930 : le méta-système de AF,
c'est... AF.
![](chap3_fichiers/fig25.gif)
Pour démontrer que AF
est son propre méta-système, il associe à chaque symbole un code
numérique, et fait ensuite des opérations sur les codes des expressions, nous
n'entrerons pas dans les détails. Mais, à peine un an plus tard, ayant poursuivi
ses travaux sur cette question, il fait exploser une énorme bombe : puisque AF
est son propre méta-système, il existe des expressions dont on ne peut rien dire
(théorème ou non-théorème) ou dont on peut dire n'importe quoi ! Nous
n'entrerons pas dans les détails, mais donnerons simplement deux
pseudo-exemples.
Considérons l'ensemble des entiers positifs que l'on peut
écrire en français avec moins de 200 caractères ASCII. Appelons-le E. Cet
ensemble n'est pas vide. Exemples :
10 , dix , 10 puissance 10 , le nombre
de protons de l'univers , etc.
Mais il est fini. Donc il admet un
complémentaire dans N, appelons-le C. Considérons le complémentaire dans N de
l'ensemble des entiers positifs que l'on peut écrire en français avec moins de
200 caractères ASCII. Ce complémentaire est infini, donc non vide, donc
admet un plus petit élément. Considérons le plus petit élément du
complémentaire dans N de l'ensemble des entiers positifs que l'on peut écrire en
français avec moins de 200 caractères ASCII.
Il est dans C, puisqu'il en
est le plus petit élément. Mais il est dans E, puisque ma phrase ne fait pas 200
caractères !
Ne cherchez pas l'astuce : en comptant les caractères
d'une formule arithmétique, je me suis exposé à ce qu'avait démontré
Gödel. Une autre?
Cette phrase contient quatre fois la
consonne "c". Alors :
Celle-ci contient
cinq fois la consonne "c". Euh, pardon
:
Celle-ci contient six fois la consonne
"c". !!!
Cette découverte est très grave, car elle met fin à 2400
ans de travaux conduits dans l'espoir de formaliser le raisonnement et le
discours. Elle est très fructueuse car elle relance la recherche sur d'autres
terrains (voir théorie des Topoï).
Chapitre précédent
Chapitre suivant
Table des matières
Attention, ce fichier n'est peut-être plus d'actualité s'il est dans votre
cache; vérifiez la date du copyright, et faites éventuellement un 'reload'
©
Jean-Marc Fouet, 25-10-1999