Le théorème de GÖDEL

mardi 18 mai 2010
par  Lydia COESSENS

1931

Théorème de Gödel par Kurt Gödel

Extrait de « Le théorème de Gödel »

Sur les propositions formellement indécidables...
Note ajoutée le 28 août 1963
* * *

Sur les propositions formellement indécidables des Principia Mathematica et des systèmes apparentés I [1] [2]
Le développement des mathématiques vers plus d’exactitude a conduit, comme nous le savons, à en formaliser de larges secteurs, de telle sorte que la démonstration puisse s’y effectuer uniquement au moyen de quelques règles mécaniques. Les systèmes formels les plus complets établis jusqu’à ce jour sont, d’un côté, le système des Principia Mathematica (PM) [3] et, de l’autre, le système axiomatique de la théorie des ensembles établi par Zermelo-Fraenkel [4] (et développé par J. von Neumann). Ces deux systèmes sont tellement larges que toutes les méthodes de démonstration utilisées aujourd’hui en mathématiques y sont formalisées, c’est-à-dire ramenées à quelques axiomes et règles d’inférence [5]. On pourrait par conséquent supposer que ces axiomes et règles d’inférence suffisent pour décider de toute question mathématique qui pourrait s’exprimer formellement dans ces systèmes. Dans ce qui suit, nous montrerons que tel n’est pas le cas et qu’il existe au contraire dans ces deux systèmes des problèmes relativement simples concernant la théorie des entiers que l’on ne saurait trancher sur la base de ces axiomes [6]. Cette situation n’est pas due, comme on pourrait le croire, à la nature spécifique des systèmes établis mais touche une très large classe de systèmes formels, à laquelle appartiennent en particulier tous les systèmes qui résultent des deux systèmes cités plus haut par addition d’un nombre fini d’axiomes [7], pourvu que, par ces axiomes, aucune proposition fausse du type spécifié dans la note (1) [voir plus bas] ne devienne démontrable.

Avant d’entrer dans le détail, esquissons tout d’abord l’idée directrice de la démonstration, sans prétendre encore bien entendu à l’exactitude. Les formules d’un système formel (nous nous limitons ici au système PM) se présentent comme des séries finies de signes élémentaires (variables, constantes logiques, parenthèses ou points finaux) et il est aisé de préciser exactement quelles séries de signes élémentaires sont des formules significatives et lesquelles n’en sont pas [8]. De manière analogue, les démonstrations ne sont, d’un point de vue formel, rien d’autre que des séries finies de formules (douées de certaines propriétés que l’on peut préciser). Naturellement, il est indifférent, pour des considérations métamathématiques, de choisir tel ou tel objet comme signe primitif et nous choisirons à cet effet les nombres naturels [9].

En conséquence, une formule est une suite finie de nombres naturels [10] et une figure de démonstration, une suite finie de suites finies de nombres naturels. Les concepts (ou propositions) métamathématiques deviennent ainsi des concepts (ou propositions) portant sur des nombres naturels ou des suites de nombres naturels [11] que l’on peut donc (du moins en partie) exprimer par les symboles du système PM lui-même. En particulier, on peut montrer que les concepts de « formule », de « figure de démonstration » et de « formule démontrable » peuvent être définis à l’intérieur du système PM, c’est-à-dire que l’on peut trouver par exemple une formule F(v) de PM avec une variable libre v (du type d’une suite de nombres) [12], telle que F(v), interprétée selon la signification des termes de PM, signifie : v est une formule démontrable. Nous allons maintenant construire une proposition indécidable du système PM, c’est-à-dire une proposition A pour laquelle on ne puisse démontrer ni A ni non-A, en procédant de la manière suivante : nous appellerons SIGNE DE CLASSE toute formule de PM contenant exactement une variable libre, cette variable étant du type des nombres naturels (classe de classe). Nous supposons que les signes de classe sont d’une certaine manière ordonnés en une suite [13], nous désignons le n-ième par R(n) et notons que le concept de signe de classe ainsi que la relation d’ordre R peuvent se définir dans le système PM. Soit α un signe de classe quelconque ; par [α ; n] nous désignons la formule qui résulte du signe de classe α lorsque l’on remplace la variable libre par le nombre naturel n. La relation ternaire x = [y ; z] apparaît comme étant également définissable dans PM. Maintenant, nous définissons une certaine classe K de nombres naturels de la manière suivante :

(1)

(où Dem x signifie : x est une formule démontrable) [14]. Puisque les concepts qui apparaissent dans le definiens [15] sont tous définissables dans PM, le concept K formé à partir d’eux l’est également, c’est-à-dire qu’il existe un signe de classe S [16] tel que la formule [s ; n], interprétée selon la signification des termes de PM, pose que le nombre naturel n appartient à K. S est, en tant que signe de classe, identique à un certain R(q), c’est-à-dire que nous avons,

S = R(q)

pour un certain nombre naturel q. Nous allons maintenant montrer que la proposition [R(q) ; q] [17] est indécidable dans PM. En effet, supposons que la proposition [R(q) ; q] soit démontrable, elle serait alors également vraie ; or dans ce cas, d’après ce qui précède, q appartiendrait à K c’est-à-dire d’après (1) que nous aurions [R(q) ; q], ce qui contredit l’hypothèse. Si au contraire la négation de [R(q) ; q] était démontrable, nous aurions alors q X K, c’est-à-dire Dem [R(q) ; q]. [R(q) ; q] serait donc démontrable en même temps que sa négation, ce qui à nouveau est impossible.

L’analogie qui existe entre ce raisonnement et l’antinomie de Richard [18] saute aux yeux ; il est également étroitement apparenté au « menteur » [19], puisque la proposition indécidable [R(q) ; q] affirme que q appartient à K, c’est-à-dire, d’après (1), que [R(q) ; q] n’est pas démontrable. Nous sommes donc en présence d’une proposition qui affirme d’elle-même qu’elle n’est pas démontrable [20], la méthode de démonstration que l’on vient d’exposer peut s’appliquer à tout système formel qui, en premier lieu, interprété comme système de concepts et de propositions, offre des moyens d’expression suffisants pour définir les concepts qui figurent dans le raisonnement précédent (en particulier le concept de « formule démontrable ») et dans lequel, en second lieu, toute formule démontrable est vraie dans l’interprétation considérée. En développant désormais avec toute l’exactitude requise cette démonstration, il s’agira, entre autres choses, de remplacer la seconde des conditions citées par une condition beaucoup plus faible et purement formelle.

Il apparaît immédiatement, dès lors que l’on remarque que [R(q) ; q] affirme d’elle-même qu’elle n’est pas démontrable, que [R(q) ; q] est vraie, puisque de fait [R(q) ; q] est indémontrable (étant indécidable). Ainsi, la proposition qui, dans le système PM, est indécidable peut pourtant être décidée par des considérations métamathématiques. L’analyse précise de cette étrange situation conduit à des résultats étonnants quant aux démonstrations de non-contradiction des systèmes formels, résultats que l’on discutera plus en détail dans la section 4 (Théorème XI).

Note ajoutée le 28 août 1963 [21]
Grâce à certains travaux qui ont suivi cet article, notamment ceux de A.M. Turing [22], nous disposons désormais d’une définition sûre, précise et adéquate du concept de système formel [23], il est possible de donner une version tout à fait générale des théorèmes VI et XI. On peut démontrer rigoureusement que dans tout système formel consistant contenant une théorie des nombres finitaire relativement développée, il existe des propositions arithmétiques indécidables et que, de plus, la consistance d’un tel système ne saurait être démontrée à l’intérieur de ce système.


[1] Kurt Gödel, Sur les propositions formellement indécidables des Principia Mathematica et des systèmes apparentés I (1931) (Cf. le résumé des résultats de ce travail paru in Anzeiger der Akademie der Wissenschaften in Wien (math. naturw. Kl.), 1930, n° 19.) Extrait de Ernest Nagel/James R. Newman/Kurt Gödel/Jean-Yves Girard, Le théorème de Gödel, Éditions du Seuil © 1989, Collection Points # S122, pages 107 à 112.

[2] Le « I » figurant dans le titre original s’explique de la façon suivante : Gödel avait l’intention de publier un second volet à son mémoire, ou il eût donné une démonstration détaillée du théorème XI, c’est-à-dire de ce que l’on appelle le second théorème d’incomplétude. Primitivement, en effet, Gödel n’était parvenu qu’au premier théorème d’incomplétude (la proposition VI de son mémoire). C’est ce résultat qu’il annonça à Königsberg, le 7 septembre 1930, au cours d’une conférence organisée par la Gesellschaft für empirische Philosophie. Au début de l’automne 1930, Gödel découvrit son second théorème d’incomplétude, comme le montre un échange de lettres avec J. von Neumann, et l’incorpora à son article avec l’intention d’y revenir plus en détail dans un prochain essai. Ces résultats paraissant être acceptés sans difficultés par la communauté scientifique, Gödel renonça à son intention et ne publia pas le second volet annoncé. C’est du moins l’une des raisons de ce choix. Sur tout cela, cf. « The reception of Gödel’s incompleteness theorems », J.W. Dawson, in Gödel’s Theorem in focus, éd. Stuart Shanker. Groom Helm, 1988, p. 74-96 (N.d.T.).

[3] A. Whitehead et B. Russell, Principia Mathematica, 2e éd., Cambridge, 1925. Au nombre des axiomes du système PM, nous comptons aussi l’axiome d’infinité (sous la forme : il y a exactement une quantité dénombrable d’individus), l’axiome de réductibilité et l’axiome de choix (pour tous les types). [Les Principia Mathematica sont une œuvre en trois volumes d’Alfred North Whitehead et Bertrand Russell, publiés en 1910-1913. Cette œuvre a pour sujet les fondements des mathématiques. Il s’agit d’un ouvrage fondamental, notamment avec l’idéographie de Frege, dans la mesure où il participa de façon décisive à la naissance de la logique moderne et fut à l’origine des symbologiques logiques actuelles. (Wikipédia 061121 (page actuelle))]

[4] Cf. A. Fraenkel. Dix Conférences sur les fondements de ta théorie des ensembles, Wissensch. u. Hyp. Bd. XXXI, 1927 ; J. von Neumann, « L’axiomatisation de la théorie des ensembles », Mathematische Zeitschrifi 27, 1928, Journal für die reine und angewandte Mathematik 154, (1925), 160 (1929). Remarquons que, pour compléter la formalisation, il faut ajouter aux axiomes de la théorie des ensembles cités dans ces travaux les axiomes et les règles d’inférence du calcul logique. – Les considérations qui suivent s’appliquent également aux systèmes formels élaborés ces dernières années par D, Hilbert et ses collaborateurs (pour autant qu’ils sont à présent disponibles), Cf. D. Hilbert, Malhematische Annalen 88, Abh, aus d. math. Sem. der Univ. Hamburg I (1922), VI (1928) ; P. Bernays, Malh. Ann. 90. ; J. von Neumann, Malhematische Zeitschrift 26 (1927) ; W. Ackermann, Math. Ann. 93.

[5] [Axiome : Point de départ donné comme postulat évident. Inférence : Opération. Règle d’inférence : Règle d’opération.]

[6] C’est-à-dire, plus précisément : Il existe des propositions indécidables dans lesquelles en dehors des constantes logiques : – (non), V (ou), (x) (pour tout), = (identique à), ne figurent pas d’autres concepts que : + (addition), · (multiplication), pris tous deux par rapport aux nombres naturels et où le quantificateur (x) ne peut s’appliquer également qu’aux nombres naturels.

[7] Dans PM, seuls les axiomes qui ne résultent pas d’un simple changement de type sont considérés comme distincts.

[8] Ici, et par la suite, nous entendrons toujours par « formule de PM » une formule écrite sans abréviations (c’est-à-dire sans utilisation des définitions). Les définitions ne servent en effet qu’à une notation abrégée et sont donc en principe superflues.

[9] C’est-à-dire que nous projetons les signes primitifs de manière bi-univoque sur les nombres naturels (voir p. 116 pour un exposé détaillé).

[10] C’est-à-dire une fonction arithmétique définie par un segment initial des nombres naturels. (Il est bien sûr impossible d’ordonner spatialement les nombres.)

[11] En d’autres termes : la procédure décrite plus haut nous procure une image isomorphe du système PM dans le domaine de l’arithmétique et les considérations métamathématiques peuvent aussi bien être perçues sur cette image isomorphe. C’est ainsi qu’il faut voir les choses dans l’esquisse de notre démonstration, c’est-à-dire que par « formule », « proposition », « variable », etc., il faut toujours entendre les objets qui leur correspondent dans l’image isomorphe. [ISOMORPHE : Même structure.]

[12] Il serait très facile (mais quelque peu fastidieux) d’écrire effectivement celle formule.

[13] Par exempte, en rangeant en ordre croissant les sommes des éléments numériques qui forment les signes de classe, et lexicographiquement dans le cas de sommes égales.

[14] La barre désigne la négation. [ x signifie donc : x est une formule non-démontrable]

[15] Definiens n. (pl. -ientia) something that defines. (From the Hutchinson Encyclopedia, Helicon Publishing Ltd. © 2007)

[Definiens n. (pl. -ientia ) la chose qui définit. (la définition).]

[16] Encore une fois, il n’y a pas la moindre difficulté à écrire effectivement la formule S.

[17] Il faut bien remarquer que « [R(q) ; q] » (ou, ce qui signifie la même chose, « [S ; q] ») n’est que la description métamathématique de la proposition indécidable. Cependant, dès lors que l’on a obtenu la proposition S, on peut aussi, bien sûr, déterminer le nombre q et par là écrire effectivement la proposition indécidable elle-même.

[18] Antinomie de Richard : FONDEMENTS DES MATHEMATIQUES
La lettre de Richard est publiée dans le numéro du 30 juin 1905 de la Revue générale des Sciences. Il propose une antinomie de la théorie générale des ensembles obtenue sans « aller jusqu’à la théorie des nombres ordinaux ». Richard définit l’ensemble de tous les arrangements avec répétition des lettres de l’alphabet ordonnés alphabétiquement ; puis il considère le sous-ensemble E des arrangements qui sont des définitions de nombres. On a ainsi, rangés dans un ordre déterminé, tous les nombres définis à l’aide d’un nombre fini de mots. Donc : Tous les nombres qu’on peut définir à l’aide d’un nombre fini de mots forment un ensemble dénombrable. [Richard 1905, p. 541] Il obtient alors une contradiction en définissant un nombre défini par un nombre fini de mots (formant un arrangement G) dont on peut montrer qu’il n’appartient pas à cet ensemble. Richard montre que cette contradiction n’est en fait qu’apparente. En effet, la définition du nombre qu’il propose, nécessite la connaissance de E ; comme E est défini par un nombre infini de mots, le nombre de Richard n’appartient pas à E. Revenons à nos arrangements. Le groupe de lettres G est un de ces arrangements ; il existera dans mon tableau. Mais, à la place qu’il occupe, il n’a pas de sens. Il y est question de l’ensemble E, et celui-ci n’est pas encore défini. Je devrai donc le biffer. Le groupe G n’a de sens que si l’ensemble E est totalement défini, et celui-ci ne l’est que par un nombre infini de mots. Il n’y a donc pas de contradiction. Poincaré - Philosophe et mathématicien.

[19] On pourrait utiliser n’importe quelle antinomie épistémologique pour construire une démonstration similaire de l’existence de propositions indécidables. [Wikipédia : Paradoxe du menteur]

[20] Pareille proposition, contrairement aux apparences, ne contient nulle circularité fallacieuse, car elle affirme tout d’abord qu’une certaine formule bien définie (savoir, celle obtenue à partir de la q-ième formule dans l’ordre lexicographique par une certtaine substitution) n’est pas démontrable. Ce n’est qu’accessoirement (et, en un sens, de manière contingente) qu’il s’avère que cette formule est précisément celle par laquelle la proposition elle-même a été exprimée.

[21] Extrait de Ernest Nagel/James R. Newman/Kurt Gödel/Jean-Yves Girard, Le théorème de Gödel, Éditions du Seuil © 1989, Collection Points # S122, pages 142 et 143.

[22] Cf. A M. Turing, « On computable numbers », Proceedings of the London Math Society, 42,. 230-265, 1937.

[23] Selon moi, le termes « système formel » ou « formalisme » ne devraient être utilisés que pour ce concept. Dans une conférence que j’ai donnée à Princeton (cf. Princeton University, 1947. p. 11), j’ai suggéré certaines généralisations transfinies des formalismes. Mais il s’agissait là de quelque chose de très différent des systèmes formels au sens propre du terme, dont la propriété caractéristique est qu’en eux, et en principe, le raisonnement peut être entièrement remplacé par des règles mécaniques.


Documents joints

Word - 96 ko
Word - 96 ko

Sites favoris


20 sites référencés dans ce secteur