Logique et Raisonnement Scientifique

A. Lecomte

Gödel et l’incomplétude

Gödel et l’incomplétude de l’arithmétique formelle

Kurt Gödel : 1906 - 1978

1931 : « Sur les propositions formellement indécidables des Principia Mathematica et des systèmes apparentés ».

(Kurt Gödel et Albert Einstein à Princeton)

« Le développement des mathématiques vers plus de précision a conduit à la formalisation de vastes domaines de telle sorte que les démonstrations puissent être développées en suivant un petit nombre de règles mécaniques. Les systèmes formels les plus étendus à ce jour sont, d’une part les Principia Mathematica de Whitehead et Russell et, d’autre part, le système de Zermelo-Fraenkel de la théorie axiomatique des ensembles. Ces deux systèmes sont si vastes que toutes les méthodes de démonstration utilisées aujourd’hui en mathématiques peuvent y être formalisées, c’est-à-dire peuvent être réduites à un petit nombre d’axiomes et de règles de déduction. Il semblerait donc raisonnable de conjecturer que ces axiomes et ces règles de déduction suffisent pour décider de toutes les questions mathématiques qui peuvent être formulées dans le système concerné. Dans ce qui suit, il sera montré qu’il n’en est pas ainsi, mais plutôt, que dans les deux systèmes cités, il existe des problèmes relativement simples de la théorie des nombres entiers ordinaires dont on ne peut décider sur la base des axiomes ».

Le théorème de Gödel

Idée centrale: à partir du moment où nous avons un système formel incluant la possibilité d’exprimer des relations arithmétiques (les nombres entiers et leurs propriétés élémentaires), alors ce système est capable d’exprimer des propriétés sur lui-même, et si nous sommes capables de construire rigoureusement dans un tel système une formule analogue à celle du Menteur, alors de deux choses l’une : ou nous acceptons qu’il y ait une contradiction dans le système ou nous acceptons qu’il y ait des formules vraies qui ne puissent pas être démontrées et c’est bien sûr la deuxième possibilité que nous choisirons.

Quelques précisions1- la numérotation de Gödel

: 1 : 2 : 3 : 4 : 5 0 : 6 s : 7 ( : 8 ) : 9 , :10

x : 11 y : 13 z : 17

p : 112

q : 132

r : 172

P : 113

Q : 133

R : 173

var. numériques

var. propositionnelles

var. prédicatives

Quelques précisions1- la numérotation de Gödel

( x ) ( x = s y )

8 4 11 9 8 11 5 7 13 9

28.34. 511.79.118.1311.175.197.2313.299

Etendre la numérotation de Gödel aux déductions

Exemple :– 1– 2

deux lignes possibles d’une déduction (substitution de 0 à y dans la ligne 1)

))(( syxx )0)(( sxx

Etendre la numérotation de Gödel aux déductions

Exemple :– 1 m– 2 n

k = 2m3n « la déduction de nombre de Gödel k est une

démonstration de la formule de nombre de Gödel n »

))(( syxx )0)(( sxx

Etendre la numérotation de Gödel aux déductions

Plus généralement : L’assertion « la suite de formules de nombre

de Gödel x est une démonstration de la formule de nombre de Gödel z  » se trouve reflétée dans le système par une relation arithmétique Dem(x, z)

Mais cette relation possède elle-même un nombre de Gödel!

Construction de «la formule G »

La formule possède un nombre de Gödel

Elle signifie : « il n’existe pas de démonstration (représentée par un nombre de Gödel x) de la formule de nombre de Gödel z »

Soit sub(m, p, q) le ndG obtenu en substituant dans la formule de ndG m, à la variable de ndG p, le chiffre q

),()( zxDemx

Construction de «la formule G »

Soit la formule : elle dit: « la formule obtenue en substituant

dans la formule de ndG y, à la variable de ndG p, le chiffre y, n’est pas démontrable »

elle possède un nombre de Gödel n, qu’on peut substituer à y, on obtient: G =

)),,(,()( ypysubxDemx

)),,(,()( npnsubxDemx

Etude de la formule G

Quel est son nombre de Gödel? On l’a obtenue en substituant au sein de la formule

de ndG n, à la variable de ndG p, le chiffre n, ce qui est la définition de sub(n, p, n)

donc son ndG est sub(n, p, n) d’autre part elle dit que « la formule qui possède le

ndG sub(n, p, b) n’est pas démontrable » Donc elle dit d’elle-même qu’elle n’est pas

démontrable

Le cœur de la démonstration

Si G est démontrable, G est démontrable– Supposons G démontrable, il existe une suite de

formules de ndG k telle que Dem(k, sub(n, p, n)), – Donc Dem(k, sub(n, p, n)) est démontrable,– Donc (x) Dem(x, sub(n, p, n)) = G est

démontrable si G est démontrable, G aussi! Donc ni G ni G ne sont démontrables (si

l’arithmétique est consistante!)

… mais G est vraie!

G n’est pas démontrable Mais c’est justement ce que dit G!!!! Donc G est vraie! D’où l’existence d’une formule vraie non

démontrable

2ème théorème de Gödel

L’arithmétique est-elle consistante? La consistance s’exprime par la formule : A =

(il y a au moins une thèse non démontrable) La formule « A G » est démontrable Si A était démontrable… G le serait donc

aussi! Donc A n’est pas démontrable

),())(( yxDemxy

Conséquence fondamentale

La consistance de l’arithmétique formelle ne peut pas être démontrée dans la théorie de l’arithmétique formelle

On ne peut pas prouver au moyen de méthodes finitistes à la Hilbert la non-contradiction d’une théorie incluant au minimum l’arithmétique formelle

Échec du programme de Hilbert