Mode d'emploi de la raison/Les théories indécidables
Un dispositif d'observation du savoir ne peut pas être universel, infaillible et répondre à toutes les questions qui exigent une réponse par oui ou non. Si un tel dispositif existait, on pourrait lui demander "vas-tu répondre non à la présente question ?" Il ne peut donner qu'une réponse fausse.
Une théorie du savoir peut être universelle et infaillible. La logique du premier ordre est une telle théorie. Mais une théorie du savoir universelle et infaillible ne peut pas répondre à toutes les questions qui se posent à propos d'elle-même. C'est une conséquence d'un théorème de Tarski : une théorie vraie ne peut pas contenir un prédicat universel de vérité pour elle-même.
La preuve du théorème de Tarski est par l'absurde : supposons que T est une théorie vraie telle que tous les énoncés de T sont dans le domaine de variation des variables de T et que est vrai est un prédicat universel de vérité qu'on peut définir dans T. Pour un énoncé de T à une variable libre A(x), on peut se demander s'il est vrai ou non de lui-même. Par exemple, x est un énoncé est vrai de lui-même, puisque x est un énoncé est un énoncé. x n'est pas un énoncé n'est pas vrai de lui-même, puisque x n'est pas un énoncé est un énoncé. Si un prédicat universel de vérité est vrai peut être défini dans T, un énoncé A(x) équivalent à x n'est pas vrai de lui-même peut être défini dans T. Est-il vrai de lui-même ? A(A(x)) est-il vrai ? Il résulte de la définition de A(x) qu'il est vrai de lui-même si et seulement s'il n'est pas vrai de lui-même. Cela conduit à une contradiction : A(A(x)) et non A(A(x)) est un théorème de T mais est faux. L'hypothèse initiale de l'existence d'une théorie T vraie dans laquelle on peut définir un prédicat universel de vérité pour elle même est donc fausse.
Quand on se sert de la logique du premier ordre pour raisonner sur la vérité de la logique du premier ordre, on se sert d'un prédicat de vérité qui n'est pas universel. Le domaine des énoncés auxquels il peut être attribué est un domaine limité, il n'est pas le domaine de tous les énoncés de la théorie dont on se sert pour raisonner.
Une théorie du savoir peut être universelle en étant une théorie de tous les savoirs, mais jamais en étant tout le savoir sur tous les savoirs. L'omniscience n'est pas à notre portée.
Une théorie vraie ne peut pas prouver qu'elle est vraie parce qu'elle ne peut pas l'énoncer, parce qu'elle ne contient pas de prédicat de vérité pour tous ses énoncés. Mais la vérité d'une théorie vraie T peut être prouvée dans une théorie T+, plus puissante que T, qui contient un prédicat de vérité pour T : x est un énoncé vrai défini avec les concepts de T. Si T+ est vraie x est un énoncé vrai défini avec les concepts de T+ ne peut pas être un prédicat de T+ mais seulement d'une théorie plus puissante T++, et ainsi de suite.
Un modèle M d'une théorie T est un ensemble de faits atomiques définis avec les concepts fondamentaux de T pour lequel tous les axiomes de T sont vrais. Tous les théorèmes de T sont également vrais pour le modèle M. Une théorie vraie ne permet jamais de prouver l'existence d'un modèle d'elle-même. Si elle le faisait elle aurait un prédicat de vérité pour elle même : x est vrai pour le modèle et d'après de le théorème de Tarski elle serait fausse. Le théorème de complétude de la logique du premier ordre affirme qu'une théorie cohérente a toujours un modèle. Si une théorie permet de prouver sa propre cohérence et si elle permet de prouver l'existence d'un modèle pour toute théorie cohérente alors elle est fausse. Gödel a prouvé qu'on peut se passer de la deuxième condition : une théorie vraie ne permet jamais de prouver sa propre cohérence. C'est le deuxième théorème d'incomplétude de Gödel.
Si une théorie T est assez puissante pour être une théorie des nombres naturels, on peut toujours définir dans T un prédicat universel de prouvabilité. x peut être prouvé dans T peut être défini dans T en numérotant les formules de T ou en les nommant d'une façon ou d'une autre, parce que l'ensemble des théorèmes d'une théorie est toujours récursivement énumérable. Or un prédicat universel de vérité dans T ne peut pas être défini dans T si elle est vraie. Donc le prédicat universel de prouvabilité dans T n'est pas un prédicat universel de vérité dans T. On obtient ainsi à partir du théorème de Tarski le premier théorème d'incomplétude de Gödel (les deux théorèmes ont été découverts indépendamment en 1931) : une théorie vraie et assez puissante pour être une théorie des nombres naturels permet toujours d'énoncer des vérités qu'elle ne peut pas prouver. Mais on aurait tort d'en conclure qu'il y a des vérités qu'on ne peut absolument pas prouver, parce qu'une vérité qu'une théorie T ne permet pas de prouver peut être prouvée dans une théorie T+ plus puissante que T. T+ à son tour permet d'énoncer des vérités qu'elle ne peut pas prouver.
La preuve du premier théorème d'incomplétude de Gödel est semblable à celle de Tarski. A partir du prédicat x peut être prouvé dans T on peut définir dans T un prédicat G(x) équivalent à que x est vrai de lui-même ne peut pas être prouvé dans T. Peut-on prouver dans T G(G(x)) ? Par définition de G(x), G(G(x)) est vrai si et seulement s'il ne peut pas être prouvé dans T. S'il pouvait être prouvé dans T alors il serait faux. Si T est vraie, tous les énoncés qui peuvent être prouvés dans T sont vrais, donc G(G(x)) ne peut pas être prouvé dans T. Donc il est vrai. On prouve ainsi que G(G(x)) est vrai et ne peut pas être prouvé dans T sous l'hypothèse que T est vraie.
La preuve de Gödel de G(G(x)) peut être énoncée dans une théorie T+ qui contient le prédicat : x est un énoncé vrai défini avec les concepts de T. T+ peut prouver la vérité de T, mais pas la vérité de T+. La preuve de G(G(x)) ne peut pas être énoncée dans la théorie T, parce que T ne peut pas prouver la vérité de T.
Les théorèmes de Gödel et de Tarski prouvent que l'omniscience n'est pas à notre portée, parce qu'aucune théorie ne suffit pour prouver toutes les vérités. Mais si on en conclut qu'il y a des vérités qu'aucune théorie ne peut prouver, on commet une faute de logique. pour toute théorie T, il existe une vérité V telle que V ne peut pas être prouvée dans T n'est pas équivalent à il existe une vérité V telle que pour toute théorie T, V ne peut pas être prouvée dans T, parce que pour tout x il existe un y tel que n'est pas équivalent à il existe un y tel que pour tout x. Personne ne peut connaître toutes les vérités n'implique pas qu'il y a des vérités que personne ne peut connaître.
Prouver que l'ensemble des théorèmes d'une théorie est récursivement énumérable est la partie laborieuse de la preuve donnée par Gödel. C'est laborieux mais c'est évident. L'énumérabilité récursive de l'ensemble des théorèmes est une conséquence du principe qu'une preuve peut toujours être reconnue comme une preuve :
Un ensemble E est récursivement énumérable si et seulement s'il peut exister un dispositif d'observation infaillible qui répond toujours oui quand on lui demande si un élément de E est élément de E.
Un ensemble E est décidable si et seulement s'il peut exister un dispositif d'observation infaillible qui répond toujours oui quand on lui demande si un élément de E est élément de E et toujours non quand on lui demande si un être qui n'est pas élément de E est élément de E.
Un ensemble est décidable si et seulement si lui-même et son complémentaire sont récursivement énumérables.
Si un ensemble récursivement énumérable est un ensemble de nombres naturels, on considère son complémentaire dans l'ensemble de tous les nombres naturels pour savoir s'il est décidable. S'il est un ensemble d'énoncés, on considère son complémentaire dans l'ensemble de tous les énoncés formulés avec les mêmes lettres.
L'ensemble de toutes les preuves dans une théorie est décidable, parce qu'une preuve peut toujours être reconnue comme une preuve.
Un théorème d'une théorie est la conclusion d'une preuve dans cette théorie. L'ensemble de tous les théorèmes d'une théorie est toujours récursivement énumérable, parce que l'ensemble de toutes les preuves dans une théorie est décidable. Il suffit de faire un dispositif d'observation qui observe toutes les suites d'énoncés de la théorie pour décider si elles sont des preuves, en commençant par les suites d'énoncés les plus courtes. Un tel dispositif d'observation finit toujours par trouver une preuve s'il en existe au moins une, mais s'il n'existe pas de preuve, il continue éternellement à chercher une preuve qui n'existe pas, il ne répond jamais, il n'est pas capable de répondre qu'il n'existe pas de preuve.
Si une théorie vraie est assez puissante pour être une théorie des nombres naturels, alors l'ensemble de tous ses théorèmes n'est pas décidable. La théorie est indécidable. On peut le prouver à partir de la preuve du premier théorème d'incomplétude de Gödel. Si une théorie T est décidable et si elle est assez puissante pour être une théorie des nombres naturels alors tous les énoncés vrais qui affirment qu'un énoncé ne peut pas être prouvé dans T peuvent être prouvés dans T, parce que l'ensemble des énoncés qui ne peuvent pas être prouvés dans T est récursivement énumérable. Mais alors l'énoncé G(G(x)) pourrait être prouvé dans T alors qu'il est faux. Donc T ne peut pas être vraie. Une théorie décidable et assez puissante pour être une théorie des nombres naturels est donc toujours fausse.
Il suffit de raisonner sur tous les noms formés avec une seule lettre : I, II, III, ... pour raisonner sur tous les nombres naturels. Une théorie vraie est donc toujours indécidable si elle donne les moyens de raisonner sur les vérités les plus élémentaires.
Il faut distinguer deux concepts d'indécidabilité : l'indécidabilité d'une théorie et l'indécidabilité d'un énoncé dans une théorie. Un énoncé est indécidable dans une théorie si et seulement si ni lui-même ni sa négation ne peuvent être prouvés dans cette théorie. Une théorie est indécidable si et seulement si l'ensemble de tous ses théorèmes n'est pas décidable.
Si tous les énoncés qu'on peut formuler avec les concepts d'une théorie sont décidables dans la théorie alors la théorie est décidable, parce qu'on peut toujours prouver qu'un énoncé n'est pas un théorème en prouvant que sa négation est un théorème. En revanche, si une théorie est décidable, il n'est pas toujours vrai que tous les énoncés qu'on peut formuler avec les concepts de la théorie sont toujours décidables dans cette théorie. Il suffit qu'on puisse toujours décider si oui ou non un énoncé est un théorème pour qu'une théorie soit décidable, il n'est pas nécessaire qu'un énoncé ou sa négation soit toujours un théorème.
Dans la preuve de Gödel, on prouve que G(G(x)) est vrai et indécidable dans la théorie T mais cela ne suffit pas pour prouver que T est indécidable. Pour cela, il faut prouver que l'ensemble des non-théorèmes (les énoncés qui ne peuvent pas être prouvés dans T) n'est pas récursivement énumérable. La théorie de l'énumérabilité récursive et de l'indécidabilité est présentée dans de nombreux livres. La thèse de doctorat de Smullyan, Theory of formal systems (1961), est une excellente présentation.