Le mathématicien Kurt Gödel a consacré ses travaux
à la rationalité, alors que sa vie privée en était
parfois dépourvue.
Les propositions indécidables
Le personnage qui est représenté sur la photographie ci-dessus
n'est pas connu du grand public. Pourtant, ses théorèmes
d'incomplétude et ses autres résultats de mathématiques
ou de logique ont ébranlé les mathématiques et l'informatique.
Toute sa vie, il rechercha la rationalité, mais dut lutter contre
une profonde fragilité mentale.
Gödel a démontré que les méthodes mathématiques
utilisées depuis Euclide ne peuvent révéler toutes
les propriétés de l'ensemble des nombres entiers naturels.
Sa découverte, qui bouleversa les mathématiques créées
au XXe siècle,
a relancé la recherche de nouvelles voies d'étude et provoqué
un débat philosophique sur la nature de la vérité.
Les techniques inventées par Gödel, qui sont applicables aux
algorithmes de calcul, ont également posé les fondations
de l'informatique moderne.
Gödel naît le 28 avril 1906 à Brno, à 180 kilomètres
au Sud-Est de Prague, en République tchèque. Il est le cadet
des deux enfants de Rudolf et Marianne Gödel, des Allemands expatriés
dont les familles travaillaient pour l'industrie textile locale. La famille
ne comptait pas d'intellectuels, et son père n'avait reçu
qu'une formation en techniques commerciales. Toutefois, ce dernier était
ambitieux et travailleur : il sera progressivement directeur, puis
actionnaire d'une importante usine de textile de Brno. Suffisamment enrichi,
Rudolf Gödel acquiert une maison dans un quartier chic et envoie
ses fils dans des écoles privées
de langue allemande, où tous deux font de brillantes études.
De toute sa scolarité primaire et secondaire, le jeune Kurt n'a
qu'une seule fois une note inférieure au maximum – en mathématiques!
Pourtant, ses talents restent insoupçonnés, car, malgré
son insatiable curiosité (il est surnommé Monsieur Pourquoi),
il est introverti, sensible et plutôt maladif. Vers l'âge
de huit ans, il contracte un rhumatisme articulaire aigu qui, bien que
sans séquelles physiques, l'éloigne de l'école assez
longtemps. Cette maladie est probablement l'une des causes
de son hypochondrie.
L'introverti
LES DEUX FRÈRES
GÖDEL, Kurt et Rudolf étaient très proches ; ils
se sont peu à peu éloignés à l'âge adulte.
Ce cliché de studio date de 1908.
En 1924, diplômé du lycée technique de Brno, Gödel
quitte son pays natal pour l'Université de Vienne, où son
frère a commencé ses études de médecine quatre
ans plus tôt. Après la Première Guerre mondiale et
la chute de l'empire austro-hongrois, Vienne est en ruine, mais le prestige
de l'Université est intact. Ainsi, malgré les privations
matérielles, la Vienne de l'entre-deux-guerres est un centre scientifique
littéraire et philosophique très actif.
Initialement inscrit en physique, Gödel s'oriente vers les mathématiques
dès qu'il a suivi les cours de Phillip Furtwängler et de Hans
Hahn (1879-1934). Il est vite remarqué : deux ans seulement
après son arrivée, il est invité dans le groupe de
travail fondé en 1924 par Hahn et par le philosophe néo-positiviste
Moritz Schlick (1882-1936). Ce groupe, qui deviendra le Cercle de Vienne,
est inspiré des écrits d'Ernst Mach (1838-1916), rationaliste
pour qui seules la logique et l'observation empirique ont une valeur explicative ;
la métaphysique est écartée.
Grâce au Cercle, Gödel rencontre des savants tels que le philosophe
des sciences Rudolf Carnap (1891-1970) ou le mathématicien Karl
Menger (1902-1985). Il se familiarise avec la logique mathématique
et la philosophie, et, en particulier, avec les écrits de Ludwig
Wittgenstein (1889-1951), dont la réflexion sur l'aptitude du langage
à parler de lui-même a peut-être poussé Gödel
à explorer les problèmes équivalents en mathématiques.
Avec certains membres du Cercle, dont Carnap, Hahn et le physicien Hans
Thirring, il s'intéresse également aux phénomènes
parapsychologiques. Des années plus tard, il confiera à
son ami économiste Oskar Morgenstern (1902-1977) que, dans un futur
lointain, on s'étonnera que les scientifiques du XXe siècle
aient découvert les particules physiques élémentaires,
sans même envisager la possibilité de facteurs psychiques
élémentaires.
Cependant, Gödel ne partage pas la vision philosophique positiviste
du Cercle. Il est platonicien : en dehors des objets, un monde de
concepts existe, accessible par l'intuition. Ainsi, toute proposition
a une «valeur de vérité» (être vraie ou
être fausse), que cette valeur ait été établie
ou non par les mathématiques ou par un moyen expérimental.
Il admettra ultérieurement que cette philosophie a facilité
ses intuitions mathématiques.
Observateur attentif et brillant, Gödel s'exprime rarement lors des
discussions du Cercle, sauf lorsqu'elles concernent les mathématiques.
Timide et solitaire, il a peu d'amis intimes (cependant, il apprécie
la compagnie des femmes, qui le trouvent séduisant). Après
1928, il délaisse peu à peu le groupe et s'investit dans
un séminaire de mathématiques organisé par Menger.
Gödel participe à la publication annuelle des actes ;
il publiera ainsi une dizaine d'articles.
Un génie réservé
C'est l'époque à laquelle Gödel acquiert une réputation
internationale en logique mathématique, notamment grâce à
deux articles : sa thèse, soutenue à l'Université
de Vienne en 1929 et publiée l'année suivante, et son traité
Sur les propositions formellement indécidables des Principia Mathematica
et des systèmes apparentés, publié en allemand en
1931 et présenté comme thèse d'habilitation à
l'enseignement en 1932. Dans les Principia Mathematica de Bertrand Russell
(1872-1970) et d'Alfred Whitehead (1861-1947), les auteurs proposent la
logique comme fondement des mathématiques. Ils résolvent
un problème posé en 1928, par David Hilbert (1862-1943)
et par Wilhelm Ackermann (1896-1962) dans leurs Fondements de la Logique
théorique : Hilbert et Ackermann y énoncent des
règles de manipulation d'expressions logiques composées
de connecteurs (et, ou...), de quantificateurs (pour tout, il existe...),
et de variables (nombres, propositions, ensembles...).
Les règles de manipulation admises ajoutées aux axiomes
d'une théorie mathématique permettent-elles de déduire
toutes
les propositions vraies pour toute structure vérifiant les axiomes?
Plus simplement, peut-on démontrer tout ce qui est vrai pour toutes
les interprétations des symboles?
La réponse attendue était oui, et Gödel le confirme
dans sa thèse intitulée La complétude du calcul des
prédicats du premier ordre, où il établit que les
principes de la logique prouvent tout ce qui est vrai à partir
d'un ensemble d'axiomes donné. Cependant, il ne démontre
pas que les axiomes alors admis pour la théorie des nombres permettent
de démontrer toutes les propositions à propos des nombres.
Les axiomes de la théorie des nombres avaient été
proposés par le mathématicien italien Giuseppe Peano (1858-1932)
en 1889 ; ils incluent l'axiome de récurrence, qui affirme
que toute propriété vraie pour zéro, et vérifiée
par le nombre n+1 lorsqu'elle est vraie pour le nombre n, est vraie pour
tout entier naturel. Cet axiome semble évident, mais il gêne
les mathématiciens parce qu'il concerne les propriétés
des nombres plutôt que les nombres eux-mêmes : c'est
un axiome du second ordre, qui semble trop éloigné des nombres
pour définir ces derniers. De la même manière, savoir
qu'un ballon est bleu n'indique pas ce qu'est un ballon.
LE COUPLE ADÈLE PORKERT ET KURT GÖDEL était très
uni. Ils sont ici à la terrasse d'un café de Vienne, pendant
leurs longues fiançailles. Adèle Porkert protégeait
Gödel de ses peurs irrationnelles et était souvent la seule
personne à pouvoir le convaincre de manger. Plus que quiconque,
elle a contribué à le maintenir en vie et en état
de travailler.
L'axiome de récurrence avait été reformulé
sous la forme d'un groupe infini d'axiomes identiques, qui se rapportaient
à des formules spécifiques plutôt qu'aux propriétés
générales des nombres. Malheureusement, le logicien norvégien
Thoralf Skolem avait démontré que ces axiomes ne caractérisent
pas seulement des nombres naturels : ils sont également vérifiés
par d'autres structures nommées entiers non standards.
Le théorème de complétude de Gödel indique que
l'on peut démontrer toutes les propositions qui découlent
des axiomes ; cependant une proposition qui est vraie pour les nombres
naturels, mais fausse pour un autre système d'éléments
qui vérifient les mêmes axiomes, est alors indémontrable
(voir l'encadré). Les mathématiciens dédaignent la
restriction en espérant qu'il n'existe pas d'entités similaires
aux nombres.
L'article que Gödel publie en 1931 bouleverse alors les mathématiques.
Il montre que certaines propositions
vraies pour les nombres naturels sont indémontrables : il
existe des objets qui vérifient les axiomes de la théorie
des nombres, mais se comportent différemment à d'autres
égards. En prenant toutes les propositions vraies pour axiomes,
on contournerait ce «théorème d'incomplétude» ;
mais alors comment savoir si les propositions sont vraies? Gödel
montre que, lorsque les axiomes sont décrits par un ensemble de
règles mécaniques, le choix des axiomes n'évite pas
la difficulté : quand elles sont vraies pour les nombres naturels,
d'autres propositions vraies sur ces nombres restent indémontrables.
Par exemple, lorsque les axiomes ne se contredisent pas mutuellement,
cette non-contradiction, correctement codée
en une proposition numérique, est formellement indécidable,
c'est-à-dire ni démontrable ni réfutable à
partir des axiomes. La démonstration de la non-contradiction nécessite
donc des principes plus puissants que les axiomes eux-mêmes.
Ce dernier résultat ruine le programme de David Hilbert, qui voulait
renforcer les fondements des mathématiques
et déduire la cohérence des théories mathématiques
complexes de celle de théories plus simples. Pour Gödel, en
revanche, les théorèmes d'incomplétude ne réfutent
pas l'inanité de la méthode axiomatique, mais ils montrent
que la démonstration de théorèmes ne peut être
complètement mécanisée et ils justifient l'intuition
en mathématique.
Les concepts et les méthodes introduits par Gödel sont au
centre de la théorie de la récurrence,
centrale en informatique. Ses idées sont à l'origine de
nombreux résultats sur les limites des procédures informatiques,
par exemple, sur le caractère indécidable de la durée
d'exécution des programmes : pour une donnée d'entrée
et un programme fixé, un ordinateur s'arrêtera-t-il finalement,
en produisant une donnée de sortie, ou finira-t-il dans une boucle
infinie? De même, aucun programme ne peut détecter tous les
programmes qui modifient le système d'exploitation d'un ordinateur
(les virus, par exemple) sans modifier lui-même ce système.
Le refuge aux États-UnisGödel passe l'année universitaire
1933-1934 à l'Institut des études avancées de Princeton,
où il enseigne son théorème d'incomplétude.
Une «dépression nerveuse» peu après son retour
à Vienne l'empêche d'y retourner l'année suivante.
Guéri à l'automne 1935, il part l'année d'après,
mais il rechute un mois après son arrivée et ne reprend
son enseignement qu'au printemps 1937, à Vienne.
Tant qu'on ne disposera pas du dossier médical de Gödel (il
était suivi par un psychiatre de Princeton), la maladie de Gödel
restera mystérieuse. Elle commence par une hypocondrie : obsédé
par son régime et sa digestion, il note quotidiennement, pendant
plus de 20 ans, sa température et sa consommation de magnésie.
Il redoute initialement un empoisonnement accidentel, mais, vers la fin
de sa vie, il craint qu'on ne veuille le tuer en l'empoissonnant.
Il cesse presque de s'alimenter, tandis qu'il prend de nombreuses pilules
contre une maladie cardiaque imaginaire.
En dehors des crises aiguës, la capacité de travail de Gödel
est peu perturbée par ses problèmes mentaux. Il est soutenu
par Adèle Porkert, qu'il a rencontrée dans une boîte
de nuit de Vienne, pendant ses études.
Son aînée de six ans, Adèle est catholique, divorcée,
danseuse de profession. Les parents de Gödel la jugent dépravée,
mais le couple est très uni, et elle l'aide souvent à surmonter
sa peur grandissante de l'empoisonnement en jouant le rôle de goûteuse.
Ils se marient en septembre 1938, juste avant le retour de Gödel
en Amérique, où il doit présenter ses nouveaux résultats
en théorie des ensembles à Princeton et à l'Université
de Notre-Dame.Ces résultats résolvent des questions anciennes.
À la fin du XIXe siècle, le mathématicien allemand
Georg Cantor (1845-1918) a trouvé un moyen de comparer la taille
des ensembles infinis : on apparie les éléments de
l'ensemble A et ceux de l'ensemble B ; si cet appariement laisse
des éléments de A non appariés, alors l'ensemble
A est plus grand que l'ensemble B. Ainsi Cantor a démontré
que l'ensemble des nombres naturels est plus petit que l'ensemble des
nombres réels. De plus, il a supposé qu'aucun ensemble de
taille intermédiaire n'existe : c'est l'hypothèse du
continu.En 1908, Ernst Zermelo (1871-1953), compatriote de Cantor, a formulé
une liste d'axiomes pour la théorie des ensembles. Parmi cette
liste figure l'axiome du choix, qui stipule que, si l'on considère
une collection infinie d'ensembles disjoints, qui contiennent chacun au
moins un élément, on peut former un ensemble en retenant
un élément de chaque ensemble de la collection.
Malgré son apparente évidence, l'axiome du choix a des conséquences
paradoxales. Par exemple, si on l'accepte, on doit aussi admettre qu'une
sphère est décomposable en un nombre fini de morceaux que
l'on peut séparer et rassembler en une nouvelle sphère de
volume double de la première.
L'axiome du choix est très controversé : les mathématiciens
contemporains de Gödel soupçonnent, à juste titre,
que ni l'axiome du choix ni l'hypothèse du continu ne peuvent être
déduits des autres axiomes de la théorie des ensembles.
Ils craignent que l'utilisation de ces théorèmes dans des
démonstrations ne mènent à des contradictions.
Cependant, Gödel démontre que les deux axiomes sont cohérents
avec les autres.
Les résultats de Gödel en théorie des ensembles répondent
à une question posée par Hilbert en 1900 lors du Congrès
international des mathématiciens.
Malgré leur importance, ils ne lui procurent pas un poste permanent.
Pendant son année passée à Princeton et à
l'Université de Notre-Dame, son autorisation d'enseigner dans les
universités autrichiennes lui est retirée. Pendant l'été
1939, alors qu'il rejoint sa femme à Vienne, il est convoqué
pour un examen médical militaire, et déclaré apte
au service dans les forces armées nazies.
Jusqu'alors Gödel s'est peu soucié de la tournure inquiétante
des événements en Europe. Il s'est intéressé
à la politique et à l'actualité, mais les événements
l'ont peu ému. Son isolement l'a peut-être empêché
de mesurer la gravité
des événements. Il s'intéresse peu à ses collègues
et professeurs, dont beaucoup sont juifs, et reste concentré sur
ses
travaux pendant que le monde s'écroule autour de lui. Avec sa convocation
de l'armée, l'Histoire le rattrape.
Désespéré, sans emploi et menacé par l'incorporation
imminente, il demande le soutien de l'Institut des études
avancées et obtient des visas de sortie. En janvier 1940, le couple
fuit vers l'Est à bord du Transsibérien.
Puis, de Yokohama, ils embarquent pour San Francisco et atteignent enfin
Princeton par le train à la mi-mars. Des
phobies grandissantes Gödel ne quittera plus les États-Unis.
Après plusieurs contrats annuels, il n'est engagé de façon
définitive qu'en 1946. Deux ans plus tard, il prend la nationalité
américaine. À cette occasion, le juge qui lui demandait
son opinion sur la constitution des États-Unis se voit affligé
d'un long discours sur les incohérences logique de ce système.
C'est seulement en 1953 que Gödel est nommé professeur, alors
qu'il est également élu membre de l'Académie américaine
des sciences. On craignait sa maladie mentale : ne disait-il pas
partout que des gaz toxiques fuyaient de son réfrigérateur?
Pendant ces années, son ami Albert Einstein s'occupe de lui de
son mieux, notamment par des promenades quotidiennes. Leurs conversations
apaisaient Gödel.
À son arrivée aux États-Unis, Gödel abandonne
la théorie des ensembles pour se consacrer à la philosophie
et à la relativité. En 1949, il montre que des univers où
le voyage vers le passé est possible sont compatibles avec les
équations d'Einstein. En 1950, il présente ces résultats
au Congrès international des mathématiciens et, l'année
suivante, il donne la prestigieuse conférence Gibbs à la
réunion annuelle de l'Association mathématique des États-Unis.
Entre ces deux discours, il frôle la mort, parce que sa méfiance
envers les médecins lui a fait négliger un grave ulcère.
LES PROMENADES AVEC EINSTEIN
dans le parc de l'Institut des études avancées de Princeton
étaient un des rites qui maintenaient Gödel en activité.
Cette photographie date de 1954.
Le dernier article publié de Gödel paraît en 1958. Il
se renferme ensuite progressivement sur lui-même, et, de plus en
plus amaigri, devient paranoïaque et hypocondriaque.
Sa dernière apparition en public date de 1972, quand l'Université
Rockefeller le fait docteur honoris causa. Trois ans plus tard, quand
on lui décerne la Médaille américaine des sciences,
il n'assiste pas à la cérémonie, pour raison de santé.
Le 1er juillet 1976, quand Gödel atteint l'âge de la retraite
(70 ans), il est nommé professeur émérite de l'Institut.
Toutefois sa femme, qui l'a tant materné, est handicapée
par un accident vasculaire cérébral qui l'a frappée
quelques mois auparavant. Il prend soin d'elle avec dévouement
jusqu'en juillet 1977, lorsqu'elle est opérée d'urgence
et hospitalisée pendant près de six mois.
À ce moment, Morgenstern, l'ami qui a pris la relève d'Einstein
après la mort de celui-ci en 1955 pour s'occuper de Gödel,
meurt d'un cancer.
Gödel se retrouve seul avec sa paranoïa grandissante, et décline
rapidement. Par peur d'un empoisonnement, il cesse de s'alimenter, et
il meurt le 14 janvier 1978.
Adèle Gödel survit trois ans à son mari. À sa
mort, le 4 février 1981, elle lègue les droits des articles
de Gödel à l'Institut des études avancées. La
population hautaine de Princeton l'a toujours tenue à l'écart,
mais elle était fière des travaux de son mari et elle savait
que, sans son soutien, il n'aurait pas pu les mener à bien.
Gödel a publié très peu d'articles de son vivant (Bernard
Riemann est le seul grand mathématicien qui ait publié moins) ;
cependant leur impact a été énorme.
Certains de ses articles, qui étaient écrits à la
main, en gothique, ont été récemment traduits et
publiés
dans le troisième volume de ses Œuvres complètes. Leur
contenu, par exemple sa formalisation de la «preuve ontologique»
de l'existence de Dieu, intéressent aujourd'hui l'attention jusqu'aux
non-mathématiciens.
John Dawson est professeur de mathématiques à l'Université
de Pennsylvanie ; il est l'un de ceux qui ont assuré l'édition
des Œuvres complètes de Gödel.
POUR EN SAVOIR PLUS :
Ernst Nagel, James Newman, Kurt Gödel et Jean-Yves Girard, Le théorème
de Gödel, Le Seuil, 1997.
Douglas R. Hofstadter, Gödel, Escher, Bach, Interéditions,
1998.
Kurt Gödel, Collected Works, vol. 1-3, sous la direction de Solomon
Feferman et al., Oxford University Press, 1986, 1990, 1995.
John W. Dawson, Logical Dilemmas : The Life and Work of Kurt Gödel,
A.K. Peters Ltd., Wellesley, Mass., 1997.
N° 262 août 1999 Pour la Science
Les propositions indécidables
Le résultat le plus célèbre de Gödel concerne
des propositions sur les nombres naturels, vraies mais indémontrables
dans l'arithmétique. La phrase réflexive suivante est un
exemple simple de propositions vraies, mais indécidables,
c'est-à-dire ni démontrables ni réfutables :
«Cette proposition est indémontrable.»
Elle peut être transformée en un nombre selon une méthode
mise au point par Gödel. Ensuite, on montre d'une part que si cette
proposition est démontrable, sa négation l'est aussi :
elle est donc indémontrable.
D'autre part, on prouve qu'elle est néanmoins vraie.
Les équations polynomiales conduisent à des propositions
un peu plus compliquées.
Par exemple, l'affirmation que certaines équations polynomiales
n'ont pas de racines (c'est-à-dire de solutions) entières
est indécidable.
Gödel a démontré que les axiomes qui définissent
les nombres entiers naturels sont incomplets : certaines propositions
vraies de la théorie des nombres sont indémontrables à
l'aide de ces axiomes.
Sa démonstration montre, par conséquent, qu'il existe des
entités, nommées entiers non standards, différentes
des nombres naturels qui obéissent néanmoins à ces
axiomes. Comme tout ce qui est démontré à partir
des axiomes (en rouge) s'applique à toutes les entités qui
obéissent aux axiomes, certaines propositions vraies concernant
les nombres naturels (en bleu, en vert et en rouge) sont nécessairement
indémontrables (en bleu et en vert).
N° 262 août 1999 Pour la Science (1999)
Pour trouver les liens d'origine http://www.pourlascience.com
Les propositions indécidables
(démonstration)
par Jean-Paul Delahaye
L'incomplétude gödélienne concerne-t-elle d'autres
domaines que les mathématiques? Jean-Paul Delahaye est professeur
à l'Université de Lille.
Démonstration des théorèmes d'incomplétude
:
George Boolos spécialiste de la logique de la prouvabilité
(et donc du théorème de Gödel) a récemment
proposé une nouvelle démonstration du second théorème
de Gödel. Avec la démonstration dite sémantique du
premier théorème on a deux raisonnements qui ne retiennent
que l'essentiel des idées originales de Gödel (qui exigent
pour être détaillées plusieurs dizaines de pages).
On s'appuie sur des propriétés élémentaires
faciles à accepter (ou à prouver pour les systèmes
utilisés en mathématiques) et sur une partie technique
de 11 lignes. Nous présentons ici ces démonstrations pour
les personnes que le formalisme et les casse-tête logiques n'effraient
pas.
On se donne un système formel S à propos duquel on fera
une série d'hypothèses qui permettront de prouver pour
S en quelques lignes les deux théorèmes d'incomplétude
de Gödel.
Lorsqu'une formule f du système S est démontrable dans
S on écrit : |- f
La première hypothèse est :
(i) S est assez riche pour que l'on puisse y exprimer la propriété,
notée @ f, qui signifie "il existe une preuve formelle de
f dans S".
Pour obtenir @ f il suffit que le langage du système formel S
contienne celui de l'arithmétique (ou celui des ensembles finis).
En pratique, la formule @ f code minutieusement la définition
de ce qu'est une déduction dans S. Si on devait
écrire @ f ce serait une formule longue. L'existence de @ f est
une découverte positive importante de Gödel.
On fait ensuite l'hypothèse que :
(ii) si |- f alors |- @ f
(si f est démontrable dans S alors @ f est aussi démontrable
dans S)
Cela signifie simplement que la capacité du système S
à faire de l'arithmétique lui permet de démontrer
les formules du type @ f lorsqu'elles sont vraies. On établit
sans mal la propriété (ii) pour les systèmes usuels
utilisés en mathématiques (arithmétique élémentaire,
théorie des ensembles, etc.). On suppose ensuite :
(iii) |- @ (f -> g) -> (@ f -> @ g)
(iv) |- @ f -> @ @ f
Comme pour (ii) ces hypothèses signifient simplement que la formule
@ f est écrite en suivant de près la définition
des déductions dans S et que l'arithmétique de S est assez
puissante. L'hypothèse suivante :
(v) S contient la logique propositionnellesignifie que les raisonnements
usuels (du type si ((A et B) -> C) et A et que B alors je peux en
déduire C) qu'on fait sans cesse dans une démonstration
mathématique sont utilisables dans S. Cette hypothèse
(que ne satisfaisait pas le système formel de la figure 1, trop
élémentaire) est vérifiée par les systèmes
usuels des mathématiques. La propriété :
(*) Si |- f -> g alors |- @ f -> @ g
se déduit de (ii), (iii)
et (v) en procédant comme suit : si |- f -> g, d'après
(ii) on a |- @ (f -> g). En utilisant (iii) et ce qu'on appelle la
règle du modus ponens (vraie en logique propositionnelle) on
a : |- @ f -> @ g.
On désignera par faux une formule de S représentant la
contradiction. On prend une formule f quelconque, et on pose faux =
(f et NON f). Dire que S est consistant, signifie qu'avec S on ne peut
pas déduire faux. Cela s'écrit donc : NON |- faux. Une
formule du système S exprimant que la théorie S est consistante
est donc : NON @ faux. Le second
théorème de Gödel va établir que lorsque S
est consistant cette formule n'est pas démontrable dans S.
Une méthode générale
décrite par Gödel permet dans les systèmes formels
assez riches de construire une formule g qui exprime sa propre non prouvabilité
dans S (là encore il s'agit d'un résultat positif que
les philosophes oublient à la faveur des résultats négatifs).
Nous ferons l'hypothèse que S permet effectivement d'avoir une
formule g telle que :
(vi) |- g <-> NON @ g
Nous supposerons (uniquement pour la démonstration du premier
théorème d'incomplétude)
que S satisfait la propriété de :
(vii) correction de S pour les formules arithmétiques
Cette hypothèse signifie que lorsque S démontre une formule
portant sur les nombres entiers, alors cette formule est vraie des nombres
entiers usuels. La propriété (vii) est vérifiée
en particulier si chaque axiome est vrai et si les règles d'inférences
ne permettent de déduire que des choses vraies à partir
de choses vraies. Dans les systèmes formels pour l'arithmétique,
cette propriété est satisfaite car on ne choisit que des
axiomes et des règles d'inférences vrais
de toute évidence. L'hypothèse (vii) est la seule hypothèse
qui ne puisse se démontrer facilement pour des systèmes
plus riches comme celui de la théorie des ensembles. C'est une
hypothèse dite sémantique car elle se réfère
au concept de formule vraie des nombres entiers usuels. Cette hypothèse
est plus forte que l'hypothèse de consistance qui sera seule
utile pour le second théorème [L'hypothèse (vii)
implique la consistance car si S était inconsistant alors tout
serait démontrable dans S et donc, en particulier, la formule
arithmétique 0=1 ce qui est impossible si (vii) est vraie. ].
La formule @ f est un énoncé arithmétique, donc
si S prouve @ f c'est que ce que dit @ f est vrai, c'est-à-dire
: |- f. Autrement dit :
(**) si |- @ f alors |- f
Gödel dans sa démonstration initiale a préféré
remplacer l'hypothèse sémantique (vii) par une hypothèse
syntaxique (faisant appel uniquement à des considérations
formelles) mais difficile à présenter ici et plus forte
que l'hypothèse de consistance. [Gödel avait adoptée
l'hypothèse d'oméga-consistance : si le S prouve une formule
du type () alors pour un entier n au moins, NON |- NON P(n).]
Premier théorème d'incomplétude de Gödel
Montrons à partir de (i)-(vii) qu'il existe une formule g de
S au moins telle que ni g ni NON g ne sont prouvables dans S (incomplétude).
Comme nos hypothèses signifient à la fois que le système
S est assez puissant et qu'il est consistant on traduira cela en disant
: un système formel ne peut à la fois être puissant,
consistant et complet.
De l'affirmation |- g <-> NON @ g on déduit que |- g ->
NON @ g (logique propositionnelle).
Donc de |- g on déduit |- NON @ g. Il en résulte que si
g est prouvable alors |- @ g (d'après (ii)) et |- NON @ g et
donc le système est inconsistant ce qui contredit l'hypothèse
(vii). Dans S on ne peut donc pas prouver g.
Si on suppose que S permet de prouver NON g c'est-à-dire : |-
NON g alors de |- g <-> NON @ g (hypothèse (vi)) on déduit
|- NON g <-> @ g et donc |- NON g -> @ g d'où on tire
|- @ g et donc |- g (d'après (**) qui est une conséquence
de l'hypothèse (vii)). Or c'est impossible d'après ce
que nous venons de voir au-dessus.
En résumé S ne peut ni prouver g, ni prouver NON g. La
formule g est indécidable dans S.
Cette première preuve est courte mais possède le défaut
d'utiliser une hypothèse sémantique. La preuve du second
théorème va améliorer très sensiblement
la situation : elle va, sous l'hypothèse de consistance (qui
remplacera l'hypothèse sémantique (vii)) montrer que la
formule exprimant la consistance de S n'est pas prouvable dans S.
Second théorème d'incomplétude de Gödel
La démonstration du second théorème de Gödel
que propose Boolos commence par la série des 11 étapes
suivantes :
1 |- g <-> NON @ g (hypothèse (vi))
2 |- g -> NON @ g (avec 1 et la logique propositionnelle)
3 |- @ g -> @ NON @ g (propriété (*) à partir
de 2)
4 |- @ g -> @ @ g (d'après (iv))
5 |- NON @ g -> (@ g -> faux) (en logique propositionnelle, les
formules du type NON q -> (q -> faux) sont démontrables)
6 |- @ NON @ g -> @ (@ g -> faux) (à partir de 5 et (*))
7 |- @(@ g -> faux) -> (@ @ g -> @ faux) (d'après (iii)
--8 |- @ g -> @ faux (logique propositionnelle à partir de
3, 6, 7 et 4)
9 |- NON @ faux -> g (logique propositionnelle à partir de
8 et 1)
10 |- @ NON @ faux -> @ g (d'après (*) et (9))
11 |- NON @ faux -> NON @ NON @ faux
(logique propositionnelle avec 8 et 10)
Donc si |- NON @ faux alors on a à la fois |- NON @ NON @ faux
d'après 11 et |- @ NON
@ faux par (ii) et donc |- faux. Par contraposition : si NON |- faux
(S est consistant) alors on a NON |- NON @ faux (S ne prouve pas que
S est consistant).
Un système formel consistant vérifiant les hypothèses
(i)-(vi) ne peut pas prouver qu'il est consistant : un système
formel S ne peut être à la fois riche, consistant et prouver
qu'il est consistant.
POUR EN SAVOIR PLUS :
Patrick Cegielski, Quelques contributions à l'étude des
arithmétiques faibles, Thèse de doctorat d'État,
Université de Paris VII, 1990.
J.-P. Delahaye, Arguments et indices dans le débat sur le réalisme
mathématique, in L'Objectivité mathématique, Platonisme
et structures formelles, pp. 23-48, Masson, 1995.
L. Kirby et J. Paris, Accessible Indépendance Results for Peano
Arithmetics, in Bull. London Math. Soc., vol. 14, pp. 285-293, 1982.
R. Smullyan, Les théorèmes d'incomplétude de Gödel,
Masson, 1993.
O. Sudac, Étude de la prouvabilité de certains résultats
classiques dans l'arithmétique primitive récursive et
l'arithmétique de Peano, Thèse de doctorat, 1998.
D. Valleman, Fermat’s Last Theorem and Hilbert Program, in The
Mathematical Intelligencer, vol. 19, n° 1, pp. 64-67, 1997.
N° 265 novembre 1999 Pour la Science (1999)
Pour trouver les liens d'origine http://www.pourlascience.com
STATUT MATHÉMATIQUE DES CONTRADICTIONS
texte intégral
LOGIQUE ET CALCUL
Jean-Paul Delahaye
Comme les physiciens, les mathématiciens proposent des théories
provisoires, infirmées par des contradictions. Celles-ci ne menacent
pas les mathématiques, mais sont sources d'inspiration.
Un étudiant demanda au logicien anglais Bertrand Russell :
«Prétendez-vous que de 2 + 2 = 5, on peut déduire
que vous êtes le pape?» «Certainement, répliqua
le grand logicien... Réfléchissez un peu. Supposons que
2 + 2 = 5. En soustrayant 2 de chaque côté du signe égal,
on obtient que 2 = 3. Par symétrie, on a aussi que 3 = 2 et,
en soustrayant un de chaque côté, 2 =1. Maintenant le pape
et moi nous sommes deux, mais, puisque 2 = 1, le pape et moi ne sommes
qu'un, et donc je suis le pape.»
Cette propriété de la logique classique, appelée
ex-falso quodlibet, énonce que, si une proposition est à
la fois fausse et vraie, alors tout autre énoncé est vrai ;
dans l'exemple, Russell est le pape...
Donc, si vous prouvez que 0 = 1, comme vous savez que 0 <> 1,
vous pouvez en déduire, généralement en raisonnant
par l'absurde, que n'importe quel théorème mathématique
est vrai, et, par exemple, qu'il existe une infinité de nombres
premiers pairs! Une seule contradiction détruirait-elle l'édifice
mathématique, une montagne de merveilles édifiée
par 40 siècles de travail?
Heureusement, les mathématiciens n'envisagent pas sérieusement
qu'une affirmation soit à la fois vraie et fausse : la contradiction
leur est insupportable, et ils font tout pour l'éviter. Ils classent
les énoncés mathématiques en deux catégories,
les vrais et les faux, et tentent de savoir à quelle catégorie
chacun appartient. Ils ne réussissent pas toujours, et certains
problèmes restent ouverts des années, voire des siècles.
De surcroît, certaines questions sont si délicates que
les mathématiciens ne savent pas s'ils pourront jamais trancher :
ces propositions sont indécidables, ni vraies ni fausses.
Dans une théorie possédant une contradiction, pour éviter
que tout ne s'effondre dans le non-sens, il faudrait s'interdire de
raisonner par l'absurde. Impossible, car tout le monde accepte ce principe
de raisonnement, l'instrument de travail quotidien du mathématicien.
Même les mathématiciens intuitionnistes (lesquels, par
peur des contradictions dont l'infini pourrait être responsable,
choisissent d'utiliser une logique moins puissante que la logique classique)
conservent le raisonnement par l'absurde.
Théories contradictoires à jeter
Plusieurs fois dans l'histoire des mathématiques, des contradictions
ont provoqué de graves inquiétudes.
Les Grecs ressentirent la découverte de l'irrationalité
de la diagonale du carré (autrement dit, que la racine carrée
de 2 n'est pas le quotient de deux entiers) comme une contradiction,
car ils pensaient implicitement que toute grandeur pouvait être
exprimée par une fraction. La diagonale du carré existait
géométriquement, mais pas en tant que nombre! Il fallait
définir un autre type de nombre. Cela n'était pas aisé,
et pendant des siècles les mathématiciens se méfièrent
des extensions de la notion de nombres : ils se replièrent
sur la géométrie, et il a fallu plus d'un millénaire
pour qu'ils s'en dégagent.
Au XVIIIe siècle, les premières présentations du
calcul infinitésimal de Newton et de Leibniz permettaient d'obtenir
sans mal une démonstration de 0 = 1 (c'est-à-dire une
contradiction). C'est d'ailleurs pour cela que l'évêque
Berkeley, fondateur de la doctrine idéaliste, refusait de prendre
au sérieux ce nouveau calcul, et disait, non sans humour, que,
lorsqu'on croit au calcul des fluxions (nom donné par Newton
à sa théorie), il n'est pas difficile de croire aux mystères
de la religion. Curieux argument de la part d'un évêque!
Plus tard encore, à la fin du XIXe siècle, la première
version de la théorie des ensembles, formalisée par Frege,
permettait de mener un raisonnement analogue à celui concernant
le barbier qui rase tous les barbiers qui ne se rasent pas eux-mêmes
(se rase-t-il lui-même?). Craignant une contamination de toutes
les mathématiques, le grand Henri Poincaré avait proposé
de renoncer complètement à la très prometteuse
théorie des ensembles.
Plus récemment, certains physiciens utilisaient dans leurs calculs
ce qu'ils appellent la fonction d'Heaviside ; cette fonction n'est
pas conforme avec ce que l'on considère habituellement comme
une fonction. Les calculs auraient amené des contradictions si
on les avait pris au pied de la lettre.
Pourtant jamais, au grand jamais, ces absurdités apparentes n'ont
entraîné de catastrophes majeures : elles ont, au
contraire, été bénéfiques.
Guérisons des théories malades
Circonscrire une contradiction revient souvent à renoncer à
un principe qu'on croyait évident. Dans le cas des irrationnels,
il a fallu renoncer à l'idée que deux grandeurs sont toujours
commensurables. Ce renoncement élimine la contradiction et, bien
loin d'en être irrémédiablement perturbée,
la théorie des nombres s'est nourrie des irrationnels.
Le calcul infinitésimal a été établi sur
des fondements solides, d'abord au XVIIIe et au XIXe siècle par
la mise au point de bonnes règles de calcul et l'introduction
d'une notion rigoureuse de limite, puis plus récemment, au XXe
siècle, grâce à l'analyse non standard qui définit
une manipulation non contradictoire des infiniment petits. Cela a donné
raison à ceux qui avaient eu le génie de prendre quelques
risques et tort à l'évêque Berkeley qui voulait
tout rejeter.
Pour remédier aux contradictions des nouvelles méthodes
d'analyse, les mathématiciens utilisent les quantités
avec lesquelles ils veulent calculer (infinitésimaux, sommes
et produits infinis), mais sans suivre certaines règles de manipulation
de l'algèbre qu'on croyait intangibles et consubstantielles.
Par exemple, selon la façon de placer les parenthèses,
la somme :
1 - 1 + 1 - 1 + 1 - 1 + 1 - 1 + 1 - 1 + ...
vaut 0 ou 1 :
(1 - 1) + (1 - 1) + (1 - 1) + (1 - 1) + ... = 0 + 0 + 0 + ... = 0
1 + (-1 + 1) + (-1 + 1) + (-1 + 1) + ... = 1 + 0 + 0 + 0 ... = 1
Pour éviter cette contradiction, il faut d'abord admettre que
toute somme infinie ne désigne pas un nombre : ici, la somme
infinie n'a pas de sens. Les manipulations effectuées ne signifient
rien, et la contradiction obtenue n'a pas à être acceptée.
Même lorsque les sommes infinies ont un sens, les opérations
qu'on faisait sur les sommes finies ne sont plus nécessairement
autorisées. C'est ce que montre la somme infinie suivante :
s = 1 - 1/2 + 1/3 - 1/4 + 1/5 - 1/6 + 1/7 - 1/8 + 1/9 - 1/10 + 1/11
...
En changeant l'ordre des termes et en les regroupant, on obtient :
s = (1 - 1/2) - 1/4 + (1/3 - 1/6) - 1/8 + (1/5 - 1/10) - 1/12 + ...
= 1/2 - 1/4 + 1/6 - 1/8 + 1/10 - 1/12 + ... = 1/2 (1 - 1/2 + 1/3 - 1/4
+ 1/5 - 1/6 + 1/7 + 1/8 - ...) = 1/2 s
Alors s = 1/2 s, donc s = 0, ce qui contredit le fait qu'en regroupant
les termes deux par deux, dans l'ordre, la somme (1 - 1/2) + (1/3 -
1/4) + ... est une somme de nombres strictement positifs, donc strictement
positive. La somme infinie s, si l'on accepte d'en permuter les termes
et de les regrouper, est à la fois nulle et strictement positive!
Pour éviter cette contradiction, il faut renoncer à changer
l'ordre des termes des séries infinies, même si elles sont
convergentes. Quelques précautions de ce genre et l'élaboration
du concept de limite éliminent toutes les contradictions des
méthodes de calcul introduites par Newton et par Leibniz.
La théorie des ensembles a su se prémunir des antinomies
(noms donnés alors aux contradictions qu'on y a trouvées)
et elle constitue aujourd'hui un socle pour toutes les mathématiques,
dont elle a unifié et simplifié la présentation.
Dans son cas, plusieurs remèdes différents ont été
proposés. L'axiomatisation de Zermelo-Fraenkel est la plus souvent
adoptée : elle se fonde sur l'idée que n'importe
quel regroupement d'objets ne doit pas être considéré
comme un ensemble et qu'en particulier les regroupements trop gros (comme
celui de tous les ensembles) sont à éviter. Même
si la solution retenue aujourd'hui apparaît ad hoc à certains
logiciens, elle fonctionne parfaitement, et, depuis plus de 70 ans,
aucune nouvelle antinomie n'a été découverte.
Le calcul des distributions, inventé par Laurent Schwartz dans
les années 1950, a justifié a posteriori les fantaisies
des physiciens. Il se fonde sur une généralisation de
la notion de fonction continue, qu'on appelle distribution ; dans
un cadre nettoyé de toute contradiction, ce qui est devenu la
«distribution d'Heaviside» a pu s'épanouir. Dans
cette théorie, même les distributions correspondant à
des fonctions non continues sont dérivables (et on peut même
y dériver les fonctions 1,5 fois ou pi fois!).
Notons que d'autres méthodes de calcul utilisées en physique
(par exemple les techniques dites de renormalisation qui consistent
à faire des manipulations étranges avec des quantités
infinies) n'ont pas aujourd'hui de justifications mathématiques
totalement satisfaisantes (autrement dit, sont contradictoires dans
les cadres actuels où l'on pourrait les faire tenir) et attendent
leur sauveur.
Confrontés à une contradiction, les mathématiciens
réussissent toujours à l'éliminer, et une contradiction
n'a jamais durablement mis en danger les mathématiques. Mieux,
en stimulant la recherche, toute contradiction amène un enrichissement.
La situation en mathématiques serait donc semblable à
celle de la physique, où toute expérience venant contredire
les théories admises stimule les imaginations et amène
une reformulation complète des vieilles théories et une
avancée générale.
Aussi, bien qu'il ne soit jamais envisageable de laisser sans traitement
une contradiction, sa découverte devrait nous réjouir,
car c'est l'indice que nous allons devoir la maîtriser et que
cela nous enrichira. Nicolas Bourbaki a exprimé cette placidité
du mathématicien : «Nous croyons que la mathématique
est destinée à survivre et qu'on ne verra jamais les parties
essentielles de ce majestueux édifice s'écrouler du fait
d'une contradiction soudain manifestée. [...] Voilà 25
siècles que les mathématiciens ont l'habitude de corriger
leurs erreurs et d'en voir leur science enrichie, non appauvrie ;
cela leur donne le droit d'envisager l'avenir avec sérénité.»
Hélas, il n'existe pas de méthode toute prête permettant
d'éliminer à coup sûr les contradictions. Interdire
juste le raisonnement qui conduit à la contradiction n'est pas
possible : dans une théorie, lorsqu'un raisonnement permet
de trouver une contradiction, il y en a de nombreux autres. Les réparations
à faire demandent à chaque fois de l'imagination, voire
de la subtilité ou même du génie. On peut donc légitimement
ne pas partager l'optimisme de Bourbaki : ce n'est pas parce qu'on
a échappé dix fois à la mort qu'on y échappera
toujours.
Rassurer les inquiets
Est-on sûr donc qu'on saura se débarrasser de toute contradiction
dans l'avenir? Est-on seulement certain que les théories résultant
des réparations antérieures sont exemptes de contradictions?
Il s'en faut. Le logicien Edward Nelson pense que, parmi d'autres théories,
l'arithmétique - la théorie permettant de traiter des
nombres entiers et de leurs propriétés - est contradictoire.
Ce serait vraiment très ennuyeux, car l'arithmétique est
le noyau central des mathématiques et il ne resterait plus rien
d'intéressant en mathématiques sans l'arithmétique.
Comment rassurer les inquiets ? Pour régler l'affaire, ne peut-on
pas prouver (évidemment par des moyens élémentaires)
que les méthodes de raisonnement que nous utilisons ne conduiront
jamais à des contradictions? Et si l'on ne réussit pas
à traiter d'un coup toutes les mathématiques, ne peut-on
pas au moins fournir des garanties pour certaines théories? Comme
celles-ci s'organisent en un schéma hiérarchique où,
progressivement, on s'élève des théories les moins
puissantes (l'arithmétique) à d'autres plus puissantes
(comme l'analyse), jusqu'à la théorie des ensembles, ne
peut-on pas au moins garantir les premiers échelons de la hiérarchie?
C'est l'idée du programme proposé par le grand mathématicien
allemand David Hilbert dans les années 1920. Ce programme, comme
le notait récemment le mathématicien Daniel Vellman, est
toujours d'actualité : la démonstration du théorème
de Fermat, proposée il y a trois ans par Andrew Wiles, bien que
ne concernant que les entiers, utilise la théorie des ensembles,
c'est-à-dire une théorie bien plus risquée que
la simple arithmétique. La démonstration de A. Wiles ne
signifie vraiment qu'on ne trouvera jamais de x > 0, y> 0, z >
0 et a > 2 tels que xa + ya = za (ce qui est une affirmation très
concrète) que si la théorie des ensembles est non contradictoire,
ce que proposait entre autres choses d'établir le programme de
Hilbert. Cette actualité renouvelée du programme de Hilbert
nous remémore les deux résultats importants auxquels il
a conduit.
Le premier est la preuve par Kurt Gödel en 1931 que, dès
qu'un domaine mathématique est assez large (précisément
dès qu'il inclut l'arithmétique), alors la démonstration
de sa non-contradiction ne peut se faire qu'à l'aide de systèmes
plus puissants que lui. C'est ce qu'on appelle le second théorème
d'incomplétude, et il signifie qu'aucune démonstration
vraiment satisfaisante de non-contradiction ne sera donc jamais donnée.
L'autre résultat - plus positif - du programme de Hilbert est
le développement d'un domaine de la logique mathématique,
appelée théorie de la preuve, où l'on établit
des énoncés de non-contradiction relative, c'est-à-dire
du genre : «Si la théorie X est non contradictoire,
alors la théorie Y l'est aussi.» Un exemple de 1938 concerne
l'axiome du choix (qui dit qu'associé à tout ensemble
X d'ensembles non vides, il y a au moins un nouvel ensemble F comportant
un élément exactement de chaque ensemble de X) :
si la théorie des ensembles sans l'axiome du choix est non contradictoire,
alors la théorie avec l'axiome du choix est aussi non contradictoire.
Bien d'autres énoncés de non-contradiction relative ont
été donnés, en particulier que, si la théorie
des ensembles est non contradictoire, alors l'analyse aussi, de même
que la géométrie et l'arithmétique. Ainsi, dans
la hiérarchie des théories, plus on s'élève,
plus on prend le risque d'obtenir des contradictions. La confiance en
l'arithmétique est quasi absolue (sauf peut-être pour E.
Nelson). À l'autre extrême, la théorie des ensembles
est nettement moins sûre. Insistons là-dessus : même
si l'on pense que le risque de contradiction dans la théorie
des ensembles est sérieux, cela ne signifie pas qu'on doit l'abandonner :
si une contradiction se manifeste, on saura sans doute la contourner.
L'incertain et les arguments de Lucas
Acceptons l'idée que les mathématiciens vivent dans l'incertain
et le provisoire. Plusieurs fois dans le passé, des théories
qui semblaient assurées se sont révélées
contradictoires. Peut-être aurons-nous à ajuster nos théories
et à les réparer, mais tel est le cours normal des choses.
Cette incertitude sans gravité ne semble pas avoir été
comprise par ceux qui utilisent les théorèmes d'incomplétude
de Gödel pour démontrer que l'esprit humain est supérieur
à celui de toute machine possible et donc que les recherches
en intelligence artificielle sont d'avance condamnées à
l'échec. Le raisonnement qu'ils avancent avait été
proposé, il y a déjà plus de 30 ans, par le philosophe
américain J. Lucas. Il est périodiquement remis à
la mode, notamment et à deux reprises (perseverare diabolicum),
par Roger Penrose.
«Une machine, disent nos philosophes, peut être identifiée
à une théorie mathématique, car, comme elle, elle
est définie par un nombre fini de règles mécaniques
fixées une fois pour toutes. D'après le second théorème
d'incomplétude de Gödel, une machine ne peut pas savoir
d'elle-même qu'elle est non contradictoire.» Jusque-là,
ça va. «Nous, à l'inverse, grâce à
la compréhension que nous avons de ce que représentent
les symboles de nos théories, grâce à notre intuition
des objets mathématiques, et parce que nous pouvons nous élever
dans la hiérarchie des théories, nous réussissons
à savoir avec certitude que certaines théories ne sont
pas contradictoires, et que nous ne nous contredisons pas. Nous ne sommes
pas équivalents à des machines et aucune ne nous égalera
jamais.»
Cet argumentaire oublie simplement que nous avons parfois de mauvaises
intuitions. Même si Frege associait des réalités
aux symboles de la théorie des ensembles qu'il proposait et donc
était certain de sa non-contradiction (au point d'écrire
un livre pour la présenter), il se trompait, et sa théorie
était contradictoire. Bien souvent, des théories ont été
proposées par des gens certains de la cohérence de leurs
idées et pourtant se sont écroulées et ont dû
être réparées. Pour les théories les plus
élevées de la hiérarchie mathématique, on
n'a vraiment aucune raison sérieuse (autre que leur utilisation
pendant une plus ou moins longue période) de croire qu'elles
sont non contradictoires. Quant à jurer, quand il s'agit de nous-mêmes,
que nous ne nous contredirons jamais, c'est renoncer à toute
discussion de problèmes politiques et sociaux entre amis!
L'histoire des mathématiques et les théorèmes de
Gödel montrent que nous ne pourrons jamais être certains
de la non-contradiction des théories que nous utilisons. Que
nous soyons des machines ou pas ne change rien : les théories
mathématiques comme les théories physiques ne proposent
pas des certitudes, mais sont des instruments qui fonctionnent plus
ou moins bien, plus ou moins longtemps et qu'il faut ajuster ou changer
de temps en temps. Peut-être réussira-t-on un jour à
démontrer que nous ne sommes pas des machines, mais cela ne se
fera pas par l'invocation des théorèmes d'incomplétude
de Gödel!
Vivre avec les contradictions
C'est sans doute à cause de l'improuvabilité de la non-contradiction
que des tentatives ont été menées récemment
pour l'accepter franchement. L'idée est de modifier la logique
classique pour éviter la contagion généralisée
des contradictions, autrement dit empêcher l'effet du ex-falso
quodlibet. Après tout, lorsque nous nous contredisons, nous ne
nous mettons pas à délirer aussitôt à propos
de tout : nous savons circonscrire les effets d'une contradiction.
Plusieurs voies semblent ouvertes et ont conduit à ce qu'on appelle
les logiques paraconsistantes, où l'on décrit des règles
de raisonnement n'incluant pas le ex-falso quodlibet et qui bien sûr
ne permettent pas de le retrouver. Ces systèmes qui sont assez
complexes provoquent souvent une gêne à cause de leurs
propriétés non classiques. Par exemple, le système
défendu par Graham Priest propose d'accepter sérieusement
que des énoncés soient à la fois vrais et faux.
Ces recherches ont cependant un double intérêt. D'une part,
elles conduisent à développer des programmes d'ordinateurs
simulant les raisonnements humains et résistant à l'apparition
de contradictions. D'autre part, elles suggèrent de reconsidérer
le programme de Hilbert en le modifiant un peu. De manière à
ne pas avoir à craindre un effondrement général
des mathématiques, nous devrions utiliser une logique paraconsistante
et nous assurer que notre nouvelle présentation (i) préserve
toutes les mathématiques intéressantes (tous les résultats
vrais des mathématiques doivent l'être encore, car on ne
veut évidemment pas perdre le travail des siècles précédents),
(ii) est non triviale, c'est-à-dire que tout n'y est pas simultanément
vrai et faux, et (iii) laisse la place à une preuve, par des
raisonnements élémentaires, des deux propriétés
précédentes.
On aurait alors, comme Hilbert l'espérait, une garantie que tout
ne sera pas à jeter suite à une découverte malencontreuse
de contradiction, et donc l'assurance d'un progrès continu et
sans retour en arrière des mathématiques. Un tel programme
de Hilbert modifié peut-il aboutir? Les avis divergent aujourd'hui,
mais les grandes idées, comme celles de Newton, Leibniz, Frege
ou Hilbert, à défaut de fonctionner du premier coup, s'imposent
à la longue.<
Jean-Paul Delahaye est directeur adjoint du Laboratoire d'informatique
fondamentale de Lille du CNRS.
Bibliographie :
Sur la controverse de Berkeley à propos du calcul infinitésimal :
P. Davis et R. Hersch, L'univers mathématique, Gauthier-Villars,
Paris, 1982.
J.-L. Gardies, Le raisonnement par l'absurde, Bibliothèque d'histoire
des sciences, PUF, Paris, 1991.
R. Penrose, Les ombres de l'esprit. À la recherche d'une science
de la conscience, InterÉditions, 1995.
G. Priest, In Contradiction : A Study of the Transconsistent, Martinus
Nijhoff Publishers, Kluwer Academic Publisher Group, Dordrecht, 1987,
(Les logiques paraconsistantes et leur importance philosophique).
D. Vellmann, Fermat's Last Theorem and Hilbert's Program, in The Mathematical
Intelligencer, 19, 1, pp. 64-67, 1997.
P. Besnard et T. Shaub, Circumscribing Inconsistency, IJCAI (Internationnal
Joint Conference Artificial Intelligence), 1997.
N° 241 novembre 1997 Pour la Science (1997)
Les liens d'origine http://www.pourlascience.com
Les propositions indécidables
Le résultat le plus célèbre de Gödel concerne
des propositions sur les nombres naturels, vraies mais indémontrables
dans l'arithmétique. La phrase réflexive suivante est
un exemple simple de propositions vraies, mais indécidables,
c'est-à-dire ni démontrables ni réfutables :
«Cette proposition est indémontrable.»
Elle peut être transformée en un nombre selon une méthode
mise au point par Gödel. Ensuite, on montre d'une part que si cette
proposition est démontrable, sa négation l'est aussi :
elle est donc indémontrable.
D'autre part, on prouve qu'elle est néanmoins vraie.
Les équations polynomiales conduisent à des propositions
un peu plus compliquées.
Par exemple, l'affirmation que certaines équations polynomiales
n'ont pas de racines (c'est-à-dire de solutions) entières
est indécidable.
Gödel a démontré que les axiomes qui définissent
les nombres entiers naturels sont incomplets : certaines propositions
vraies de la théorie des nombres sont indémontrables à
l'aide de ces axiomes.
Sa démonstration montre, par conséquent, qu'il existe
des entités, nommées entiers non standards, différentes
des nombres naturels qui obéissent néanmoins à
ces axiomes. Comme tout ce qui est démontré à partir
des axiomes (en rouge) s'applique à toutes les entités
qui obéissent aux axiomes, certaines propositions vraies concernant
les nombres naturels (en bleu, en vert et en rouge) sont nécessairement
indémontrables (en bleu et en vert).
N° 262 août 1999 Pour la Science (1999)
Pour trouver les liens d'origine http://www.pourlascience.com
LES VÉRITÉS MATHÉMATIQUES
bibliographie
LOGIQUE ET CALCUL
Jean-Paul Delahaye
Certains résultats mathématiques sont vrais, mais ne peuvent
être prouvés ; des êtres mathématiques
existent mais sont introuvables, non constructibles ou non calculables.
Quelle faune!
Jean-Paul Delahaye est directeur adjoint du Laboratoire d’informatique
fondamentale de Lille du CNRS.
Bibliographie complète :
M. J. Beeson. Foundations of Constructive Mathematics Metamathematical
Studies. Springer-Verlag. Berlin / Heidelberg / New-York. 1985. (Excellent
traité sur les mathématiques constructives.)
E. Bishop. Foundations of Constructive Analysis. McGrawHill, New-York.
1967.
E. Bishop, D. Bridges. Constructive Analysis. Springer-Verlag. 1985.
L. E. J. Brouwer. Collected Works. A. Heyting ed. Amsterdam. 1975.
J.-P. Delahaye. Information, complexité et hasard, Edition Hermès,
1995. (Voir le chapitre 8 sur l'importance en mathématiques des
indécidables de Gödel.)
M. Dummett. Elements of Intuitionism. Clarendon Press. 1977.
T. J. Jech. About the Axiom of Choice. In "Handbook of Mathematical
Logic" J. Barwise editor. Studies In Logic n°80. North-Holland
Publishing Company, Amsterdam, 1977. pp. 345-370.
Y. Gurevich. Platonism, Constructivism, and Computer Proofs vs Proofs
by Hand. Bulletin of the European Association for Theoretical Computer
Science, n°57, oct. 1995, pp.145-166. (Un point de vue récent
sur la constructivité en mathématiques.)
Y. Matiiassevitch. Le dixième problème de Hilbert et son
indécidabilité. Masson, Paris, 1995.
J. Milnor. A Nobel Prize for John Nash. Mathematical Intelligencer,
Vol n° 17, n° 3, 1995, pp. 11-17
G. H. Moore. Zermelo's Axiom of Choice. Its Origins, Development and
Influence. Springer-Verlag, New-York. 1982.
Parigot M. Preuves de Programmes: Les Mathématiques comme Langage
de Programmation. Le Courrier du CNRS, supplément au numéro
69: Images des Mathématiques. 1988. pp. 40-47.
R. Smullyan. Les théorèmes d'incomplétude de Gödel.
Masson, Paris, 1993. (La meilleure présentation des théorèmes
de Gödel leur démonstration détaillée.)
A. S. Troelstra, D. van Dalen. Constructivism in Mathematics : an introduction.
North-Holland, Amsterdam. 1988. <
N° 237 juillet 1997 Pour la Science (1997)
Les liens d'origine http://www.pourlascience.com
|