1931
Théorème de Gödel
SOMMAIRE
|
|
|
|
|||
|
|
|||||
|
|
1931 |
||||
|
Théorème de Gödel |
|||||
|
SOMMAIRE |
|||||
|
Sur les propositions formellement indécidables 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. 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 [5]. 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 [6], 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 [7]. 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 [8]. En conséquence, une formule est une suite finie de nombres naturels [9] 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 [10] 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) [11], 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 [12], 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 a un signe de classe quelconque ; par [a ; n] nous désignons la formule qui résulte du signe de classe a 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 :
(où Dem x signifie : x est une formule démontrable) [13]. Puisque les concepts qui apparaissent dans le definiens [14] 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 [15] 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] [16]
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 L'analogie qui existe entre ce raisonnement et l'antinomie de Richard [17] saute aux yeux ; il est également étroitement apparenté au « menteur » [18], 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 [19], 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 [20] Grâce à certains travaux qui ont suivi cet article, notamment ceux de A. M. Turing [21], nous disposons désormais d'une définition sûre, précise et adéquate du concept de système formel [22], 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. [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, où 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). [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]
C'est-à-dire, plus précisément : [6] Dans PM, seuls les axiomes qui ne résultent pas d'un simple changement de type sont considérés comme distincts. [7] 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. [8] C'est-à-dire que nous projetons les signes primitifs de manière biunivoque sur les nombres naturels (voir p. 116 pour un exposé détaillé). [9] 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.) [10] 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. [11] Il serait très facile (mais quelque peu fastidieux) d'écrire effectivement celle formule. [12] 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.
[13]
La barre désigne la négation.
[
[14]
Definiens n. (pl. -ientia) something that defines [la définition]. [15] Encore une fois, il n'y a pas la moindre difficulté à écrire effectivement la formule S. [16] 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.
[17]
Antinomie de Richard :
FONDEMENTS DES MATHÉMATIQUES [18] On pourrait utiliser n'importe quelle antinomie épistémologique pour construire une démons-tration similaire de l'existence de propositions indécidables. [Wikipédia : Paradoxe du menteur] [19] 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 certaine 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. [20] 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, pp. 142-143. [21] Cf. A. M. Turing, « On computable numbers », Proceedings of the London Math Society, 42, 230-265, 1937. [22] Selon moi, les 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.
|
|||||
|
|
(1)
[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.
