Fondements des mathématiques/L'incomplétude mathématique
Un livre de Wikibooks.
Le contenu que vous recherchez a été déplacé vers la Wikiversité. Il devrait être disponible sous le nom Fondements des mathématiques.
| Fondements des mathématiques |
| Modifier le modèle |
L’existence des ensembles indicibles montre le caractère essentiellement incomplet de toute théorie mathématique. Cette incomplétude ontologique n’était pas considérée comme une restriction trop sévère avant que Gödel ait prouvé ses théorèmes d’incomplétude. Les mathématiciens pouvaient espérer que les éléments sans noms des ensembles indicibles n’étaient pas importants, que tous les ensembles “intéressants” pouvaient être définis à l’intérieur des théories existantes. La pratique confirmait cet espoir, parce que les outils connus de construction des ensembles étaient suffisants pour couvrir tous les besoins courants.
Les théorèmes de Gödel ont montré que l’incomplétude mathématique n’est pas seulement ontologique. Toutes les théories mathématiques générales sont incomplètes au sens où elles ne sont jamais capables de prouver toutes leurs vérités. Elles ne peuvent pas apporter de réponses à toutes les questions qu’elles permettent pourtant de poser. Elles ne contiennent jamais assez d’axiomes pour cela.
Le chapitre 6 prouvera que l’incomplétude de la prouvabilité axiomatique est étroitement liée à l’incomplétude ontologique, ce qui n’est pas étonnant, puisqu’une ontologie est fixée par des axiomes. Mais c’est très important pour comprendre que les théorèmes d’incomplétude sont des manifestations de la puissance de l’imagination et de la raison. Ils ne sont pas des preuves d’une insuffisance de la logique, comme cela est admis couramment, d’une façon incohérente, parmi de nombreux autres préjugés, ésotériques ou pseudo-mystiques, qui circulent sur ce sujet.
[modifier] Le paradoxe du menteur
Les théorèmes d’incomplétude mettent à profit un très ancien paradoxe. Quelqu’un dit “je mens”, est-ce qu’il ment ? S’il ment c’est qu’il ne ment pas. S’il ne ment pas c’est qu’il ment. Ce qu’il dit affirme sa propre fausseté. Le même paradoxe peut être présenté sous de nombreuses formes, parfois plus rigoureuses. La présente phrase qui commence par “la présente phrase” et finit par “est fausse” est fausse. Ou plus simplement. Cette phrase est fausse.
Une théorie est un ensemble de phrases. On peut la considérer comme une sorte de diseur de vérités. La théorie dit que toutes ses phrases sont vraies. Le paradoxe du menteur prouve qu’il y a des restrictions sur les capacités des diseurs de vérité quand ceux-ci sont capables de formuler des énoncés à propos de ce qu’ils disent. Supposons qu’un diseur de vérité soit capable de répondre par avance à toutes les questions sur ce qu’il va répondre. Posons-lui alors la question “à cette question vas-tu répondre non ?”. Qu’il réponde oui ou non, dans les deux cas il dit faux. Il ne peut donc pas répondre sans se tromper.
Il s’agit d’une incomplétude essentielle pour les théories et les diseurs de vérité. Ils ne peuvent pas dire toute la vérité sur tout ce qu’ils disent à partir du moment où leurs moyens d’expression sont suffisamment riches pour permettre de poser des questions telles que celle qui vient d’être citée. En résumé, dès qu’on peut poser à un diseur de vérité des questions telles que “à cette question vas-tu répondre non ?” il ne peut pas à la fois toujours répondre et toujours dire la vérité. Une théorie à la fois riche et vraie est forcément incomplète. Le paradoxe du menteur permet de prouver l’incomplétude des théories mathématiques dès que leurs moyens d’expression sont suffisamment riches. Gödel, Tarski, Church, Post, Türing et beaucoup d’autres ont montré que de très nombreuses théories permettent d’énoncer des formules paradoxales semblables à celle du menteur. En particulier, toutes les théories destinées à fonder les mathématiques, même l’arithmétique formelle, permettent d’énoncer de telles formules.
[modifier] Les prédicats de vérité et le théorème d’incomplétude de Tarski
Les énoncés paradoxaux sont produits par une technique logique très générale qui consiste à représenter les formules d’une théorie T par des objets de T. C’est possible dès que T contient les nombres entiers positifs parmi ses objets. Gödel et ses successeurs ont inventé des techniques de codage, de numérotation, qui permettent de représenter n’importe quelle formule par un entier, de telle façon que chaque entier représente au plus une formule.
Dans la suite, les théorèmes de Gödel et Tarski sont énoncés avec l’ensemble des nombres entiers positifs, qu’on appellera tout simplement nombres. Mais on pourrait remplacer cet ensemble par n’importe quel autre système formel infini. Quand on les énonce avec les nombres, ces théorèmes sont plus faciles à comprendre mais il est aussi plus difficile de prouver que les théories mathématiques générales satisfont aux conditions des théorèmes. Dans le chapitre suivant, nous prouverons qu’une théorie élémentaire des ensembles satisfait à ces conditions. Mais les formules ne seront pas représentées par des nombres. L’ensemble des noms que nous choisirons se prêtera plus aisément que les nombres à la représentation des formules.
Si une théorie a un modèle, l’ensemble de toutes ses formules vraies est défini sans équivoque. Lorsqu’une théorie est représenté à l’intérieur d’elle-même, l’ensemble de tous les objets qui représentent des formules vraies est lui aussi défini sans équivoque.
Toute théorie vraie permet de définir des ensembles même si elle n’est pas une théorie des ensembles, parce qu’elle permet toujours de définir des prédicats. Par exemple, le prédicat (il existe un y tel que x = y+y) contient x comme unique variable libre, il est donc unaire, et pour l’arithmétique il définit l’ensemble des nombres pairs. Un prédicat définit de même un ensemble de couples s’il est binaire, de triplets s’il est ternaire, et ainsi de suite.
On peut alors se demander si parmi tous les prédicats d’une théorie vraie, il y en a un qui définit l’ensemble de tous les représentants des formules vraies. Tarski a prouvé que sous des conditions générales, l’existence d’un tel prédicat est impossible. C’est une autre manifestation de l’incomplétude ontologique. Une théorie ne permet jamais de définir tous les ensembles qui ont cependant le droit d’exister. L’ensemble de tous les représentants des formules vraies existe d’une façon aussi certaine que tous les ensembles définis avec des moyens élémentaires.
Le théorème de Tarski dit qu’une théorie mathématique vraie et suffisamment riche ne permet jamais de définir un prédicat de vérité pour elle-même. Plus précisément les conditions du théorème sont les suivantes.
a) Une théorie T a suffisamment de moyens d’expression pour qu’elle compte parmi ses objets tous les nombres.
b) Elle est vraie au sens où elle a un modèle et où toutes ses formules arithmétiques vraies, au sens de la théorie des nombres, sont également vraies pour ce modèle.
c) Les opérateurs de la logique du premier ordre (négation, conjonction, existentiation) sont utilisés dans T.
d) Il existe un procédé de codage qui permet de représenter toutes les formules de T par un nombre unique et pour lequel il existe une formule de T, SUBxyz, qui contient trois variables libres, et qui est vraie si et seulement si (x représente une formule p de T avec une variable libre et z représente une formule obtenue par la substitution du nombre y à toutes les occurrences de la variable libre de p).
SUB est un prédicat ternaire de T. x représente n’importe quel prédicat unaire p de T.
On peut déduire de d) que SUB est une relation fonctionnelle de deux variables, au sens où pour tous w, x, y, z, si (SUBxyz et SUBxyw) alors z=w et où pour tous nombres x et y, si x représente un prédicat unaire de T alors il existe un z tel que SUBxyz.
Les conditions a, b, c et d sont très généralement vérifiées pour les théories destinées à fonder les mathématiques. Même l’arithmétique formelle est suffisamment riche pour se représenter ainsi elle-même. Mais la définition du prédicat ternaire SUB est techniquement assez élaborée et ne sera pas exposée ici.
Faisons alors l’hypothèse que T permet de définir un prédicat unaire, c’est à dire une formule avec une variable libre, Vx et que Vx est vrai si et seulement si x représente une formule vraie de T. Autrement dit, on suppose que T permet de définir un prédicat de vérité pour T.
Tarski a prouvé que cette hypothèse conduit à une contradiction.
Considérons la formule (il existe un z tel que SUBxxz et non Vz). C’est une formule avec une variable libre que T permet de définir. Elle est donc représentée par un nombre n de T. Il y a aussi un autre nombre AT de T tel que SUBnn(AT). Est-ce que AT représente une formule vraie ?
La formule représentée par AT dit que le prédicat représenté par n est vrai pour n. Le prédicat représenté par n est vrai pour x si et seulement si il existe un z tel que SUBxxz et non Vz. V(AT) est donc équivalent à (il existe un z tel que SUBnnz et non Vz) par définition de AT. De la condition c, on déduit que SUBnnz équivaut à z=(AT). Donc par définition de AT, V(AT) équivaut à non V(AT). C’est une contradiction. Il s’agit bien du paradoxe du menteur, parce que du fait de sa définition la formule représentée par AT dit d’elle-même qu’elle est fausse. Puisque l’hypothèse de l’existence du prédicat de vérité V conduit à une contradiction, elle doit être rejetée. Tel est précisément le théorème d’incomplétude de Tarski.
Une théorie mathématique vraie et suffisamment riche ne permet jamais de définir un prédicat de vérité pour elle-même.
Ou plus précisément.
Une théorie mathématique vraie T, pour laquelle les conditions a, b et c et d sont vérifiées, ne permet jamais de définir une formule à une variable libre qui serait vraie pour toutes les représentations des formules vraies de T et seulement pour elles.
Le théorème de Tarski n’est pas toujours applicable. Le chapitre suivant donnera deux exemples de prédicats de vérité. Le premier est un prédicat de vérité pour la théorie Enum de tous les ensembles énumérables. Son existence est une conséquence du théorème fondamental de l’énumérabilité. Dans ce cas, la condition b du théorème de Tarski n’est pas remplie. L’existence d’un prédicat de vérité pour la théorie Finitaire1 des ensembles finitaires de base pourra être établie avec un modèle non-standard, pour lequel il n’existe pas de prédicat ternaire SUB.
[modifier] Les prédicats de prouvabilité et le premier théorème d’incomplétude de Gödel
Gödel a prouvé qu’une théorie mathématique T vraie et suffisamment riche remplit une autre condition. Pour toute théorie axiomatique T’, il existe dans T un prédicat de prouvabilité pour T’, c’est à dire une formule à une variable x qui est vraie si et seulement si x représente un théorème de T’, c’est à dire une formule démontrable à partir des axiomes de T’. En particulier, T contient un prédicat de prouvabilité pour elle-même.
Même l’arithmétique formelle est capable de représenter ainsi toutes les théories axiomatiques. En ce sens on peut la voir comme une théorie universelle. Il suffit de savoir raisonner sur les nombres pour définir toutes les théories concevables. Les nombres peuvent être considérés comme les atomes, les principes premiers de la raison, au sens où tout le reste peut être construit à partir d’eux. Il y a quelque chose de pythagoricien, tout est nombre, dans cette approche gödelienne des mathématiques.
Comme pour la condition d du théorème de Tarski, la preuve de l’existence d’un prédicat de prouvabilité est un peu difficile quand on représente des formules par des nombres. Dans le chapitre suivant, on montrera que l’existence d’un prédicat de prouvabilité pour toute théorie axiomatique à l’intérieur d’une théorie élémentaire, Enum, est une conséquence directe du théorème fondamental de l’énumérabilité, qui sera démontré.
A partir du théorème de Tarski et de l’existence d’un prédicat de prouvabilité on déduit le premier théorème d’incomplétude de Gödel comme une conséquence directe.
Une théorie axiomatique, vraie et suffisamment riche, ne peut pas prouver toutes ses formules vraies.
Ce théorème peut être considéré comme un corollaire de celui de Tarski. Mais Gödel est le premier à avoir publié ses preuves. Tarski a eu les mêmes intuitions au même moment.
La fin de la preuve de Gödel est semblable à celle de Tarski, sauf qu’il se sert pas d’un prédicat de vérité mais du prédicat de prouvabilité dont il a montré auparavant l’existence.
Gödel considère alors la formule (il existe un z tel que SUBxxz et non Pz). Elle est représentée par un nombre n de T. Il y a aussi un autre nombre KG tel que SUBnn(KG). n et (KG) sont des nombres bien définis que l’on peut calculer dès que les axiomes de T et le procédé de représentation des formules de T par des nombres sont précisément définis.
KG représente-t-il une formule prouvable ?
La formule représentée par KG dit que le prédicat représenté par n est vrai pour n. Le prédicat représenté par n est vrai pour x si et seulement si il existe un z tel que SUBxxz et non Pz. La formule représentée par KG est donc équivalente à (il existe un z tel que SUBnnz et non Pz) par définition de KG. Or SUBnnz équivaut à z=(KG). Donc par définition de KG, la formule représentée par KG équivaut à non P(KG). Autrement dit la formule représentée par KG dit d’elle-même qu’elle n’est pas prouvable.
Si on suppose que T est cohérente alors KG est nécessairement vraie, parce que si elle ne l’était pas, alors elle serait prouvable, T permettrait de prouver une formule fausse et ne serait donc pas cohérente.
La partie longue de la démonstration de Gödel consiste à définir un prédicat de prouvabilité à l’aide d’une représentation des formules par numérotation. Après les découvertes de Church, Post et Türing, les résultats de Gödel sur la prouvabilité s’inscrivent dans un contexte plus général, celui des ensembles énumérables. Nous montrerons que l’ensemble des théorèmes, ou formules prouvables, d’une théorie axiomatique est énumérable.
On pourrait croire que les énoncés vrais mais non prouvables sont toujours des formules très compliquées, construites avec des techniques logiques paradoxales, qui n’interviennent jamais dans les mathématiques couramment étudiées. Autrement dit, on pourrait espérer que l’incomplétude est seulement marginale et qu’elle ne concerne pas les questions mathématiques importantes.
La preuve donnée par Cohen qu’une conjecture de Cantor, l’hypothèse du continu, n’est pas prouvable à partir des axiomes de ZFC, montre au contraire que l’improuvabilité est une question qui se pose vraiment. En nous fondant sur cette preuve nous montrerons que les ensembles indicibles sont indéfinis, au sens où il n’est pas possible de définir de façon univoque la notion de vérité à leur sujet.
Même des théorèmes des mathématiques élémentaires, sur les équations diophantiennes par exemple, ne peuvent pas être prouvés sur la base des seuls axiomes couramment acceptés.
[modifier] Les ensembles indicibles sont indéfinis
Les ensembles indicibles conduisent à des énoncés indéfinis, c’est à dire des énoncés pour lesquels on ne sait pas vraiment donner un sens à l’affirmation de leur vérité ou de leur fausseté.
Tous les ensembles indicibles sont indéfinis, pour les raisons suivantes.
Pour donner un sens à une affirmation d’existence d’un élément d’un ensemble E, il faut une théorie. Par définition des ensembles indicibles, ceux-ci ne peuvent pas être complètement définis à l’intérieur d’une théorie. Comment savoir alors si une affirmation d’inexistence est vraie ? Si un être n’existe pas dans une théorie, il pourrait exister dans une autre. La seule façon de prouver de telles affirmations d’inexistence consiste à prouver que l’existence conduirait à une contradiction. Mais la présence d’une contradiction dans une théorie dépend de tous les axiomes qui la définissent. L’existence de l’ensemble de tous les ensembles par exemple conduit à une contradiction dans la théorie ZFC mais pas dans la théorie du zig-zag interdit. La vérité des énoncés d’existence sur le contenu des ensembles indicibles ne peut donc pas être définie d’une façon non-équivoque. Elle dépend d’une part d’arbitraire dans le choix des axiomes.
L’hypothèse du continu, “le plus petit nombre ordinal infini dont le cardinal est plus grand que celui du premier ordinal infini, est le nombre des nombres réels”, est l’un des plus célèbres de ces énoncés indéfinis. Sa vérité est problèmatique. Le problème n’est pas seulement qu’on ne sait pas s’il est vrai ou faux mais surtout qu’on ne sait pas bien quel sens donner à l’affirmation de sa vérité ou de sa fausseté.
L’ensemble PC(O) de tous les ordinaux inférieurs à un ordinal donné O et dont le cardinal est plus grand que celui du premier ordinal infini, est un ensemble indéfini, parce que la vérité des énoncés d’appartenance à PC(O) n’est pas définie de façon univoque. Il restera indéfini tant qu’on ne saura pas comment définir sa vérité avec fiabilité et précision.
[modifier] Les ensembles décidables et énumérables
On doit principalement à Türing l’approche de l’incomplétude que nous allons maintenant présenter. Elle permet de poser le problème de la prouvabilité dans toute sa généralité. Elle repose principalement sur la définition des ensembles énumérables.
Türing a conçu une machine idéale pour apporter une réponse précise et bien définie à la question, qu’est-ce qui est vraiment calculable ? Les ordinateurs ont été inventés ensuite. Ils sont une réalisation concrète de l’idée de Türing. La décidabilité et l’énumérabilité sont deux façons de préciser ce qu’on entend par la calculabilité.
Les ensembles décidables sont énumérables mais l’inverse n’est pas toujours vrai. Les différences entre ces ensembles viennent de la nature du critère d’après lequel on peut savoir quels éléments ils contiennent et ne contiennent pas. Si ce critère est efficace à la fois pour les affirmations et pour les négations, alors l’ensemble est décidable. Si ce critère est efficace seulement pour les affirmations alors l’ensemble est énumérable.
Il y a plusieurs façons équivalentes de donner une définition précise à cette notion d’efficacité des procédures de décision. Les découvertes de Herbrand, Gödel, Church, Post, Türing, et de beaucoup d’autres ont conduit à de telles définitions. La définition proposée par Türing sera présentée ici parce qu’elle est la plus facile à comprendre maintenant qu’aujourd’hui tout le monde ou presque connaît l’existence des ordinateurs. Dans le chapitre suivant, nous présenterons une autre définition, équivalente, inspirée des travaux de Post et de la thèse de doctorat de Smullyan, parce qu’elle est mieux adaptée à la méthode axiomatique.
Selon Türing, un ensemble E d’expressions formelles est décidable lorsqu’on peut programmer un ordinateur de telle façon que pour toute expression formelle x, la machine puisse répondre si oui ou non E contient x.
Si un ensemble est fini et si on connaît la liste de ses éléments alors il est décidable. Certains ensembles infinis sont également décidables, par exemple (l’ensemble de toutes les égalités x à la puissance y = z où x, y et z sont des entiers) est décidable. Il suffit de programmer un ordinateur pour qu’il calcule x à la puissance y et qu’il compare le résultat avec z.
On pense en général que les capacités de calcul d’un ordinateur sont limitées, à cause de la finitude de sa mémoire. Pour donner à sa définition toute la généralité de l’infini mathématique, Türing avait inventé le concept d’une machine dotée d’une mémoire infinie : un ruban de papier d’une longueur en principe illimitée. Le concept de Türing est à l’origine de l’invention des ordinateurs. On peut aussi considérer que leur mémoire est infinie, parce qu’on peut les connecter à des banques de données, dont la taille peut être augmentée indéfiniment. Avec une telle extension de mémoire, les ordinateurs peuvent faire tout ce que peuvent faire les machines idéales de Türing.
Un ensemble E est énumérable lorsqu’on peut programmer un ordinateur pour qu’il soit toujours capable de répondre oui si on lui présente le nom d’un élément de E et qu’il ne réponde jamais oui si on lui présente le nom d’un être qui n’est pas dans E. Mais dans ce dernier cas on n’exige pas que l’ordinateur réponde non. Il suffit qu’il ne réponde pas, il peut continuer à tourner indéfiniment sans jamais fournir de réponse.
On peut définir la décidabilité à partir de l’énumérabilité en disant qu’un ensemble est décidable si et seulement si lui-même et son complémentaire (dans l’ensemble de toutes les expressions formelles composées des mêmes symboles) sont énumérables.
Lorsqu’un ensemble est énumérable, on peut prouver pour tous ses éléments qu’il les contient. Les preuves consistent simplement à mettre en route la machine et à attendre qu’elle apporte les réponses souhaitées. Mais on ne sait pas a priori comment prouver qu’il ne contient pas certains éléments. Un simple mortel ne peut pas attendre une éternité. Si la machine continue à tourner, il ne sait pas a priori si elle va s’arrêter un jour et fournir un résultat ou si elle ne s’arrêtera jamais.
Une autre définition de l’énumérabilité consiste à dire qu’un ensemble est énumérable lorsqu’on peut programmer un ordinateur pour qu’il énumère, qu’il écrive par exemple, les noms de tous ses éléments. Si l’ensemble est infini, la machine ne s’arrête jamais, et consomme une quantité illimitée de papier.
Pour montrer que cette énumérabilité, appelons la liste-énumérabilité, est équivalente à la définition précédente, la oui-énumérabilité, il faut remarquer qu’on peut toujours programmer un ordinateur en mode multi-tâche. Plus précisément, on lui prescrit un temps de travail unitaire, disons 1 million d’opérations, et on lui prescrit d’examiner un ensemble infini de questions, en consacrant à chaque question un temps de travail unitaire. S’il ne trouve pas la réponse pendant ce temps limité, il conserve la question en mémoire et passe à la question suivante. On peut programmer un cheminement dans l’ensemble des questions tel que l’ordinateur revienne toujours aux questions auxquelles il n’a pas trouvé de réponses sans jamais cesser d’examiner de nouvelles questions et tel qu’il arrive ainsi à trouver les réponses à toutes les questions, en nombre infini, qui ont effectivement une réponse. Cela montre qu’un ensemble oui-énumérable est aussi liste-énumérable. La réciproque n’est pas difficile à prouver.
Une théorie axiomatique est toujours énumérable, pour les raisons suivantes. La liste, finie ou infinie, de ses axiomes, est toujours décidable, parce qu’on veut savoir précisément ce qui est et ce qui n’est pas un axiome. Les méthodes formelles imposent que les règles de déduction aient un caractère mécanique, qu’elles puissent être appliquées aveuglément par une machine. L’ensemble des preuves formelles est donc toujours décidable. Si on présente une preuve formalisée à un ordinateur convenablement programmé, il répond si oui ou non la preuve est correcte, si oui ou non elle commence par des axiomes et respecte les règles de déduction. La théorie, c’est à dire l’ensemble des théorèmes, ou formules prouvables à partir des axiomes, est énumérable, parce qu’on peut définir un ordre sur l’ensemble de toutes les listes finies de formules. Soit une formule F dont on veut savoir si elle est un théorème. L’ordinateur examine chaque liste finie de formules une par une et décide si oui ou non elle est une preuve formelle. Si oui, alors la dernière formule de la liste est un théorème. Si cette formule est F alors l’ordinateur s’arrête et répond que F est un théorème. Dans les autres cas, l’ordinateur examine la liste finie suivante. Si F est vraiment un théorème, un ordinateur ainsi programmé trouvera toujours la réponse, parce qu’il examine toutes les preuves formelles possibles. Mais il mettra beaucoup de temps, beaucoup trop pour que cette méthode soit réellement efficace pour nous simples mortels. Si F n’est pas un théorème, l’ordinateur ne s’arrête jamais, il examine sans arrêt de nouvelles listes, il trouve de nouvelles preuves, mais il ne trouvera jamais de preuve de F, puisque F n’est pas un théorème. Une théorie axiomatique est donc toujours énumérable mais il n’est pas sûr a priori qu’elle soit décidable.
Avant que la notion de décidabilité soit précisément définie, Hilbert avait espéré que l’on pourrait définir l’ensemble de toutes les vérités mathématiques comme un ensemble décidable. Gödel et ses successeurs ont montré qu’il existe des ensembles indécidables et que toutes les théories mathématiques suffisamment riches sont indécidables. Les ensembles décidables sont importants mais ils ne sont pas suffisants pour définir des théories suffisamment riches. Celles-ci sont des ensembles énumérables mais indécidables.
[modifier] Le théorème fondamental de l’indécidabilité et le problème de Türing
Le théorème fondamental de l’indécidabilité établit l’existence d’au moins un ensemble indécidable.
A partir de l’existence d’un ensemble indécidable on ne peut pas conclure qu’il y a des problèmes mathématiques bien définis et néanmoins insolubles, mais seulement qu’il n’existe pas de méthode unique et bien définie pour répondre à toutes les questions, en nombre infini, qui portent sur certains ensembles bien définis.
Tous les théorèmes sur l’incomplétude de la prouvabilité axiomatique peuvent être considérés comme des corollaires des théorèmes d’existence d’ensembles indécidables. Le raisonnement est le suivant. Une théorie axiomatique T est toujours énumérable. Si elle est suffisamment riche, elle permet de définir un ensemble indécidable Indécid et son complémentaire C-Indécid. Si T était complète, elle contiendrait toutes les vérités sur C-Indécid. Comme T est énumérable, C-Indécid serait alors lui aussi énumérable. Mais C-Indécid n’est pas énumérable, parce que Indécid est indécidable. Il faut alors conclure que T est incomplète.
La présente section expose la preuve de Türing du théorème fondamental de l’indécidabilité. Cette preuve sera informelle. Pour une preuve complète, il faudrait préciser la notion de machine idéale de Türing, et prouver l’existence d’une machine de Türing universelle, ou ordinateur. Cette partie de la preuve n’est pas exposée ici parce que l’existence des ordinateurs est désormais couramment acceptée.
Il est possible de définir un ensemble énumérable Enum, et même décidable, de tous les noms des ensembles énumérables. On veut dire par là que l’on peut définir un formalisme dont le domaine d’objets est un ensemble EF d’expressions formelles, que Enum est une partie de EF, que toutes les parties énumérables de EF sont nommées par un élément de Enum, et que EF est suffisamment riche pour que tout ensemble énumérable concevable puisse être identifié à une partie énumérable de EF, par un processus simple de traduction. Il y a plusieurs façons de définir Enum. Nous présenterons celle de Türing.
Il est également possible de définir un ensemble VAEnum de toutes les vérités atomiques d’appartenance aux les ensembles énumérables. Le théorème fondamental de l’énumérabilité dit que VAEnum est énumérable. Autrement dit, l’ensemble de toutes les vérités atomiques d’appartenance aux ensembles énumérables est énumérable. Une vérité atomique d’appartenance sur les ensembles énumérables est une formule atomique vraie qui dit qu’une expression formelle appartient à l’ensemble énumérable nommé par une autre expression formelle. Nous montrerons plus loin que ce théorème est équivalent à celui de l’existence d’une machine de Türing universelle. Dans le chapitre suivant, nous donnerons une preuve de ce théorème à partir d’une autre définition de l’énumérabilité, équivalente à celle de Türing.
Le théorème fondamental de l’indécidabilité dit que VAEnum est indécidable. Autrement dit, l’ensemble de toutes les faussetés atomiques d’appartenance aux ensembles énumérables n’est pas énumérable. Appelons FAEnum cet ensemble. Une fausseté atomique d’appartenance est une formule atomique qui n’est pas vraie. A chaque fausseté atomique, on peut associer une formule vraie, qui dit qu’une expression formelle n’appartient pas à l’ensemble énumérable nommé par une autre expression formelle. Cette dernière formule n’est pas atomique mais presque parce qu’elle est la négation d’une formule atomique.
Nous allons d’abord présenter la méthode de Türing pour définir Enum. De cette méthode il résulte immédiatement que la vérité du théorème fondamental est équivalente à l’indécidabilité du problème de l’arrêt, ou problème de Türing. Il s’agit du problème de savoir par avance si oui ou non un ordinateur va s’arrêter et fournir un résultat. Türing a prouvé qu’on ne peut pas programmer un ordinateur pour savoir dans tous les cas si oui ou non un ordinateur va s’arrêter.
La méthode de Türing est facile à comprendre pour tous ceux qui savent programmer un ordinateur. Si on ignore les différences de capacité de mémoire et de temps de calcul, tous les ordinateurs sont équivalents, au sens où tout ce qui peut être fait par l’un peut aussi être fait par n’importe quel autre. En ce sens, les ordinateurs sont des calculateurs universels. On peut ignorer les différences de mémoire parce que celle-ci peut toujours être rallongée en connectant la machine à une banque de données. On peut ignorer les différences de temps de calcul dans la mesure où on s’intéresse seulement aux limites théoriques de la puissance des ordinateurs, comme si le fait d’attendre un résultat pendant des milliards d’années n’était pas un problème. Les ordinateurs sont équivalents parce qu’ils peuvent se représenter les uns les autres. On dit qu’une machine émule ou simule une autre machine. Türing a inventé la première technique de simulation d’une machine par une autre, avant même que les ordinateurs existent réellement.
Pour représenter une machine de Türing, il suffit de représenter son programme, c’est à dire la liste finie de toutes les règles qu’elle exécutera mécaniquement dès qu’elle aura été lancée.
Une machine de Türing peut être considéré comme une fonction qui à chaque état initial de la mémoire associe son état final, après que la machine se soit arrêtée. Le domaine de définition de cette fonction est l’ensemble de tous les états initiaux pour lesquels la machine s’arrête. Nous dirons que c’est aussi le domaine de définition de la machine. Un ensemble énumérable peut être représenté par une machine de Türing dont il est le domaine de définition. L’ensemble Enum est alors identifié à l’ensemble de tous les programmes, c’est à dire l’ensemble infini des listes finies d’instructions. Comme par définition de l’énumérabilité, un ensemble énumérable peut toujours être représenté par une machine de Türing, Enum ainsi défini est bien un ensemble de noms de tous les ensembles énumérables.
Dans une machine de Türing universelle U , la mémoire peut être divisée en deux parties, P et I . P sert à représenter le programme de la machine que l’on simule. Comme c’est une liste finie, P n’occupe qu’une partie finie de la mémoire totale. Le reste I sert à représenter l’état initial de la machine simulée. Après que U soit lancée, U s’arrête si et seulement si la machine représentée dans P s’arrête lorsque son état initial est celui représenté dans I. (Si U s’arrête le résultat que U fournit dans la partie I de sa mémoire représente le résultat fourni par la machine simulée par U .)
L’existence d’une machine universelle U montre que VAEnum est énumérable. Les énoncés atomiques sont représentés par les états initiaux de la mémoire de U. Un état initial représente l’énoncé que l’expression formelle représentée dans I appartient à l’ensemble énumérable représenté dans P. Les énoncés sont vrais lorsque U s’arrête, faux sinon.
Le théorème d’existence d’une machine universelle est donc équivalent au théorème fondamental de l’énumérabilité. Une machine universelle peut être conçue comme une sorte de diseur de vérités.
Par définition de la décidabilité, le problème de l’arrêt serait décidable si deux ensembles étaient énumérables, celui des couples (programme, état initial) pour lesquels une machine universelle s’arrête et celui des couples (programme, état initial) pour lesquels une machine universelle ne s’arrête pas. L’énumérabilité du premier est une conséquence directe de l’existence d’une machine universelle. Mais le théorème fondamental de l’indécidabilité affirme que le second ensemble n’est pas énumérable, qu’il ne peut pas exister de machine NegU qui représenterait FAEnum. Il est donc équivalent à l’indécidabilité du problème de l’arrêt.
Montrons que le paradoxe du menteur conduit à l’indécidabilité de VAEnum.
Si VAEnum était décidable, la machine NegU qui représente FAEnum existerait. On pourrait alors s’en servir pour construire une autre machine AT qui aurait la propriété suivante. AT s’arrête si et seulement si (l’ état initial de la mémoire de AT représente une machine M, par son programme, et M ne s’arrête pas lorsque son état initial représente la machine M elle-même). AT serait représentée par un programme PrAT. Türing a montré qu’il serait très facile d’écrire le programme PrAT si on avait le programme PrNegU de l’hypothétique NegU.
Supposons que l’état initial de la mémoire de AT soit chargée avec PrAT. Est-ce que AT va s’arrêter ? AT s’arrête si et seulement si (l’ état initial de la mémoire de AT représente une machine M, par son programme, et M ne s’arrête pas lorsque son état initial représente la machine M elle-même). Dans ce cas, la machine M est AT. On en conclut que, lorsque son état initial représente AT, AT s’arrête si et seulement si AT ne s’arrête pas. C’est une contradiction. L’hypothèse de l’existence de AT doit donc être rejetée, et par voie de conséquence l’existence de NegU aussi. Le problème de l’arrêt n’est donc pas décidable et FAEnum n’est pas énumérable. Autrement dit, VAEnum est indécidable.
En s’arrêtant après avoir été initialisé avec PrAT, la machine AT, conçue comme un diseur de vérités, dirait d’elle-même qu’elle ne s’arrête pas après avoir été initialisé avec PrAT. Il s’agit donc bien du paradoxe du menteur.
Le problème de l’arrêt est un problème concret, c’est un problème qui se pose quand on développe des programmes, ou logiciels. La preuve de son indécidabilité est donc une application concrète du paradoxe du menteur. Les paradoxes sont parfois considérés à tort comme des obstacles à l’avancement des sciences. C’est tout le contraire qui est vrai. Les paradoxes sont de très puissants moteurs pour la science.
[modifier] Où sont les axiomes manquants ?
Les théorèmes fondamentaux de l’énumérabilité et de l’indécidabilité permettent ensemble de montrer que toute théorie mathématique suffisamment riche n’est jamais capable de prouver toutes ses vérités. Il suffit de définir suffisamment riche par les conditions suivantes.
a) la théorie T permet de définir tous les ensembles énumérables
b) à partir de deux ensembles déjà définis E et F, T permet de définir E Moins F, l’ensemble différence de E et F, c’est à dire la partie de E qui ne contient aucun élément de F.
Si E est l’ensemble de toutes les expressions formelles et F un ensemble indécidable alors E Moins F n’est pas énumérable. Comme l’ensemble des formules prouvables de T est énumérable, il y a des vérités d’appartenance à l’ensemble non-énumérable E Moins F qui ne sont pas prouvables.
On peut voir ce théorème comme une généralisation du premier théorème d’incomplétude de Gödel. Les conditions a et b sont remplies par l’arithmétique formelle mais la preuve est un peu difficile et ne sera pas présentée ici.
Si on ne peut pas prouver toutes les vérités, c’est qu’il manque des axiomes. Quels sont-ils ?
Jusqu’ici on a seulement prouvé que des théories sont incomplètes mais on n’a pas dit pourquoi. Il semble également assez mystérieux que ces théories résistent toujours aux tentatives de complétude. Quelle que soit la façon dont on les complète avec de nouveaux axiomes elles restent incomplètes. Même si on se donne des axiomes en nombre infini elles restent incomplètes, dès que ces axiomes sont déterminés par des règles explicites et univoques. Qu’est-ce qui manque ? Qu’est-ce qui rend la complétude inaccessible à nos esprits finis ?
Il semble intuitivement assez évident que les incomplétudes de la prouvabilité axiomatique et de l’ontologie sont étroitement liées. La ressemblance entre les façons dont tous tous ces théorèmes d’incomplétude sont prouvés, dont l’ensemble paradoxal BR de Bertrand Russell, le nombre réel GC de Georg Cantor, les nombre entiers AT d’Alfred Tarski et KG de Kurt Gödel, et la machine AT d’Alan Türing, sont construits montrent que dans tous les cas il y a une ressemblance, ne serait-ce que formelle mais parfois très explicite, avec le paradoxe du menteur.
Le chapitre 6 prouvera ce qui suit, qui peut être considéré comme presqu’évident.
L’incomplétude mathématique est essentiellement ontologique. Les théories axiomatiques ne permettent jamais de prouver toutes leurs vérités parce que leur ontologie est toujours limitée. Elles n’ont jamais assez d’axiomes d’existence. Elles ne permettent jamais de définir assez d’ensembles, de prédicats ou de concepts pour formaliser toutes les preuves concevables. On ne peut pas donner un nombre fini de règles qui suffise pour établir l’existence de tous les êtres imaginables, c’est à dire tous les êtres qui ont le droit d’exister au yeux des mathématiciens. L’imagination déborde tous les cadres.
