Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Information, complexité et hasard Jean-Paul Delahaye Laboratoire d'Informatique

Information, complexité et hasard Jean-Paul Delahaye Laboratoire d'Informatique Fondamentale de Lille URA CNRS 369 HERMES 159 Chapitre 6 L'importance des indécidables Résumé Les indécidables dont les théorèmes de Gödel de 1931 démontrent l'existence et qu'ils exhibent, ont-ils une signification réelle, ou au contraire, sont-ils des énoncés pathologiques sans intérêt autre que technique!? Cette question posée depuis longtemps (et qui peut être entendue de plusieurs façons différentes) semble recevoir des réponses contradictoires, chacune des deux thèses pouvant trouver dans les résultats de logique mathématique récents des arguments en sa faveur (ceux en faveur de l'insignifiance sont assez élaborés mais d'autant plus intéressants). Des indécidables de la théorie de la calculabilité qui semblent concerner toutes les parties des mathématiques et qu'on découvre par dizaines, aux indécidables de Paris-Harrington et Friedman, en passant par les indécidables de l'arithmétique pure et par les indécidables de la théorie des ensembles, nous parcourons rapidement une classification des indécidables de Gödel, en nous posant à chaque fois la question de leur signification mathématique et physique. Malgré de nombreux résultats nouveaux, rien ne semble définitivement tranché. On peut considérer évident qu'ils sont partout, et qu'on en trouve facilement qui ont du sens. De même on peut, comme Feferman, à côté des mathématiques abstraites essayer de délimiter le domaine des "mathématiques ordinaires applicables", qui pourrait être indifférent —!d'une certaine façon!— aux indécidables de Gödel. 160 INFORMATION, COMPLEXITÉ ET HASARD 6.1. Introduction 95% des mathématiciens se moquent éperdument de ce que peuvent faire tous les logiciens et tous les philosophes. Dieudonné 1982 Le sentiment général est que le théorème de Gödel ne concerne que les logiciens. Solovay cité par Kolata (Kolata 1985) La proposition indécidable A décrite par Gödel paraît très artificielle, sans lien avec aucune autre partie de la théorie des nombres actuelle!; sa principale utilité était d'établir l'impossibilité d'une preuve de la non-contradiction de l'arithmétique. Parmi les nombreuses questions classiques non résolues de la théorie des nombres, on n'a pas encore à ma connaissance établi que l'une d'elles est indécidable. Dieudonné 1987 Ce que l'on souhaiterait, c'est qu'un grand problème irrésolu des mathématiques comme le théorème de Fermat soit démontré indécidable. Cela serait vraiment remarquable. Joël Spencer cité par Kolata (Kolata 1985) La croyance que la théorie de la démonstration de Hilbert fait partie intégrante de la mathématique (...) ne nous paraît pas justifiée, et nous considérons que l'intervention de la métamathématique dans l'exposé de la logique peut et doit être réduite à la partie élémentaire qui traite du maniement des symboles abréviateurs et des critères déductifs. Bourbaki 1969 6.1.1. Importance philosophique et importance mathématique Les indécidables dont les théorèmes de Gödel de 1931 démontrent l'existence et qu'ils exhibent, ont-ils une signification réelle, ou au contraire sont-ils des énoncés pathologiques sans intérêt autre que technique!? C'est cette question que nous voulons nous poser. L'intérêt logique ou philosophique des indécidables est lié à leur intérêt mathématique et c'est donc à cet aspect particulier que nous allons principalement nous intéresser. Il se trouve en effet que bien des mathématiciens considèrent les indécidables avec prudence et les jugent comme de simples curiosités ne les concernant pas vraiment. N. Bourbaki par exemple ne les mentionne que dans ses notes historiques. Tenter de comprendre ce que peut vouloir dire!: "les indécidables sont sans véritable importance pour les mathématiques" est un défi. Il semble en effet évident que ce qui est important pour la philosophie des mathématiques —!et l'impossibilité aujourd'hui d'aborder la philosophie des mathématiques sans traiter des indécidables de Gödel est admise par tout le monde!— l'est aussi pour les mathématiques elles- mêmes!: que veulent donc dire ceux qui refusent de prêter attention aux indécidables!? L'IMPORTANCE DES INDÉCIDABLES 161 Notre méthode sera de parcourir les différentes classes d'indécidables découvertes par les logiciens depuis 1931. A propos de chacune de ces classes, nous imaginerons un dialogue contradictoire sur l'importance des indécidables. Nous envisagerons par endroits le problème de la physique. Notre conclusion sera que si soutenir l'insignifiance mathématique des indécidables est encore possible, cela se fait toujours au prix d'un réductionnisme qui possède plusieurs formes dont les deux extrêmes sont le formalisme et le finitisme. Certaines variantes du réductionnisme comme le prédicativisme de Feferman, se nourrissant des récents résultats de la théorie de la preuve, refusent de dire leur dernier mot et prétendent même faire revivre le programme de Hilbert qu'on pensait enterré justement par les théorèmes d'indécidabilité de 1931. Nous verrons finalement que cette question de l'importance mathématique des indécidables de Gödel concentre en elle tout le problème de la philosophie des mathématiques, en un mot que l'importance mathématique des indécidables de Gödel est un problème important ... philosophiquement!! 6.1.2. Comment définir un indécidable de Gödel Nous commençons par proposer une définition des "indécidables de Gödel". La définition que nous donnons n'est pas mathématique, elle a simplement pour objet de préciser un usage établi qui refuse que n'importe quel énoncé indépendant de n'importe quel système formel puisse être considéré comme un "indécidable de Gödel". Plus loin nous serons d'ailleurs amenés à préciser que parmi les indécidables de Gödel il faut encore distinguer ceux qui renforcent réellement les systèmes auxquels on les ajoute (comme les énoncés de consistance) de ceux qui sont conservatifs (comme l'axiome du choix en théorie des ensembles, ou le lemme de König). Un indécidable de Gödel c'est!: un énoncé mathématique vrai et non démontrable. Plus précisément!: un indécidable de Gödel c'est un énoncé mathématique E tel que!: (1) E n'est pas démontrable dans un système formel S1 qui permet de l'exprimer!; (2) on peut montrer (dans un système formel S2) la non-prouvabilité de E!; (3) on peut montrer (dans un système formel S3) que E est vrai!; (4) le système S1 est une axiomatisation raisonnable d'un champ mathématique donné et reconnu comme intéressant, et on a pu penser que cette axiomatisation formalisait bien le champ en question, (comme l'arithmétique de Peano du premier ordre vis-à-vis de l'arithmétique). Cette condition est réalisée si on a cru à un moment donné que S1 est une axiomatisation complète du champ en 162 INFORMATION, COMPLEXITÉ ET HASARD question. Cette condition est aussi satisfaite si certains soutiennent que tous les énoncés intéressants (dans un sens à préciser) du champ en question sont prouvables avec S1. Beaucoup de mathématiciens pensent que ZF + AC par exemple permet d'exprimer et de démontrer tout énoncé mathématique vraiment intéressant. La condition (4) sert à éviter qu'on appelle "indécidable de Gödel" n'importe quel axiome indépendant d'un système S1 clairement trop faible!: l'axiome des parallèles par exemple n'est pas considéré comme un indécidable de Gödel, de même l'axiome de l'infini n'est pas un indécidable de ZF-{axiome de l'infini}!; (5) le système S2 est un système dont on a certaines raisons de penser qu'il est consistant (par exemple ZF + AC)!; (6) le système S3 est un système raisonnable dont on a aussi certaines raisons de penser qu'il est consistant. Dans le cas de certains axiomes des grands cardinaux en théorie des ensembles, les raisons de croire à la consistance de S3 sont assez ténues (car S3 est obtenu en ajoutant un axiome de grand cardinal à ZF + AC), il y a même des cas où la consistance de S3 est douteuse. 6.2. Classification des indécidables de Gödel Dans ce paragraphe nous présentons une classification des indécidables de Gödel et pour chaque type d'indécidables, nous imaginons un petit dialogue entre Monsieur Insignifiance qui ne trouve aucun intérêt mathématique réel à ces indécidables, et Monsieur Importance qui lui leur trouve un sens et défend l'idée qu'ils sont d'authentiques résultats mathématiques. Les dialogues sont quelque peu naïfs, sauf à propos des derniers éléments de la classification où ils prennent un tour un peu plus technique. 6.2.1. Les indécidables du premier théorème d'incomplétude Ils ont un sens simple, moyennant des considérations métamathématiques sur la prouvabilité. Ils signifient en effet!: je ne suis pas démontrable dans S1 Le système formel S1 peut être n'importe quelle extension (primitive récursive) du système Q de Robinson qui est un système plus faible que PA (l'arithmétique du premier ordre de Peano) et même que PRA (l'arithmétique primitive récursive). Voir par exemple (Boolos Jeffrey 1980) pour des définitions précises. La restriction aux extensions primitives récursives n'est pas une véritable restriction. Ils sont démontrés exister, mais mieux que cela, ils sont produits effectivement!: si S1 est donné, la démonstration de Gödel permet d'expliciter un indécidable de S1. L'IMPORTANCE DES INDÉCIDABLES 163 Pour S2 on peut prendre S1+consistance(S1). Dans la démonstration originale de Gödel S3 est plus fort que S1+consistance(S1) puisque Gödel utilisait l' - consistance de S1 (l'impossibilité dans S3 de démontrer n P(n) en même temps que nonP(0) nonP(1) etc.). C'est Rosser 1936 qui, en modifiant l'énoncé de Gödel (qui n'a alors plus un sens simple), a permis de prendre S2=S3= S1+consistance(S1). Les formulations (données par Kleene) du premier théorème de Gödel utilisant les concepts de la théorie de la récursivité sont très intéressantes, elles s'appliquent à tout système formel, et éclairent le phénomène de l'indécidabilité!qu'on peut résumer en disant!: •!l'ensemble des vérités de l'arithmétique du premier ordre n'est pas uploads/Philosophie/ delahaye-information-compl-1999-ch-6.pdf