À compter de la Renaissance, en passant par le Siècle des lumières et la révolution française, et jusqu’au début du vingtième siècle (approximativement), la Science est devenue la principale croyance, voire religion déguisée, de l’humanité. Nous profitons encore, anciens élèves d’écoles d’ingénieurs, d’universités…des retombées de ce formidable mouvement. Cependant, depuis une cinquantaine d’années, la Science tend à perdre la place dominante qu’elle occupait, au profit de l’économie et du << management >>.
Il n’est guère besoin de longs discours pour établir le phénomène, les faits parlent d’eux-mêmes. Dans la littérature populaire, le personnage central souvent campé par le savant au dix-neuvième siècle1, est de plus en plus occupé par un (ou même souvent une, là aussi signe des temps) jeune << raider >>, aventurier de Wall-Street et du billet vert.
Au niveau philosophique, la Mathématique fut longtemps considérée comme une référence absolue de justesse, une quasi-manifestation de l’esprit divin2.
Il y a une centaine, voire une cinquantaine d’années, les physiciens étaient des personnages publiquement connus (Maxwell, Edison, Einstein, Bohr, et bien d’autres furent célèbres de leur temps). Aujourd’hui, les gens célèbres sont les grands financiers qu’il soient triomphants ou déchus (tout le monde connaît Bernard Tapie, voire Bernard Arnault) mais quel homme de la rue serait capable de citer le nom d’un grand savant contemporain ?
Enfin, nombre de postes de direction de grandes entreprises ou de grands services, confiés traditionnellement à des gens de culture scientifique, vont de plus en plus vers des spécialistes de << management >>, de gestion et d’économie3. Les anciens élèves de l’École Polytechnique entendent d’ailleurs depuis quelques années des exhortations à se lancer dans la << guerre économique >> (sic), montrant en cela un certain changement de cap de la dite institution, quoiqu’on en dise.
Les raisons de ce changement sont multiples ; certaines sont structurelles et tiennent à l’évolution profonde de la société plus orientée aujourd’hui vers le paraître et le posséder que vers l’être et le faire4.
Mais il y a des raisons liées à l’évolution de la science elle-même ; tout d’abord la science est devenue extrêmement complexe, spécialisée et difficile à vulgariser. Il est plus facile d’impressionner quelqu’un en réalisant la première transmission par voie Hertzienne qu’en montrant le résultat d’une expérience en chambre à bulles prouvant l’existence d’une nouvelle particule élémentaire. Les chercheurs ne travaillent plus individuellement mais en équipe et les théories scientifiques modernes sont très spécialisées, incompréhensibles pour le grand public : il était possible de donner une image intuitive de la relativité, mais essayez donc d’expliquer la théorie des super-cordes à un auditoire novice5.
Enfin, la dernière raison qui nous intéresse au premier chef : la crise interne qu’ont traversée et traversent encore les deux sciences majeures des siècles derniers : la Mathématique et la Physique.
Nous ne dirons qu’un mot des problèmes de la physique contemporaine. Les gens intéressés pourront se référer pour plus de précisions à [d’Espagnat1989] ou [Pomian1990]. Grossièrement, on peut dire que les difficultés de la physique sont liées à la remise en cause d’un principe sacré de la Science : celui du déterminisme Un certain nombre d’expériences tendrait à prouver qu’il faut renoncer à ce principe ou au dogme voulant qu’il n’y ait pas d’interférences pouvant se déplacer plus vite que la lumière. Le débat fait encore rage en ce moment. Mais avant même que ces problèmes se posent, les premiers résultats << paradoxaux >> de la mécanique quantique (impossibilité de connaître précisément à la fois la position et la vitesse d’une particule, caractère dualiste (ondulatoire et corpusculaire) de la notion de particule, …) avaient fortement secoué la communauté scientifique6, séisme qui s’était propagé jusque dans la communauté sociale en général.
Les problèmes qu’affrontent les mathématiques ne sont pas moins intéressants et ce chapitre va permettre, je l’espère, de mieux les comprendre.
Nous allons nous attacher à montrer dans la suite de ce paragraphe l’ampleur de la crise des mathématiques au XXe siècle. Il n’existe sans doute pas de meilleures phrases pour décrire cette crise que celles de Morris Kline dans son introduction [Kline1989] :
<< Il y a des tragédies provoquées par la guerre, la famine et la peste. Mais il existe aussi des tragédies intellectuelles provoquées par les limites de l’esprit humain. Ce livre est en quelque sorte le récit des calamités qui ont mis bas la plus efficace et incomparable réalisation de l’homme, en son effort permanent et approfondi de la raison humaine : les mathématiques. >>
Jusqu’au dix-neuvième siècle, les mathématiciens connurent fort peu de problèmes métaphysiques. Certes, on se posait des questions sur l’équivalence des différentes branches des mathématiques et René Descartes démontra très tôt l’équivalence entre la géométrie traditionnelle et la théorie analytique. Mais on ne doutait en aucun cas de la validité des axiomes de la géométrie euclidienne7, pierre d’angle des mathématiques de l’époque. Le premier sérieux coup à cette confiance fut donné par Bolyai, Lobachevsky et Riemman qui démontrèrent l’indépendance du troisième axiome d’Euclide (par un point on ne peut faire passer qu’une parallèle à une droite), et le remplacèrent soit par un axiome prétendant qu’on pouvait faire passer par ce point une infinité de droites, soit par un axiome prétendant qu’on ne pouvait en faire passer aucune8.
À partir de ce moment, commencèrent à se faire jour les notions d’axiomatique matérielle et d’axiomatique formelle, et les risques que font courir la confusion de ces deux notions ; la géométrie euclidienne classique était une théorie axiomatique matérielle : chaque axiome avait une signification intuitive immédiate, et les termes employés avaient une réalité physique << obligatoire >> dans l’esprit de chacun : une droite géométrique était une droite << physique >>. Bolyai, Lobachevsky et Riemman en firent (probablement sans le savoir) un système d’axiomatique formelle : ils reprirent les axiomes, supprimèrent les notions intuitives placées implicitement derrière les mots et purent ainsi modifier un axiome. La notion de droite et de point dans leurs systèmes n’avaient plus la signification intuitive primitive et représentaient des objets formels sur lesquels on opérait mentalement. Certes, il existe des modèles (la géométrie sphérique pour Riemman, ou la géométrie des surfaces à courbure négative pour Bolyai-Lobachevsky), où ces systèmes formels reprennent une interprétation intuitive. Mais ce ne sont alors que des modèles d’application de la théorie formelle.
Ces résultats sonnaient les premiers le glas de la géométrie traditionnelle, qui perdait tout fondement << métaphysique >>, et aussi des mathématiques traditionnelles. Les systèmes formels étaient en route et avec eux, ce que l’on a coutume d’appeler aujourd’hui les mathématiques modernes.
L’infini commença à poser des problèmes aux mathématiciens très tôt. Leibnitz, lors de ses travaux sur le calcul différentiel, rencontra cet objet bizarre. Les sentiments de la communauté mathématique furent plutôt circonspects voire défavorables. On cite souvent la phrase de Gauss (1831) : << Je m’élève contre l’emploi de grandeurs infinies conçues comme des réalités achevées car cela n’est jamais permis en mathématique >>. Cette phrase visait la notion de grandeur infinie (le + ∞ que nous employons aujourd’hui), mais un autre problème de l’infini se posait aussi, celui des ensembles infinis.
En 1638, Galilée remarquait le << paradoxe >> suivant : il est possible de mettre en correspondance chaque élément de l’ensemble des entiers naturels avec un et un seul élément de l’ensemble des carrés d’entiers naturels9. Or la méthode de comptage par correspondance un à un est sans doute la méthode la plus intuitive qui soit. Deux enfants qui ne savent pas compter, peuvent déterminer quel est celui d’entre eux qui a le plus de billes : il suffit qu’ils en posent chacun simultanément une jusqu’à ce qu’il n’y ait plus qu’un seul enfant à avoir des billes dans la main. Le résultat de Galilée prouvait-il donc qu’il y a << autant >> de carrés qu’il y a d’entiers ? Et que signifiait dans ce contexte le mot autant, car intuitivement il semble bien qu’il y ait plus d’entiers que de carrés parfaits.
Il faudra attendre le dix-neuvième siècle et le mathématicien Georg Cantor pour << formaliser >> les notions d’ensemble et d’infini. Cantor imposa comme définition de autant : << peut être mis en correspondance un à un avec >> (dans la terminologie moderne, nous dirions qu’il existe une bijection entre les deux ensembles, ou que les deux ensembles sont équipotents [Xuong1992]). Ainsi, l’ensemble des entiers et l’ensemble des carrés d’entiers avaient bien << autant >> d’éléments. Les ensembles qui peuvent être mis en correspondance un à un avec l’ensemble des entiers naturels10 sont dits dénombrables.
Cantor démontra rapidement que l’ensemble des fractions rationnelles était lui aussi dénombrable, ainsi que l’ensemble des nombres algébriques11. Se posa alors le problème de savoir s’il existait des ensembles non dénombrables. Cantor s’intéressa à l’ensemble des fonctions définies partout sur l’ensemble des entiers naturels12 i.e., les fonctions de ℕ dans ℕ. Cantor démontra que cet ensemble n’était pas dénombrable, en utilisant une méthode, dite méthode de la diagonale cantorienne13, que nous allons étudier plus en détail ; nous aurons en effet à la réutiliser dans les paragraphes suivants pour démontrer la non-calculabilité de certaines fonctions.
La démonstration de Cantor est une démonstration par l’absurde. Il suppose qu’il existe une correspondance un à un entre l’ensemble de fonctions sur ℕ et l’ensemble des entiers naturels. On peut alors numéroter ces fonctions à l’aide de cette correspondance : f0,f1,f2,…,fn… On définit alors la fonction :
La fonction f que nous venons de construire est une fonction partout définie sur ℕ. Donc elle doit appartenir à notre énumération de fonctions. Donc, il doit exister un nombre n tel que pour tout i :
Mais considérons alors l’égalité précédente en prenant pour valeur de i précisément n :
Ceci est évidemment impossible, donc il n’existe pas de correspondance un à un entre l’ensemble des fonctions partout définies sur ℕ et l’ensemble ℕ. Pourquoi appelle-t-on cette méthode diagonale cantorienne ? On peut le voir sur le tableau 1.1.
0 1 2 … f0 f0(0) f0(1) f0(2) … f1 f1(0) f1(1) f1(2) … f2 f2(0) f2(1) f2(2) … … … … … …
La méthode de Cantor consiste à prendre chaque élément de la diagonale en lui ajoutant 1 pour définir sa fonction f. Par une méthode analogue, il est possible de démontrer que l’ensemble des fonctions de ℕ dans {t,f} ou que l’ensemble des nombres réels ne sont pas dénombrables14.
Fort de ces résultats, Cantor se lança dans une théorie générale des ensembles abstraits. La définition de Cantor laisse cependant une large part à l’intuition : << Par un ensemble, j’entends toute collection M d’objets bien distincts m de notre perception ou de notre pensée >>. Nous allons voir que le flou laissé autour de la définition d’ensemble va amener nombre de paradoxes.
Un des paradoxes les plus célèbres est sans doute celui de Russell. Russell considère l’ensemble E de tous les ensembles qui ne se contiennent pas eux-mêmes. La question que pose alors Russell est la suivante : E se contient-il lui-même ? Examinons successivement les deux possibilités :
Ce type de paradoxes découle du flou laissé par Cantor autour de sa définition d’ensemble. Il fut nécessaire de reformaliser sa théorie, en fait de construire une axiomatique formelle des ensembles abstraits. Zermelo, dès 1908, fut le premier à proposer de construire un tel système pour réduire la notion intuitive d’ensemble à une notion formelle. Une excellente axiomatique formelle des ensembles fut fournie par Gödel en 1940. Les lecteurs intéressés peuvent se reporter à [Kleene1987]. Cette classe de paradoxes est souvent désignée sous le nom de paradoxes logiques, dans la mesure où ils sont liés à la logique de la théorie en cause (ici la théorie ensembliste).
Les paradoxes sémantiques forment une toute autre classe de paradoxes. Un des plus célèbres est le paradoxe de Berry. On considère le nombre naturel défini par << le plus petit nombre entier ne pouvant être exprimé en moins de quinze mots >>. On sait qu’il existe un ensemble des nombres naturels qu’on ne peut définir en moins de quinze mots. En raison des propriétés des sous-ensembles de ℕ, cet ensemble admet une borne inférieure I. Il semble même que ce nombre I soit 1297297 (un million deux cent quatre-vingt-dix-sept mille deux cent quatre-vingt-dix-sept, soit exactement quinze mots). Mais ce nombre I est aussi défini par l’expression << le plus petit nombre entier ne pouvant être exprimé en moins de quinze mots >>. Or cette expression comporte quatorze mots. Il y a donc contradiction. Ce type de paradoxe est d’origine sémantique, c’est-à-dire lié au langage dans lequel nous exprimons la définition. En fait nous construisons là une définition auto-référente (cf. [Alliot and Schiex1993], page ??) : nous utilisons un langage qui opère sur lui-même. Les paradoxes sémantiques attirèrent l’attention sur la nécessité d’utiliser des langages précis et restreints à un ordre de raisonnement. Nous retrouvons le problème que nous évoquions lors de l’introduction au chapitre ?? : celui du langage objet et du langage de l’observateur. Nous n’avons pas le droit d’utiliser le langage objet (d’ordre n) pour parler des objets, nous devons utiliser la langue de l’observateur (d’ordre n+1). De même si nous voulions parler du langage qui parle du langage qui parle de la logique, il nous faudrait définir un langage formel d’ordre n+2 (ou plutôt (n+1)+1). On peut citer comme autre genre de paradoxe sémantique le célèbre paradoxe du menteur : << la phrase que je dis est fausse >>, connu depuis l’Antiquité (Epiménide VIe siècle A.C).
La théorie des types de Russell a précisément été créée dans le but de formaliser correctement ce type de problèmes. Le but initial de Russell est la réduction des mathématiques à la théorie logique. Les Principia Mathematica publiés avec Whitehead de 1910 à 1913 constituent le travail qui fondera la logique moderne. Comme le signale D. Dubarle [Dubarle1967], c’est Wittgenstein qui le premier remarquera le problème principal du réductionnisme de Russell [Wittgenstein1961] :
<< 6.1 Les propositions de la logique sont les tautologies.6.31 La soi-disant loi d’induction ne peut en aucun cas être une loi logique, car elle est de toute évidence une proposition ayant un sens. >>
L’axiome de l’infini de Russell (nécessaire à la démonstration de la loi d’induction) n’a pas le caractère d’évidence indispensable pour faire des Principia Mathematica un fondement valable de la mathématique, sur un plan philosophique.
Comme le fait d’ailleurs remarquer Kleene (1967) :
<< Le problème [des paradoxes] est plus profond [qu’on ne pourrait le croire] et nous contraint à nous demander sur quels points nous avons été induits en erreur par des méthodes de construction et de raisonnement qui avaient toujours paru convaincantes avant qu’on se fût avisé qu’elles aboutissaient à des paradoxes. L’unanimité entre les mathématiciens touchant les causes des paradoxes et les remèdes à y apporter n’a pas encore été atteinte et il est douteux qu’elle le soit jamais. >>
L’ensemble des problèmes rencontrés par les mathématiques que nous venons de décrire dans ce chapitre semblait montrer qu’il était temps de renoncer aux mathématiques << intuitives >> pour en venir à des constructions formelles pures, bien que la tentative logiciste formelle de Russell ait déjà montré quelques faiblesses. C’est dans ces conditions qu’éclata la controverse entre formalistes et intuitionnistes.
Au lieu de tenter de résoudre les problèmes des mathématiques par des constructions formelles où l’intuition n’aurait plus sa place, les intuitionnistes souhaitaient revenir en arrière et ne conserver des mathématiques que la partie intuitivement accessible. Ils refusaient en particulier la notion d’infini achevé : pour eux, l’existence d’un ensemble achevé contenant tous les nombres naturels n’était pas évidente. Seul existait le fait, qu’on pouvait toujours construire un nombre plus grand que n’importe quel autre nombre. Tous les objets mathématiques devaient se construire15.
Ce type d’attitude conduisit Brouwer16 à contester certains principes considérés jusque-là comme évidents, comme le principe du tiers exclus17. Brouwer reconnaissait volontiers que dans le cas où le domaine D que parcourt un prédicat P(x) est fini, ∃ x P(x) ∨ ¬ ∃ x P(x) est vrai. Il est en effet possible dans ce cas de vérifier pour chaque élément de D si l’on a P(x).
En revanche, pour un ensemble D infini, ∃ x P(x) ∨ ¬ ∃ x P(x) n’est pas forcément vrai. Il nous est en effet matériellement impossible de vérifier pour tous les éléments de D si l’on a P(x). Bien sûr, nous pouvons, avec de la chance, trouver un tel x rapidement, mais nous pouvons aussi bien ne jamais le trouver.
Il y a une autre conséquence des notions intuitionnistes : pour démontrer ∃ x P(x), il faut trouver un tel x et l’exhiber. Une démonstration par l’absurde, qui montrerait la fausseté de ¬ ∃ x P(x) ne montrerait en aucun cas qu’un tel x existe mais seulement que ¬ ¬ ∃ x P(x) est vraie.
On voit donc que pour un intuitionniste, dans un ensemble infini, ¬ ¬ A n’est pas systématiquement équivalent à A.
Depuis 1918, les mathématiques intuitionnistes se sont développées parallèlement aux mathématiques << traditionnelles >>. Les démonstrations constructivistes donnent souvent des résultats plus tangibles que les démonstrations formelles, mais sont plus difficiles. Il faut reconnaître que les intuitionnistes sont restés en deçà des résultats formalistes.
Leur apport fut néanmoins très important, surtout sur le plan épistémologique, car il conduisit à une réflexion profonde sur la façon d’appréhender l’infini.
L’école formaliste emmenée par le mathématicien David Hilbert choisit une voie totalement différente de la voie intuitionniste.
Constatant que les paradoxes venaient de systèmes d’axiomes insuffisamment formalisés, Hilbert proposa de rédiger une théorie purement formelle des mathématiques et de démontrer sa consistance formelle. En effet, on avait jusque là toujours démontré les propriétés de consistance par rapport à des modèles : la géométrie de Bolyai-Lobachevsky avait été ramenée à la géométrie euclidienne, la géométrie euclidienne à l’analyse (Descartes)…Or ce type de démonstration montre seulement qu’une théorie est consistante si une autre théorie l’est. La propriété de consistance formelle demande simplement qu’à l’intérieur de la théorie formelle, on ne puisse avoir une formule qui soit démontrable et dont la négation soit démontrable (ce qui constituerait un paradoxe). Hilbert imposa également que les méthodes de démonstration de ce type de propriété soient << intuitivement convaincantes >> et finitistes, c’est-à-dire ne faisant jamais appel à l’infini achevé. Hilbert appela cette nouvelle branche des mathématiques métamathématique. Hilbert énonça ce programme en 1908, et la réalisation commença vers 1920.
Hilbert se justifia de son attitude face à celle des intuitionnistes de la façon suivante : il scinda les mathématiques en deux domaines, celui des énoncés réels qui ont un sens intuitif et celui des énoncés idéaux qui n’en ont pas. Les énoncés idéaux ne sont que des moyens théoriques et élégants de simplifier les démonstrations d’une théorie donnée (cf. [Péter1977]). Il est ainsi plus facile de démontrer que a.n+b prend une infinité de valeurs premières si a et b sont premiers entre eux en utilisant des méthodes analytiques (théorie << idéale >> des fonctions holomorphes) qu’en passant par une méthode << intuitive >> n’utilisant que des résultats sur les nombres entiers. Il est même des cas où le recours à la théorie idéale est obligatoire, simplement parce qu’on ne connaît pas d’autres moyens de résoudre le problème. On peut également citer comme exemple concluant de cette attitude la construction de la géométrie projective (théorie idéale) à partir de la géométrie euclidienne traditionnelle.
Si l’ensemble de la communauté scientifique ne fut pas convaincu, nombre de mathématiciens se lancèrent cependant dans la réalisation du programme de Hilbert18 et les résultats qu’ils allaient obtenir devaient se révéler assez inattendus.
L’idée originelle de Hilbert était de construire un système formel des mathématiques, ou tout au moins de l’analyse. Mais le problème se révéla tellement complexe que lui et ses élèves se limitèrent à construire un système formel de l’arithmétique. Nous allons décrire ce système. Nous insistons cependant sur le fait que les définitions données ci-dessous n’ont pas toujours toute la précision nécessaire, mais la mise en place parfaitement rigoureuse d’un système formel de l’arithmétique dépasserait, et de beaucoup, le cadre de cet ouvrage.
L’arithmétique formelle est une extension de la théorie de la démonstration19 du calcul des prédicats.
[Symboles] Les symboles de l’arithmétique formelle seront :
Les lettres a,b,c,… sont les variables de notre langage. Afin d’en disposer d’une infinité, nous admettons également comme variable les termes de la forme a||…|20. Nous allons définir les termes de notre langage. [Termes]
Tout terme est obtenu en appliquant un nombre fini de fois les règles précédentes.
Il nous reste à définir les formules de notre langage : [Formules]
Toute formule est obtenue en appliquant un nombre fini de fois les règles précédentes.
Munis du langage, nous allons pouvoir définir les axiomes et règles d’inférence du système formel ℕ.
[Axiomes et règles d’inférence standards]
Les axiomes et les règles d’inférence du calcul des prédicats s’appliquent dans le système formel ℕ.
Les axiomes que nous allons définir ensuite sont appelés axiomes non-logiques. Pourquoi ce nom ? Les axiomes que nous avons définis jusqu’ici ne remettent pas en cause les notions du calcul des prédicats et en particulier la notion de conséquence valide. En revanche, les axiomes que nous allons introduire ne peuvent plus s’interpréter au niveau de la notion de conséquence valide que comme des hypothèses de calcul, dans la mesure où ils n’ont pas de vérité logique. C’est en raison de ces axiomes que les résultats du calcul des prédicats ne peuvent s’étendre directement à l’arithmétique formelle. Nous essaierons de donner de chacun de ces axiomes une interprétation matérielle intuitive.
| A(0) ∧ ∀ x (A(x) → A(x′)) → A(x) |
Si nous interprétons l’opérateur ′ comme successeur de, alors l’axiome précédent se comprend immédiatement comme la définition de la récurrence : si la propriété est vraie pour 0 et que, si elle est vraie pour n, elle est vraie pour n+1, alors elle est vraie pour tout n21.
[Quatrième axiome de Peano]
| a′=b′ → a=b |
Cet axiome formalise que : a+1=b+1 → a=b [Cinquième axiome de Peano]
| ¬ a′ =0 |
Il n’existe aucun nombre ayant 0 pour successeur. [Pseudo-Transitivité de l’égalité]
| a=b → (a=c → b=c) |
[Égalité]
| a=b → a′=b′ |
Axiome fondateur de l’égalité et de la notion de successeur avec le quatrième axiome de Peano ; si a=b alors a+1=b+1. [0 élément neutre pour l’addition]
| a+0=a |
[Successeur et addition]
| a+b′=(a+b)′ |
[0 élément absorbant de la multiplication]
| a.0=0 |
Définit 0 comme élément absorbant de la multiplication. [Distributivité de la multiplication]
| a.b′=a.b+a |
À partir des définitions données ci-dessus, il est possible de définir la suite des nombres 1,2,3…récursivement en posant 1=0′, 2=1′=0 >>…
On ne peut définir dans ℕ que des fonctions polynomiales, en raison du symbolisme extrêmement pauvre du langage. Mais l’on peut, en revanche, définir pour toute fonction arithmétique f(x1,…,xn) un prédicat p(x1,…,xn,y) qui est vrai si et seulement si f(x1,…,xn)=y. On peut alors << parler >> d’une fonction et opérer sur elle en travaillant sur le prédicat associé qui, lui, appartient bien au système formel. Ainsi considérons la fonction indicatrice22 des nombres pairs P(x) et son prédicat associé p(x,y). Le théorème P(x+2)=P(x) s’exprimera dans ℕ par ∃ u ∃ v (p(x+2,u) ∧ p(x,v) ∧ (u=v)).
Il est également possible de définir les symboles traditionnels de l’arithmétique classique comme synonymes de formules plus complexes. C’est le cas de > ou de < ou de l’exponentiation. En fait, l’essentiel des relations familières au mathématicien sont définissables.
On pense donc que le système formel ℕ que nous venons de définir a bien comme interprétation standard, l’arithmétique telle que nous la pratiquons couramment. Si tel n’était pas le cas, il est clair que notre formalisme n’atteindrait pas son but.
Nous ne donnerons pas d’exemple de démonstration formelle dans ℕ. De telles démonstrations sont excessivement lourdes. La démonstration du théorème a=a ne prend pas moins de 17 lignes ! Nous utiliserons d’ailleurs tout au long des paragraphes suivants des démonstrations informelles.
Nous devons bien nous rappeler le but d’Hilbert : il s’agit, maintenant que les bases formelles sont posées, de démontrer la consistance formelle de ℕ (i.e., il n’existe pas dans ℕ une formule E telle que ⊢ E et ⊢ ¬ E).
En 1925, Ackermann publia une démonstration de consistance de ℕ. Mais deux ans plus tard, Von Neumann montrait que la démonstration d’Ackermann ne s’appliquait qu’à un sous-système de ℕ, dans lequel l’axiome 1.4 est remplacé par un axiome voisin, mais plus faible.
En fait, les tentatives de démonstration de la consistance étaient vouées à l’échec comme allait le montrer Gödel. La démonstration originale de Gödel n’est pas celle que nous allons donner. Nous présenterons la démonstration donnée par Kleene en 1943, démonstration qui s’appuie sur les machines de Turing.
Nous avons déjà effleuré les problèmes de calculabilité et de décidabilité dans le chapitre consacré aux machines de Turing.
Rappelons la définition que nous avons donnée de la calculabilité : [Calculabilité] Une fonction est dite calculable s’il existe une procédure algorithmique finie permettant de calculer en un nombre de pas fini sa valeur pour tout argument de son domaine.
La notion de décidabilité est très proche de la définition de calculabilité, mais s’applique à des problèmes de décision i.e., à des classes de questions auxquelles la réponse est oui ou non. :
[Décidabilité]
Une classe de questions est dite décidable s’il existe une procédure algorithmique finie permettant de résoudre n’importe laquelle des questions de cette classe en un nombre fini de pas. Des problèmes classiques de décision dans un système formel sont : << Une suite de symboles donnée est-elle une formule bien formée ? >> ou << Une suite d’expressions donnée est-elle la démonstration d’une formule ? >> ou encore << Une formule donnée est-elle démontrable ? >>.
Les deux premières questions sont décidables. Il n’en est pas de même pour la troisième. Nous connaissons des cas où l’on sait résoudre le problème de décision : il s’agit par exemple du calcul propositionnel, par application de la méthode des tables de vérité. En revanche, nous ne savons pas a priori s’il existe une procédure de décision pour ℕ. Or une telle procédure permettrait de résoudre de façon simple et mécanique tous les problèmes concernant l’arithmétique élémentaire non encore résolus aujourd’hui. On pourrait ainsi prouver que la conjecture de Goldbach23 ou le grand << théorème >> de Fermat24 sont démontrables ou indémontrables en appliquant mécaniquement cet algorithme. Il semble difficile de trouver une telle procédure. Il semblait encore plus difficile de prouver qu’elle n’existait pas. C’est pourtant ce que Church a fait.
La thèse de Church-Turing, que nous avons présentée au chapitre ??, ramène la notion de calculabilité intuitive à la notion de calculabilité pour les machines de Turing. Nous avons déjà évoqué les arguments en faveur de cette thèse. Nous la supposons admise dans la suite de l’énoncé. Rappelons la notion de décidabilité au sens de Turing : un prédicat est décidable au sens de Turing s’il existe une machine de Turing capable de déterminer sa vérité ou sa fausseté. La thèse de Church-Turing implique que la décidabilité intuitive et la décidabilité au sens de Turing sont équivalentes.
Considérons de nouveau les machines de Turing que nous avons présentées au chapitre ??. Une machine de Turing est entièrement déterminée par son tableau, qui représente son programme. Ainsi le tableau 1.2
B 0 1 z0 (z1,B,G) (z0,0,D) (z0,1,D) z1 (zh,1,I) (zh,1,I) (z1,0,G)
détermine totalement une machine de Turing (celle qui calcule la fonction f(x) = x+1). Nous pouvons réécrire le programme précédent, en représentant un état zi par i, sous la forme :
Tout programme de machine de Turing peut donc s’écrire à l’aide des dix-sept symboles suivants25 :
Tout programme de machine de Turing peut donc être écrit sous la forme d’un nombre en base 17. De même, tout mot de Γ * (de cardinal 11) peut se traduire de façon unique en un élément de ℕ.
[Index d’une machine de Turing] Le nombre i (en base 17) qui représente une machine de Turing est appelé index de la machine de Turing, machine que nous noterons Mi26.
Il découle immédiatement des résultats précédents le théorème : L’ensemble des machines de Turing est dénombrable. Nous devons commencer à sentir le résultat plus proche. En effet, nous avons démontré au début de ce chapitre que l’ensemble des fonctions à variable entière était non-dénombrable, et nous venons de montrer que l’ensemble des fonctions que nous pouvons calculer est << seulement >> dénombrable. Nous sommes donc déjà convaincus qu’il existe bien des fonctions non-calculables. Il nous suffit maintenant d’en exhiber une. Il nous reste quelques étapes à franchir avant d’en arriver là.
Nous posons T(i,a,n) le prédicat T qui prend la valeur vraie lorsque la machine de Turing dont l’index est i, appliquée à l’argument a, calcule au bout de n étapes exactement un résultat que nous noterons ϕi(a). Remarquons que T(i,a,n) est également faux si i n’est pas l’index d’une machine de Turing valide. Nous allons établir deux résultats fondamentaux sur T et ϕ.
Le prédicat T(i,a,n) est décidable (au sens intuitif et au sens de Turing).
Les valeurs de i, a et n étant données, il est possible de vérifier que i est bien l’index d’une machine de Turing valide. Si ce n’est pas le cas, T est faux. Si c’est le cas, nous pouvons appliquer la machine de Turing Mi à a et regarder si au bout de n étapes la machine vient juste de terminer le calcul d’une valeur. Si c’est le cas T(i,a,n) est vrai, sinon il est faux.
T étant décidable au sens intuitif, il est décidable au sens de Turing, d’après la thèse de Church-Turing.
La fonction partielle ϕi est calculable. Nous disons que ϕi est une fonction partielle car elle n’est définie que pour les valeurs de a et de i telles qu’il existe un n tel que T(i,a,n) est vrai. Dire que ϕi est une fonction partielle calculable consiste simplement à dire que si ϕi est définie pour l’index i et l’argument a, alors elle est calculable. Le résultat dans ces conditions est évident. Il suffit d’appliquer la machine Mi à l’argument a et attendre qu’elle ait calculé un résultat (ce qui arrivera car ∃ n T(i,a,n) est vrai).
Il est temps pour nous d’arriver au résultat fondamental de cette section : Soit la fonction ψ définie par :
| ψ(a) = | ⎧ ⎨ ⎩ |
|
ψ n’est pas calculable. Supposons en effet que ψ soit calculable. Alors il existe une machine de Turing Mj qui calcule ψ. Nous avons donc pour tout a : ψ(a) = ϕj(a) et en particulier pour a=j nous avons :
| ψ(j) = ϕj(j) |
Comme Mj calcule ψ, nous avons pour tout a, ∃ n T(j,a,n) En particulier, pour a=j, nous savons qu’il existe n tel que T(j,j,n). Or en appliquant directement la définition de ψ nous obtenons :
| ψ(j) = ϕj(j)+1 |
Ce qui est en contradiction avec l’équation précédente. Q.E.D.
On remarquera que cette démonstration s’appuie une fois de plus sur la méthode de la diagonale cantorienne.
Il existe un corollaire important à ce théorème : Le prédicat ∃ n T(a,a,n) est indécidable. Si ce prédicat était décidable, nous pourrions pour un a donné décider s’il existe n tel que T(a,a,n). Si tel n’était pas le cas nous saurions que la valeur de ψ(a) est 0. Sinon, nous pourrions appliquer la machine de Turing Ma à l’argument a, récupérer le résultat du calcul au bout des n étapes, lui ajouter 1, ce qui nous donnerait la valeur de ψ(a). Nous venons de décrire là une procédure27 de calcul de ψ. Or ψ n’est pas calculable, donc, par réduction à l’absurde, ∃ n T(a,a,n) est indécidable. Plus généralement, le prédicat ∃ n T(i,a,n) est indécidable. On en conclut que le problème de l’arrêt d’une machine de Turing est, lui aussi, indécidable.
La démonstration de l’indécidabilité de ℕ va s’appuyer sur le résultat précédent. Il semble clair que le prédicat ∃ n T(a,a,n) peut se formaliser dans ℕ. Les machines de Turing ne comprennent dans leur définition que des opérations arithmétiques élémentaires et le prédicat T ne fait appel à aucune notion autre qu’arithmétique ou liée au calcul des prédicats. Il doit donc exister dans ℕ une formule qui a comme interprétation28 ∃ n T(a,a,n). Appelons Ca cette formule.
Remarquons maintenant que :
| ∃ n T(a,a,n) entraîne { ⊢ Ca dans ℕ } |
En effet, si l’on sait qu’il existe un n tel que T(a,a,n), on peut le démontrer informellement en construisant chacune des étapes de la machine de Turing associée. Une telle démonstration peut évidemment se formaliser dans ℕ.
Si nous supposons que seules les formules vraies sont démontrables29, nous avons :
| { ⊢ Ca dans ℕ } entraîne ∃ n T(a,a,n) |
En fait, Ca représente exactement ∃ n T(a,a,n).
[Indécidabilité de ℕ] ℕ est indécidable i.e., il n’existe pas de procédure de décision permettant d’établir la démontrabilité d’une formule. En effet, si une telle procédure existait, il serait possible, pour a donné, de savoir si Ca est démontrable ou non. On disposerait donc d’une procédure de décision pour T(a,a,n), ce qui est impossible.
Il n’existe donc aucune procédure algorithmique permettant de déterminer la vérité ou la fausseté d’une formule quelconque de ℕ comme nous pouvions le faire avec les tables de vérité en calcul propositionnel.
Nous allons avoir besoin de quelques propriétés supplémentaires pour démontrer l’incomplétude de ℕ (rappelons qu’il s’agit de montrer qu’il existe une formule F telle que l’on ait ni ⊢ F, ni ⊢ ¬ F).
Notons tout d’abord que comme dans ℕ seules les formules vraies sont démontrables, nous avons :
| { ⊢ ¬ Ca dans ℕ } entraîne ¬ ∃ n T(a,a,n) |
Nous allons maintenant nous appuyer sur deux éléments fondamentaux liés à l’architecture de ℕ. La première est que dans ℕ, on peut reconnaître la démonstration d’une formule comme telle : la reconnaissance d’une démonstration est un problème décidable, comme nous l’avions déjà fait remarquer. Ensuite, nous devons remarquer que les symboles permettant de construire les formules de ℕ étant en nombre fini, le nombre de formules et de démonstrations est donc dénombrable, et l’on peut en établir une énumération. Ce dernier point est la clé de voûte de l’ensemble des démonstrations d’incomplétude dans les systèmes formels ; toute démonstration d’incomplétude revient finalement à montrer qu’il y a un nombre non dénombrable de formules vraies, alors qu’il y a seulement un nombre dénombrable de démonstrations (de la même façon que l’on montre qu’il y a une infinité non-dénombrable de fonctions et seulement un nombre dénombrable de fonctions calculables).
Les deux points précédents étant établis, il devient évident qu’il est possible de construire une machine de Turing Mj qui, parcourant l’ensemble des démonstrations de ℕ, imprime 1 et s’arrête si elle trouve une démonstration de ¬ Ca, et ne s’arrête jamais sinon. Ceci se résume par :
| ∃ n T(j,a,n) est équivalent à { ⊢ ¬ Ca dans ℕ } |
Nous pouvons donc résumer les trois points que nous avons établis et qui vont nous permettre de poursuivre la démonstration :
Nous pouvons maintenant démontrer le théorème d’incomplétude de Gödel. Supposons qu’il existe n tel que T(j,j,n). Alors d’après (3), nous avons : ⊢ ¬ Cj. Mais alors (2) nous donne : ¬ ∃ n T(j,j,n). Ceci contredit l’hypothèse. Donc nous avons ¬ ∃ n T(j,j,n), donc ¬ Cj est vrai.
Mais d’autre part, ¬ ∃ n T(j,j,n) impose d’après (3) que non ⊢ ¬ Cj.
Enfin, supposons que ⊢ Cj ; alors d’après (1), nous savons qu’il existe un n tel que T(j,j,n), ce qui impliquerait que Cj soit vrai. Or ceci est contradictoire avec le premier point que nous avons démontré. Donc, on n’a pas ⊢ Cj.
Nous pouvons résumer nos trois résultats dans le théorème suivant : [Théorème d’incomplétude] Dans ℕ, nous pouvons trouver une formule liée Cj telle que
Nous avons donc démontré que pourvu que ℕ soit adéquat et que seules les formules vraies soient démontrables dans ℕ, ℕ est incomplet, c’est-à-dire qu’il existe des formules (vraies d’après l’interprétation standard) qui ne sont pas démontrables et dont la négation n’est pas non plus démontrable.
Essayons de comprendre comment nous sommes arrivés à ce résultat ; reprenons (3)
| ∃ n T(j,j,n) est équivalent à { ⊢ ¬ Cj dans ℕ } |
Dans l’interprétation que nous utilisons, ¬ Cj exprime ¬ ∃ n T(j,j,n). Nous avons donc construit une formule qui dans l’interprétation considérée exprime sa propre indémontrabilité. Il s’agit d’une assertion très proche du paradoxe du menteur.
Le résultat qui découle du théorème d’incomplétude est qu’il est impossible de formaliser l’ensemble des propriétés de l’arithmétique standard dans un système formel. La formule ¬ Cj est une propriété de l’arithmétique, vraie, mais indémontrable. Une partie du programme de Hilbert disparaissait.
Nous ne donnerons qu’une idée de la démonstration montrant qu’il est impossible de démontrer la consistance formelle de ℕ dans le système formel ℕ.
Constatons tout d’abord que dans notre démonstration nous avons utilisé comme hypothèse : { ⊢ ¬ Ca dans ℕ } entraîne ¬ ∃ n T(a,a,n)
En fait cette hypothèse peut se réduire à la notion de consistance de ℕ : il n’existe pas dans ℕ de formule F telle que ⊢ F et ⊢ ¬ F. Il suffit pour s’en convaincre de constater que ({ ⊢ ¬ Ca dans ℕ } entraîne ¬ ∃ n T(a,a,n)) se démontre à partir de (∃ n T(a,a,n) entraîne { ⊢ Ca dans ℕ }) et de la consistance simple.
Donc nous avons : (ℕ est simplement consistant) entraîne (¬ Cj est vrai) (ici j représente le j particulier du théorème précédent).
La suite de la démonstration consiste à remarquer que l’on peut exprimer de façon formelle la proposition : ℕ est simplement consistant. Il suffit de considérer que l’on peut construire une machine de Turing Mk cherchant dans les démonstrations de ℕ une démonstration d’une formule de la forme F ∧ ¬ F, qui imprime 1 si elle en trouve une et ne termine jamais sinon.
Alors la consistance de ℕ est équivalente au fait que, pour un a quelconque, il n’existe pas de n tel que T(k,a,n). En particulier, il ne doit pas exister de n tel T(k,k,n). Ce prédicat peut être formalisé, nous le savons déjà, par une formule de ℕ que nous appellerons C. Nous pouvons alors reprendre la proposition : (ℕ est simplement consistant) entraîne (¬ Cj est vrai). Elle devient formellement :
| C → ¬ Cj |
Hilbert et Bernays ont montré en 1939 que cette formule est démontrable dans ℕ, ce qui est assez naturel dans la mesure ou ℕ doit être adéquat à notre modèle intuitif de l’arithmétique. Donc :
| ⊢ C → ¬ Cj |
Supposons maintenant que ⊢ C (c’est-à-dire que la consistance de ℕ est démontrable), alors nous obtenons ⊢ ¬ Cj, ce qui contredit le théorème précédent (nous avons montré par le théorème d’incomplétude que nous n’avons pas : ⊢ ¬ Cj).
D’où le résultat : [Indémontrabilité de la consistance de ℕ] La formule C exprimant formellement dans ℕ la consistance de ℕ est indémontrable dans ℕ.
Nous ne nous attarderons pas sur les conséquences du théorème de non-démontrabilité de la consistance. Disons simplement que, pour nombre de mathématiciens, il signifia la fin de l’espoir d’obtenir une garantie de la sûreté des mathématiques classiques.
En revanche, la notion de non-décidabilité et de non-calculabilité nous intéresse au premier chef. Ces résultats ont donné naissance à une branche fructueuse de l’informatique, la théorie de la calculabilité et de la complexité. Ils ont également fourni un argument aux défenseurs de l’IA : << dans la mesure où des fonctions ne sont pas calculables, et où nous voulons tout de même obtenir des résultats utilisables, nous sommes obligés d’utiliser des méthodes heuristiques, méthodes caractéristiques d’une approche IA. >> Il faut cependant prendre ce raisonnement avec prudence ; un algorithme d’intelligence artificielle s’exécutera, comme tout autre algorithme, sur une machine de Turing, et est donc soumis aux mêmes limitations.
Le théorème d’incomplétude nous intéresse également dans la mesure où, selon certains, il montre qu’il existe des propositions vraies qu’aucun moyen mécanique ne permet de démontrer ; certains adversaires de l’IA se sont servis de cet argument pour prétendre qu’un calculateur ne pourrait jamais réaliser certains travaux réalisés par l’esprit humain. L’argument doit aussi être prudemment considéré.
On peut, d’autre part, se demander si la démonstration d’incomplétude ne vient pas de la trop grande pauvreté du jeu d’axiomes que nous avons utilisé au départ. Si nous ne parvenons pas à démontrer une propriété que nous savons vraie (comme celle que nous avons construite lors de la démonstration du théorème d’incomplétude), il nous suffit de l’inclure comme axiome supplémentaire. On pourrait ainsi espérer construire un système complet par ajout successif de toutes les propriétés vraies que nous ne pouvons démontrer. Il existe malheureusement une objection majeure à cette méthode. Une extension du théorème de Gödel stipule que pour tout système formel contenant l’arithmétique, il est possible de construire une propriété vraie non-démontrable, en utilisant d’ailleurs une méthode très voisine de celle que nous venons de présenter. Ceci ruine définitivement nos espoirs. Disons tout de même que le théorème d’incomplétude n’est pas aussi anti-naturel ou anti-intuitif qu’il peut apparaître au premier abord. En fait, il exprime que notre modèle intuitif de l’arithmétique est trop riche pour être réduit à un quelconque système formel, ce qui peut sembler relativement normal. Depuis la démonstration du théorème d’incomplétude, des modèles différents vérifiant l’axiomatique formelle de l’arithmétique ont été développés ; il a été démontré que l’ensemble de toutes les formules vraies dans tous les modèles est exactement l’ensemble des théorèmes.
Au sujet des modèles non-standard, Thoralf Skolem a démontré, en étendant un théorème dû à Lowenheim, que toute formalisation axiomatique du premier ordre de la théorie des ensembles (dont le modèle standard admet, bien entendu, des ensembles non-dénombrables) admet un modèle dont le domaine d’objets est au plus dénombrable. Donc la théorie naïve des ensembles ne peut être formalisée de façon catégorique30 par un système axiomatique du premier ordre. Ce théorème n’est pas aussi paradoxal qu’il peut le paraître. En effet, toute théorie axiomatique formelle contient au plus, nous l’avons vu, un nombre dénombrable de démonstrations. Il semble clairement difficile dans ces conditions de représenter des ensembles non-dénombrables. On peut aussi mettre le théorème de Lowenheim-Skolem en relation avec le théorème d’incomplétude : considérons un système S << riche >>. Comme tous les systèmes << riches >> sont incomplets, on peut trouver une propriété p telle que les systèmes S ∪ p et S ∪ ¬ p soient des systèmes << corrects >>. Ces deux systèmes ne peuvent être catégoriques car les interprétations ne sont pas isomorphes.
Remarquons enfin la grande différence qui existe entre le théorème d’incomplétude et le théorème énonçant l’impossibilité de démontrer la consistance de ℕ dans ℕ. Le premier stipule qu’il existe des propriétés vraies non démontrables. Le second ne prétend en aucun cas qu’il existe des propriétés démontrables qui ne soient pas vraies. Il dit simplement que l’on ne peut démontrer la consistance de ℕ en utilisant seulement les axiomes de ℕ et des méthodes finitistes, comme l’exigeait Hilbert. Une démonstration de consistance utilisant des méthodes non-finitistes a d’ailleurs été publiée par Gerhard Gentzen peu après que Gödel ait énoncé son théorème. Cette méthode satisfait de nombreux mathématiciens, même si elle fait appel à la notion d’induction transfinie. Il ne faut donc en aucun cas parler de théorème d’inconsistance comme on parle du théorème d’incomplétude, mais bien d’un théorème de non-démontrabilité finitiste de la consistance, ce qui est bien différent.
Les résultats obtenus par Gödel ont eu des conséquences très importantes sur la communauté des mathématiciens eux-mêmes. Certains d’entre eux, dont Imre Lakatos, ont même estimé nécessaire de renoncer à la théorie de la démonstration pour ne garder aux démonstrations mathématiques que leur caractère intuitif [Lakatos1984] :
<< Pourquoi ne disons-nous pas que le test ultime permettant de savoir si une méthode peut-être admise en arithmétique revient à la question de savoir si elle est intuitivement convaincante ? >>
Il faut cependant faire une distinction entre ce qui apparaît comme deux parties fondamentalement différentes de la logique, que l’on a parfois tendance à confondre :
En fait, ces deux points correspondent à deux étapes pragmatiques du travail du mathématicien ou du logicien. Face à une réalité trop vaste pour être traitée efficacement, il commence par la réduire en un langage formel dans lequel il définit une théorie de la vérité et un modèle, puis il construit une théorie de la démonstration qui lui permet de vérifier la validité de ses intuitions dans le cadre de ce modèle. Les deux étapes sont indispensables, mais il ne faut pas attendre plus de la logique que ce qu’elle peut donner : sa démarche est réductionniste, et on ne peut trouver au bout de la chaîne un système aussi riche que le monde réel qu’elle modélise. La crise de la science actuelle est plus une crise liée aux limites de cette science qu’à ses fondements : ce qui est en cause, c’est le dogme réductionniste qui, si l’on caricature un peu, prétendait transformer sans perte de généralité le monde en un système axiomatique fini où tout serait démontrable. Il semble clair que le dogme a fait long feu, dans les deux domaines ; les philosophes semblent accepter l’impossibilité de réduire le langage ou la pensée humaine, ainsi que les notions intuitives de vérité et de validité sous-jacentes, à un système unique ; les mathématiciens sont conscients que la théorie sémantique et la théorie de la démonstration ne sont pas équivalentes, et qu’aucun système axiomatique fini ne peut représenter complètement et catégoriquement un modèle un peu complexe.
Il ne faut pourtant pas rejeter le travail accompli, ni refuser de le continuer. Il faut accepter la vision pragmatiste qui consiste à regarder la logique comme un outil, imparfait certes, mais pourtant indispensable. On ne peut rejeter les axiomes de la logique modale sous prétexte qu’elle est << née dans le péché >> (Quine), si celle-ci fournit un modèle utile pour formaliser le raisonnement. De même, on ne peut rejeter la théorie de la démonstration, sous prétexte qu’elle ne fournit pas une certitude absolue : elle n’est qu’une vérification de nos intuitions et a rempli et continuera à remplir parfaitement ce rôle.
Le téléchargement ou la reproduction des documents et photographies
présents sur ce site sont autorisés à condition que leur origine soit
explicitement mentionnée et que leur utilisation
se limite à des fins non commerciales, notamment de recherche,
d'éducation et d'enseignement.
Tous droits réservés.
Dernière modification: 09:48, 22/02/2024