« N’EST SCIENTIFIQUE QUE CE QUI EST RERODUCTIBLE, OBSERVABLE ET MESURABLE »

Source : Wikipédia
Les théorèmes d'incomplétude de Gödel sont deux théorèmes célèbres de logique mathématique, prouvés par Kurt Gödel en 1931 dans son article Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme (Sur l'indécidabilité formelle des "Principia Mathematica" et des systèmes apparentés).

 

Sommaire
1 Enoncés des deux théorèmes
@ - 1.1 Les conditions d'application des théorèmeso
@ - 1.2 Conséquences immédiates du premier théorème d'incomplétude
@ - 1.3 Conséquences immédiates du second théorème d'incomplétude·
2 La relativité de l'indécidabilité des énoncés·
3 Des exemples de systèmes incomplets et d'indécidables·
4 La mise en cause du mouvement formaliste·
5 Le théorème d'incomplétude en philosophie·
6 Une preuve partielle du premier théorème d'incomplétude·
7 Argument de la preuve et discussion du second théorème d'incomplétude·
8 Sources·

Enoncés des deux théorèmes
Le premier théorème d'incomplétude peut être énoncé de la façon un peu approximative suivante.
Dans n'importe quelle théorie récursivement axiomatisable, cohérente et capable de "formaliser l'arithmétique", on peut construire un énoncé arithmétique qui ne peut être ni prouvée ni réfutée dans cette théorie.
De tels énoncés sont dits indécidables dans cette théorie. Toujours dans l'article de 1931, Gödel en déduit le second théorème d'incomplétude :
Si T est une théorie cohérente qui satisfait des hypothèses analogues, la cohérence de T, qui peut s'exprimer dans la théorie T, n'est pas démontrable dans T.
Ces deux théorèmes ont été prouvés pour l'arithmétique de Peano, et donc pour les théories plus fortes que celle-ci, en particulier les théories destinées à fonder les mathématiques, telles que la théorie des ensembles, ou les Principia Mathematica ...

Les conditions d'application des théorèmes
Pour fixer les idées, on considère dorénavant que les théories en question sont des théories du premier ordre de la logique classique, même si les théorèmes d'incomplétude restent valides, sous les mêmes conditions, par exemple en logique intuitionniste ou en passant à l'ordre supérieur.
· Par théorie récursivement axiomatisable, on entend que la théorie peut être axiomatisée de façon qu'il soit possible de reconnaître de façon purement mécanique les axiomes parmi les énoncés du langage de la théorie. C'est le cas évidemment des théories utilisées pour formaliser tout ou partie des mathématiques usuelles.
· Une théorie est cohérente si aucune contradiction ne peut être prouvée à partir de ses axiomes. On dit aussi qu'elle est consistante, ou non-contradictoire. Pour le premier théorème d'incomplétude, Gödel faisait une hypothèse de cohérence un peu plus forte. L'hypothèse de cohérence simple suffit de toute façon pour le second théorème, qui n'énonce que la non-démontrabilité de l'énoncé de cohérence. J. B. Rosser a donné en 1936 une démonstration du premier théorème d'incomplétude sous la simple hypothèse de cohérence.
· Une théorie permet de formaliser l'arithmétique si, d'une part il est possible de définir (en un sens qu'il faudrait préciser) les entiers (donnés par 0 et la fonction successeur), avec les opérations usuelles, au moins l'addition et la multiplication, et si d'autre part un certain nombre d'axiomes sur les entiers sont prouvables dans la théorie. Les axiomes de Peano conviennent, mais, pour le premier théorème d'incomplétude une théorie arithmétique beaucoup plus faible suffit (la récurrence n'est essentiellement pas utile). Pour le second il faut un minimum de récurrence.

Conséquences immédiates du premier théorème d'incomplétude
On peut reformuler le premier théorème d'incomplétude en disant que si une théorie T satisfait les hypothèses utiles, il existe un énoncé tel que chacune des deux théories obtenues l'une en ajoutant à T cet énoncé comme axiome, l'autre en ajoutant la négation de cet énoncé, sont cohérentes.
Étant donné un énoncé G, notons non G sa négation. On montre facilement qu'un énoncé G n'est pas démontrable dans T si et seulement si la théorie T + non G (la théorie T à laquelle on ajoute l'axiome non G) est cohérente. En effet, si G est démontrable dans T, T + non G est évidemment contradictoire, et, réciproquement, de T + non G est contradictoire, on déduit que G est conséquence de T (c'est le raisonnement par l'absurde). Il est donc équivalent de dire qu'un énoncé G est indécidable dans une théorie cohérente T, et de dire que les deux théories T + non G et T + G sont cohérentes. L'énoncé G n'étant évidemment pas indécidable dans chacune de ces deux théories, on voit que la notion d'énoncé indécidable est par nature relative à une théorie donnée.
Ainsi, si G est l'énoncé indécidable donné par le premier théorème d'incomplétude pour T, on aura, en appliquant à nouveau ce théorème, un nouvel énoncé indécidable dans la théorie T + G (et donc d'ailleurs indécidable aussi dans la théorie T).
De fait, quand le théorème d'incomplétude s'applique à une théorie T, il s'applique à toutes les extensions cohérentes de cette théorie, tant qu'elles restent récursivement axiomatisables. Il n'y a aucun moyen effectif de compléter une telle théorie. Il faut également noter que, quelquesoit la théorie en jeu, l'énoncé obtenu est arithmétique, c'est à dire qu'on peut l'exprimer dans le langage de l'arithmétique. Il s'agit même d'un énoncé de l'arithmétique logiquement assez simple (en un sens précis). Par exemple on obtiendra par le théorème de Gödel un énoncé arithmétique qui sera indécidable dans la théorie des ensembles de Zermelo-Fraenkel.

Conséquences immédiates du second théorème d'incomplétude
Il peut être utile pour comprendre l'énoncé du second théorème d'incomplétude, de le reformuler par contraposée : Si T est une théorie récursivement axiomatisable qui permet de formaliser "suffisament d'arithmétique", et si T prouve un énoncé exprimant qu'elle est cohérente, alors T est contradictoire. Par contre une théorie qui démontre un énoncé exprimant qu'elle n'est pas cohérente, peut très bien ne pas être contradictoire, comme on le déduit du second théorème d'incomplétude lui-même ! Esquissons la preuve. Appelons coh(T) un énoncé qui exprime la cohérence de T dans la théorie T. D'après ce qui précède, le second théorème d'incomplétude affirme que, sous les hypothèses utiles sur T, si la théorie T est cohérente, la théorie T'=T + non coh(T) est encore cohérente. Rappelons que " T n'est pas cohérente ", signifie qu'il existe une preuve d'une contradiction dans T. Une preuve dans T est aussi une preuve dans T' , qui a juste un axiome supplémentaire. Il est donc simple de montrer dans une théorie telle que T, qui satisfait les hypothèses du théorème de Gödel, que non coh(T) a pour conséquence non coh(T'). On a donc déduit du second théorème de complétude, et de l'existence d'une théorie cohérente T qui satisfait les hypothèses de ce théorème -- prenons par exemple l'arithmétique de Peano -- l'existence d'une théorie T' cohérente qui démontre non coh(T'), à savoir un énoncé exprimant qu'elle n'est pas cohérente.
A contrario une théorie incohérente, dans laquelle tous les énoncés sont prouvables, démontrera évidemment un énoncé exprimant qu'elle est cohérente.
On voit par ces diverses remarques que le second théorème d'incomplétude ne dit rien en défaveur de la cohérence d'une théorie à laquelle il s'applique, par exemple la cohérence de l'arithmétique de Peano. Tout ce qu'il dit de cette dernière, c'est qu'elle ne peut se prouver que dans une théorie logiquement plus forte.

La relativité de l'indécidabilité des énoncés
Le théorème ne prétend pas pour autant l'existence d'indécidables « absolus », c'est-à-dire indémontrables dans n'importe quel système formel. En effet, il est toujours possible d'ajouter un axiome à un système formel dans le but de rendre un indécidable démontrable dans le nouveau système.
On pourrait penser « s'échapper » du théorème d'incomplétude en construisant un système formel où les indécidables seraient progressivement « résolus » avec de nouveaux axiomes. Mais le nouveau système ainsi créé remplirait encore les conditions des théorèmes de Gödel, pourvu que ses axiomes soient en un sens calculables (liste récursivement énumérable d'axiomes). Il comporterait alors lui aussi des indécidables, et serait donc toujours incomplet. Ainsi, le théorème de Goodstein est un énoncé arithmétique non prouvable dans l'axiomatique de Peano de l'arithmétique. Néanmoins, il est prouvable dans l'axiomatique de la théorie des ensembles de Zermelo-Fraenkel. Mais cette dernière théorie possède ses propres indécidables.
On peut directement déduire du second théorème que la démonstration de la cohérence de l'arithmétique en utilisant uniquement les axiomes de l'arithmétique, sans utiliser par exemple les axiomes de l'infini et les autres axiomes de la théorie des ensembles, comme l'avait suggéré David Hilbert, est impossible. Mais la cohérence de l'arithmétique peut tout de même être prouvée, de plusieurs façons.
Gerhard Gentzen a donné une preuve de consistance après avoir développé des méthodes d'analyse des théories définies par récurrence et en se fondant sur une induction transfinie jusqu'au petit ordinal dénombrable ε0. Cette preuve met à profit toute la puissance du raisonnement par récurrence mais elle raisonne toujours sur des ensembles « bien construits ». Sans utiliser les méthodes de Gentzen, qui ont été ensuite développées dans la théorie de la preuve, on peut donner une preuve naturelle, simple, élémentaire, de la cohérence des axiomes de l'arithmétique formelle en se servant de la théorie des modèles. Mais cette preuve ne peut pas être formalisée à l'intérieur de l'arithmétique formelle. Elle présuppose notre capacité à connaître les ensembles infinis définis par récurrence et la validité générale du principe d'induction complète. De tels présupposés reviennent à reconnaître la validité de certaines constructions ensemblistes élémentaires.
Cette preuve ne prouve donc pas la validité du principe d'induction complète puisqu'elle la présuppose, mais elle prouve que la forme qui lui est donnée dans l'arithmétique formelle est sans danger, qu'elle ne peut pas conduire à une contradiction. Elle est convaincante dans la mesure où on est déjà convaincu que les raisonnements sur certains ensembles infinis sont valides. On peut s'échapper des conditions du premier théorème d'incomplétude en adoptant comme axiomes toutes les vérités de l'arithmétique formelle. Mais un tel système d'axiomes, quoique très bien défini, ne peut pas être finiment axiomatisé, au sens où aucun système finiment axiomatisé ne lui est équivalent - finiment axiomatisé ne veut pas dire que le nombre des axiomes, c'est à dire les formules initiales des preuves, est fini, mais que les principes des axiomes sont en nombre fini : nombre fini de schémas d'axiomes, ou plus généralement, liste infinie et récursivement énumérable d'axiomes. Mais ce système est complet. On peut y prouver toutes les vérités puisqu'elles sont toutes des axiomes.

Des exemples de systèmes incomplets et d'indécidables
Qu'une théorie soit incomplète n'est a priori pas étonnant. Il suffit qu'elle ne contienne pas assez d'axiomes. Mais que l'arithmétique formelle et les Principia Mathematica soient incomplets était beaucoup plus étonnant. Dans le projet logiciste des auteurs des Principia, leur système devait contenir tous les axiomes dont on a besoin pour toutes les preuves mathématiques. Le problème de l'incomplétude s'était déjà posé à propos de la géométrie. Jusqu'aux travaux de Gauss, de Lobatchewsky, puis de Riemann, on pouvait croire que l'axiome des parallèles pourrait être prouvé à partir des autres axiomes de la géométrie euclidienne, qui définissent la géométrie absolue. En cherchant des preuves de cet axiome, certains se sont rendus compte que la négation de l'axiome des parallèles pouvait conduire à des résultats intéressants. Cela a conduit aux développements des géométries non-euclidiennes. Cela a montré que l'axiome des parallèles n'est pas déductible à partir des autres axiomes d'Euclide. Autrement dit, la géométrie absolue est incomplète. L'axiome des parallèles est pour elle un indécidable. On peut le prouver (Beltrami 1868) en donnant un modèle de la géométrie absolue (les droites sont les grands cercles d'une sphère, les points sont les couples de points diamétralement opposés sur la sphère) pour lequel tous les axiomes de la géométrie plane sont vrais, sauf l'axiome des parallèles.
Le théorème d'incomplétude donne une méthode mécanique pour créer des indécidables, si bien que les logiciens ont pu construire de nombreux indécidables. Mais ces énoncés sont créés « artificiellement » et ne répondent pas toujours à des interrogations réelles des mathématiciens.
Quand on se donne une théorie suffisamment riche en axiomes (l'arithmétique formelle ou une théorie des ensembles), 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. Mais ce jugement est erroné, on peut donner de nombreux exemples. Paul Cohen a prouvé qu’une conjecture de Cantor, l’hypothèse du continu, n’est pas prouvable à partir des axiomes de la théorie ZFC des ensembles. Cela seul suffit pour montrer que l’improuvabilité est une question qui se pose vraiment.
Mais elle se pose aussi pour des problèmes plus élémentaires. Nous allons voir qu'elle se pose à propos des équations diophantiennes par exemple.
On peut donner un sens absolu à la notion d'indécidabilité, non à propos des énoncés, mais des ensembles d'énoncés, ou problèmes. Un ensemble d'énoncés est indécidable s'il n'existe pas de théorie finiment axiomatisée qui permette de répondre pour tous les énoncés si oui ou non ils sont vrais. On ne prétend pas qu'il y a des énoncés dont la vérité ne peut pas être connue mais seulement qu'il n'existe pas de méthode unique et mécanisable qui suffise pour répondre à toutes les questions.
Les axiomes de l'arithmétique formelle, ou de toute autre théorie finiment axiomatisée, ne suffisent pas pour la résolution de toutes les équations diophantiennes (savoir si une équation algébrique à coefficients entiers a des solutions en nombres entiers et si non, le prouver). Le théorème de Matiyasevich dit que ce problème est indécidable. Les axiomes de l'arithmétique formelle suffisent pour trouver toutes les solutions, mais ils ne suffisent pas pour prouver pour toutes les équations qui n'ont pas de solutions qu'elles n'en ont pas. Autrement dit, il y a des formules arithmétiques composées d'une unique équation diophantienne, niée, et précédée de quantificateurs universels sur toutes ses variables, qui sont vraies mais qui ne sont pas prouvables à partir des axiomes.
Un exemple célèbre d'équation diophantienne est le théorème de Fermat-Wiles. On ne sait pas s'il est un énoncé indécidable de l'arithmétique formelle, ayant été prouvé par Andrew Wiles dans la théorie des ensembles.
Un autre exemple est les équations de Grégory Chaitin, qui ne possèdent pas moins de 12000 variables, et qui possèdent soit une infinité de solutions soit un nombre fini. Chaitin a montré que dans n'importe quel système formel on ne peut résoudre qu'un nombre fini de ces équations, les autres étant des indécidables du système en question.
D'autres exemples de problèmes indécidables sont donnés dans l'article indécidabilité.

La mise en cause du mouvement formaliste
Pour répondre aux problèmes de la crise des fondements des mathématiques, Hilbert et ses élèves avaient espéré que des méthodes formalistes apporteraient une réponse complète et définitive aux problèmes des fondements des mathématiques, en donnant une procédure mécanique, un algorithme, destiné à répondre à toutes les questions formelles (voir Fondation des mathématiques).
On peut déduire du premier théorème d'incomplétude de Gödel que ce programme de Hilbert n'est pas réalisable, du moins pas sous sa forme initiale. On connait cependant de nombreuses théories décidables. Elles ne suffisent pas pour toutes les mathématiques mais présentent parfois un grand intérêt. Tarski a donné un algorithme de décision pour la géométrie euclidienne élémentaire (la géométrie sans axiome sur la continuité de l'espace).

Le théorème d'incomplétude en philosophie
· Souvent cité en philosophie. Il faut pourtant faire très attention à son utilisation hors du champ des mathématiques, car l'utilisation du théorème d'incomplétude doit être basée sur un système formel. De plus, comme nous l'avons dit, des indécidables absolus n'existent pas, si bien que toute tentative de démontrer par exemple que l'existence de Dieu est un indécidable absolu serait vaine.
· Les théorèmes d'incomplétude montrent qu'il n'est pas possible de donner une liste finie et formalisée de tous les principes à partir desquels on peut développer une preuve mathématique. On peut toujours imaginer d'aller au-delà de ce qui est permis par les axiomes. Ces théorèmes montrent que l'imagination déborde tous les cadres. (voir incomplétude)
· On les interprète parfois comme des signes d'impuissance de la raison. Cette interprétation doit être prise avec précaution. Ces théorèmes manifestent la puissance de l'imagination et la capacité de la raison à reconnaître ses limites, à reconnaître son incapacité à enfermer l'imagination dans des limites fixées une fois pour toutes, comme un cheval dans un enclos trop petit. En outre ils ne mettent pas en doute la possibilité de connaître tous les principes logiques valides (voir théorème de complétude), si l'on limite la logique au calcul des prédicats du premier ordre.

Une preuve partielle du premier théorème d'incomplétude
La preuve du premier théorème d'incomplétude de Gödel est, comme celle du théorème d'incomplétude de Tarski, fondée sur le paradoxe du menteur.
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.
Gödel a alors inventé la notion de prédicat de prouvabilité. Un prédicat de prouvabilité pour une théorie T est 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.
Gödel a prouvé qu’une théorie mathématique T vraie et suffisamment riche remplit la condition suivante.
Pour toute théorie axiomatique récursivement axiomatisable T', il existe dans T un prédicat de prouvabilité pour 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. A l'époque actuelle, quiconque connait un peu d'informatique n'a aucun mal a imaginer que l'on puisse représenter les énoncés d'une théorie par des nombres. La difficulté réside dans les restrictions du langage : une théorie du premier ordre avec essentiellement l'addition et la multiplication comme symboles de fonction. C'est la difficulté que Gödel résout pour montrer l’existence d’un prédicat de prouvabilité.
A partir du théorème de Tarski et de l’existence d’un prédicat de prouvabilité on peut déduire une forme faible du premier théorème d’incomplétude de Gödel, restreint aux théories du premier ordre qui ont pour modèle les entiers usuels.
Tarski a utilisé une preuve analogue à celle de Gödel. Il suppose, en vue d'obtenir une contradiction, l'existence d’un prédicat de vérité, alors que Gödel utilise un prédicat de prouvabilité Px dont il a montré auparavant l’existence, ainsi que celle du prédicat de substitution SUBxyz. (voir théorème d'incomplétude de Tarski).
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.
Le nombre 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 s’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 la formule représentée par 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.
Si T est cohérente KG représente un énoncé indécidable de T. 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 Turing, les résultats de Gödel sur la prouvabilité s’inscrivent dans un contexte plus général, celui des ensembles énumérables. L’ensemble des théorèmes, ou formules prouvables, d’une théorie finiment axiomatisée est toujours énumérable.

Argument de la preuve et discussion du second théorème d'incomplétude
Le second théorème d’incomplétude de Gödel affirme que toute théorie mathématique cohérente et suffisamment riche ne peut pas prouver sa propre cohérence. Autrement dit, n’importe quelle technique théorique, qu’elle soit ensembliste ou autre, ne permet jamais de définir une théorie capable de prouver sa propre cohérence, dès lors qu’elle est suffisamment riche pour formaliser l’arithmétique formelle.
La preuve du second théorème est difficile à formaliser mais elle suit assez directement celle du premier.
Si une théorie pouvait prouver sa propre cohérence, c’est qu’elle contient un prédicat de prouvabilité P et le théorème, pour tout x, si x représente une contradiction alors non Px.
Gödel a montré que les théories qu'il étudie permettent de prouver · P(KG implique x), pour n’importe quelle contradiction représentée par x, ------- où (y implique z) est la représentation de la formule qui affirme que la formule représentée par y implique la formule représentée par z.
· si P(y implique z) alors (si Py alors Pz).
On en déduit que si (non Px) était prouvable pour une contradiction représentée par x, alors non P(KG) le serait aussi. Mais ce dernier énoncé équivaut à la formule représentée par KG et la théorie serait contradictoire.
Si la théorie est cohérente, non Px ne peut donc pas être prouvable, pour n’importe quelle contradiction représentée par x. Ces théories, si elles sont cohérentes, ne peuvent donc pas prouver leur propre cohérence.
Les interprétations courantes du second théorème d’incomplétude de Gödel exagèrent souvent sa portée. Gödel a prouvé qu’un certain type de preuve de cohérence ne peut pas exister. Mais il n’a jamais prouvé, ni prétendu avoir prouvé, que des preuves fiables de cohérence sont impossibles.
On propose parfois le raisonnement suivant : la cohérence d’un système X d’axiomes ne peut pas être prouvée avec X. Il faudrait donc un système X+ d’axiomes plus fort que X pour prouver la cohérence de X. Mais la cohérence de X+ serait encore plus douteuse que celle de X, puisqu’il est plus fort. Ce doute invaliderait la preuve. On en conclut parfois à tort que la cohérence des théories mathématiques suffisamment riches ne peut pas être prouvée.
Le raisonnement précédent n’est pas complètement dénué de vérité, parce que le problème de la fiabilité des principes se heurte aux difficultés de la régression à l’infini. À partir de quels principes peut-on prouver la validité des principes ?
Mais le raisonnement ci-dessus ne peut pas non plus être complètement vrai. La cohérence d’un système X d’axiomes est un problème mathématique bien défini. Ou bien il y a une conjonction d’axiomes de X dont la négation est une loi logique, dans ce cas X est incohérent, ou bien non, et X est cohérent. Dans la phrase précédente, toutes les notions (axiome de X, loi logique) peuvent être définies avec précision. Il s’agit donc d’un problème bien défini.
Il n'y a aucune raison valable qui nous permette de penser qu’un problème bien défini puisse être néanmoins insoluble. Les théorèmes sur l’incomplétude et l’indécidabilité portent seulement sur l’inexistence d’une méthode unique et bien définie pour répondre à toutes les questions bien définies.
S’il fallait admettre que la régression à l’infini rend insoluble le problème de la fiabilité des principes alors même les méthodes les plus élémentaires devraient être suspectées. On ne pourrait même pas être sûr que les opérations arithmétiques d’addition et de multiplication fournissent toujours un résultat bien défini. L’erreur dans le raisonnement ci-dessus consiste à admettre que la cohérence de X+ est plus douteuse que celle de X. Tant qu’on se limite à des théories élémentaires, on n’a en vérité pas de doutes sur la validité de nos principes de preuve.
Les doutes sur la fiabilité des principes et le problème de la régression à l’infini peuvent être résolus si l’on étudie attentivement la différence entre ce qui est élémentaire et ce qui ne l’est pas en mathématiques.

Sources
· Jean-Paul Delahaye, L'intelligence et le calcul - Belin pour la science, 2002 - ISBN 284245040X
· Jean-Marc Alliot, Thomas Schiex, Pascal Brisset, Frédérik Garcia, Intelligence artificielle & informatique théorique - Cepadues, 2002 - ISBN 2854285786
· Douglas Hofstadter, Gödel, Escher, Bach, les brins d'une guirlande éternelle - Dunod, 2000 - ISBN 210005435X
· Raymond Smullyan, Quel est le titre de ce livre ? - Dunod, 1993 - ISBN 210002003X
· Raymond Smullyan, Ca y est, je suis fou - Dunod, 1993 - ISBN 2100019635
· Raymond Smullyan, Les énigmes de Sheherazade - Flammarion, 1998 - ISBN 2080355643
· Raymond Smullyan, Les théorèmes d'incomplétude de Gödel - Dunod, 2000 - ISBN 210005287X, Theory of formal systems
· William Poundstone, Les labyrinthes de la raison - Belfond, 1998 - ISBN 2714425666
· Kurt Gödel, Collected works vol 1
· Martin Davis (éd) The undecidable (recueil des principaux articles de Gödel, Church, Turing, Rosser, Kleene, Post)
· Yann Ollivier, Le théorème de Gödel et ses non-interprétations