I am nothing, no one, nobody, no more

Get out of life alive le blog de SnippyHolloW.

L’incomplétude pour les (matheux) nuls

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: , , ,

27 commentaires pour “L’incomplétude pour les (matheux) nuls”

  1. Julius dit :

    Di…digeste ?!

  2. KratosWitch dit :

    Talk liek a fag !

  3. Rygaar dit :

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

    Raté, j’ai strictement rien compris (à partir de la 2ème ligne).
    Ca doit s’adresser à un public très resteint en l’occurrence, mais pas à des nuls.

  4. epsylon dit :

    Ricardo Caferra, j’le connais lui, prof à l’ENSIMAG :]

  5. Ulys dit :

    Mouais…
    Ton raisonnement par l’absurde est immonde.
    Tu as l’air d’avoir un bon niveau en maths, tu dois savoir que faire un raisonnement par l’absurde pas clair et en trois lignes c’est un peu comme jongler avec des grenades. Ça risque de te péter à la gueule au moment où tu t’y attends le moins.

  6. elpopo dit :

    Comment tu fais le A à l’envers ?

  7. KratosWitch dit :

    Comme ça ∀

  8. elpopo dit :

    ∀ ;d ca marche thx!

  9. Anon dit :

    “geste”

  10. SPhoenix dit :

    J’ai pas encore regardé en détail, mais merci, j’ai jamais eu le courage de me plonger dans les théorèmes de Gödel.
    Je regarderai ca demain quand j’aurai plus de temps!

  11. SnippyHolloW dit :

    Eh bien désolé pour ceux qui trouvent ça incompréhensible … J’aurais essayé (je devrais avoir le droit de mettre un smiley triste ici) ! J’y ai passé du temps et ai pensé rendre ça accessible avec un niveau bac+1 / bac+2 en mathématiques. Je l’ai testé sur des potes mais ils sont un peu plus entrainés.

    Ah oui, c’est pas “mon” raisonnement par l’absurde mais celui de Gödel ! Il faut le lire lentement, voir se faire un dessin. On n’a rien sans rien …

  12. Mysterius dit :

    C’est probablement accessible pour un bac +1 ou +2 en mathématiques, mais à ce moment là ne dit pas “pour les nuls” =].

  13. PositiveFunk dit :

    J’ai tenu jusqu’au iv, ensuite je pige rie. C’est grave docteur?

  14. SnippyHolloW dit :

    Mysterius : j’ai “corrigé” !

    PositiveFunk : T’as fait le plus dur …
    - Suppose F prouvable à partir de A. On a défini plus haut F comme l’énoncé qui anonce qu’il est improuvable à partir uniquement de A DONC F est faux.
    - F faux + prouvable à partir de A DONC A contient des énoncés faux (il prouve un énoncé faux).
    - OR on avait construit A avec uniquement des énoncés vrais DONC F n’est pas prouvable à partir de A.

  15. PositiveFunk dit :

    OUias, je crois avoir pigé lé truc. Mais c’est hardcore ce truc? Circuit logique ou ce genre de truc?

    Limite son théorème est utilisable en psychologie. (j’y connais rien en maths) c’est tellement général en fait. Logique de meurtre et alibis.

    III) c’est la mise en contexte d’un meurtre et de ces paramètres.

    iv) ce serait la vérification de l’énoncé.

    III) l’énoncé me rappelle lorsque j’utilisais pspice de façon un peu poussé, il y avait des boards qui ne pouvaient pas faire le travail car je partais d’axiome qui ne rentraient pas dans le cadre de III)

    Fin bref, il se fait tard.

  16. SnippyHolloW dit :

    C’est un résultat qui fait la différence entre vérité mathématique et prouvabilité. Ça entraine surtout que l’on ne peut pas prendre un ensemble d’axiomes de bases pour étudier les mathématiques de manière formelle. Il n’y a pas de lien direct avec les “circuits logiques” (qu’entends-tu par là ?). Je ferais peut-être un article beaucoup plus “philosophique” de son implication sur l’intelligence artificielle.

  17. anonyme dit :

    Si vous avez deja eu un cours de preuve mathematique, tout ce qui est racconter plus haut est normalement simple a “decoder”.

    Donc, FA or, on utilise la biconditionallitee (je sais pas si ca se dit mais en gros c’est ca) comme relation entre les 2 “veritees”. En qqsorte, si on a par exemple F et A

    vrai vrai = vrai
    faux vrai = faux
    vrai faux = faux
    faux faux = vrai

    Donc la, comme un obtient qqchose de faux, ou bien A ou bien F est faux et vu qu’on sait que A est vrai quoi qu’il arrive, F est faux.

  18. epsylon dit :

    Pour ceux que ça intéresse, mais qui comprennent rien, y’a aussi Raymond Smullyan en parle de manière ludique et relativement accessible dans son Livre qui rend fou (c’est une compilation d’énigmes logiques, les classiques, à base de portes, de menteurs, etc… Il y a pas forcément besoin d’avoir un gros cursus mathématique pour le lire, suffit d’aimer se griller un peu le cerveau :-)).

  19. Clacbec dit :

    On peut aussi lire la GEB
    http://www.amazon.fr/G%C3%B6del-Escher-Bach-Guirlande-Eternelle/dp/2100523066/ref=sr_1_3?ie=UTF8&s=books&qid=1232007678&sr=1-3

    un peu un pavé mais assez agréable a lire surtout quand on aime les trucs un peu méta, rien que le dialogue
    placé au milieu du livre qui est un palindrome geant, dont le point central est le passage d’un crabe, que du bon
    Il y a une bonne intro aux systèmes formel avant d’amener le théorème de godel

  20. SnippyHolloW dit :

    Je confirme pour les 2 ;)

  21. DindonPoilu dit :

    En effet, Gödel Escher Bach (GEB) est un bouquin passionnant.
    Et il a maintenant une suite : Je suis une boucle étrange.

  22. A dit :

    Bof je suis pas impressioné, tout ça n’est qu’une vue de l’esprit. Il n’y a de vrai, de faux que dans les mots (hobble).

  23. El_Porico dit :

    anonyme: on dit XNOR.

  24. LeGreg dit :

    oui et la plupart des paradoxes du genre (ensemble des ensembles n’est pas un ensemble, ce programme est-il terminable ?) font appel à l’auto-référence.

    self-reference is evil

  25. DindonPoilu dit :

    L’auto-référence c’est ce qui permet la conscience. C’est grâce à ça qu’on peut dire “je”, qu’on peut se reconnaître dans un miroir.
    C’est justement le sujet de “Je suis une boucle étrange”.

  26. Kyriea dit :

    J’aime pas comment il dit ca Ulys. ‘nyway.

    Moi j’ai rien capté. Vive les bac ES =D

  27. Tof dit :

    Je trouve que c’est de grande qualité. J’ai pas suivi les cours de logique de 3A, donc je suis un peu largué, mais je suis content de chopper un peu de culture là dessus. Bon, on est de la même école, donc on a un passé commun, mais je crois que ce que t’as écrit est plutôt accessible pour qui veut faire l’effort. Genre un (bon) élève de bac+2 suivant un cursus mathématique. Par contre, en bac+1, je pense que j’aurais pas pu.

Laisser un commentaire

Si vous avez un compte sur WeFrag, connectez-vous pour publier un commentaire.

Vous pouvez, entre autres, utiliser les tags XHTML suivant :
<a href="" title="">...</a>,<b>...</b>,<blockquote cite="">...</blockquote>,<code>...</code>,<i>...</i>