Coder but Gamer

Je me suis librement inspiré d’Intelligence Artificielle de Russel & Norvig, du Polycopié de Logique et Mécanisation de l’Inférence de Ricardo Caferra, et de Wikipedia.

En 1920, David Hilbert a lancé un programme de recherche visant à donner une base formelle aux mathématiques. Un ensemble d’axiomes de base à partir desquels on pourrait prouver tous les théorèmes mathématiques qui sont  des (énoncés de) vérités dans ce “monde imaginaire dont on crée les règles”. Kurt Gödel a démontré, avec son premier théorème d’incomplétude, qu’il existe des énoncés (formules closes) arithmétiques vrais qui sont impossibles à prouver. Ce fut dès lors la fin du rêve d’Hilbert d’unifier les mathématiques sur une base formelle.

Voici une esquisse de la preuve (la preuve complète, de Gödel, fait 30 pages) de ce théorème dans un but de vulgarisation à des personnes ayant des bases de mathématiques mais pas de logique. J’essaye ici de donner plus la forme et l’idée qui devraient permettre de comprendre le résultat de Gödel qu’une preuve formelle qui demanderait des connaissances en logique mathématique. Ceux qui veulent sont toujours à même d’aller consulter Wikipedia pour avoir des définitions formelles ou la preuve complète.

I) Définition d’un langage pour l’arithmétique
Commençons par énumérer les entiers, il nous faut :
• la constante 0
• la fonction S, successeur
S(0) = 1, S(S(0)) = 2 . . . On a construit les entiers. On dit qu’ils sont récursivement énumérables.
On rajoute à ce langage les fonctions ‘+’, ‘x’, ‘exp’ (la mise à la puissance si vous préférez), ainsi que les quantificateurs existentiel et universel et les connecteurs logiques non, et, ou, implication.

II) Numération de Gödel
L’ensemble des énoncés que l’on peut écrire dans ce langage est énumérable. Par exemple si l’on définit un code pour chacun des symboles de base (S()=’1′, +()=’2′, x()=’3′ …), un énoncé peut-être codé par la concaténation des codes des symboles qui le composent. On numérote ainsi les énoncés avec leur nombre de Gödel #E. À chaque énoncé E correspond une ou plusieurs preuves. Une preuve P étant une suite d’énoncés, on peut elle-même la numéroter par son nombre de Gödel G(P).

III) Construction d’un énoncé particulier
Prenons un ensemble A récursivement énumérable d’énoncés vrais à propos des entiers naturels (le point important est que l’on puisse les compter). On peut écrire un énoncé E=(j, A) qui serait : ∀ i, i ≠ G(P(E)) avec {P(E)} ⊆ A et #E=j, qui se lit “pour tout i, i n’est pas le nombre de Gödel de la preuve, utilisant seulement des hypothèses A, d’un énoncé dont le nombre de Gödel est j”.  Autrement dit, un énoncé dont le nombre de Gödel est j est improuvable avec seulement les hypothèses A. Soit F l’énoncé (#F, A) construit comme ci-dessus, c’est un énoncé qui affirme sa propre non-prouvabilité à partir de A. “Un énoncé dont le nombre de Gödel est #F est improuvable avec seulement les hypothèses de A”. F est l’énoncé qui se dit non prouvable à partir de A, nous n’avons pas encore prouvé sa véracité.

IV) “Diagonalisation”, par l’absurde
Montrons maintenant par l’absurde que F n’est pas prouvable à partir de A. Supposons que F soit prouvable à partir de A, alors F est faux (puisqu’on peut le prouver alors qu’il dit le contraire). F est faux et prouvable à partir de A donc A n’est pas constitué seulement d’énoncé vrais, ce qui est en contradiction avec notre hypothèse de départ. (Parenthèse : si l’on accepte de contredire l’hypothèse de départ, notre théorie n’est pas cohérente et n’a donc pas de sens.) Donc F n’est pas prouvable à partir de A et donc F est vrai (c’est ce qu’il affirme).

<< 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é ni réfuté dans cette théorie. >> (Wikipedia) On peut aussi le voir comme ceci : il n’existe pas d’ensemble d’axiomes de base qui permettent de démontrer l’ensemble des vérités arithmétiques.

Remarque : Le langage arithmétique pourrait (devrait) contenir avoir la comparaison (’<’) et le raisonnement par induction complète mais ça ne fait que complexifier les choses ici.

J’espère avoir écrit quelque chose de digeste …

Tags: Gödel, incomplétude, logique, mathématiques