Les théorèmes d’incomplétude de Gödel

Aujourd’hui je m’attaque à un gros morceau : les théorèmes de Gödel !

Il y aurait des pages à écrire pour compléter cette vidéo, et ci-dessous je vous commente certains points et fait quelques remarques, mais bien évidemment ceci ne saurait constituer une présentation exhaustive de la chose !

Des propositions indécidables

Je l’ai dit dans la vidéo, on ne rencontre pas a priori de propositions indécidables tous les jours. Et pourtant, une question relativement simple comme l’hypothèse du continu est indécidable dans ZFC.

Parmi les choses indécidables dans Peano, mais prouvables dans des systèmes plus fort (comme ZFC), on peut citer :

Il existe aussi toute une liste de questions indécidables dans ZFC.

Par exemple, il existe des propositions comme le problème de Whitehead qui est une question de théorie des groupes pas trop trop tordue, mais qui est quand même indécidable de ZFC.

La portée du théorème

Je l’ai dit à la fin de la vidéo, on a souvent tendance à faire dire au théorème de Gödel bien plus que ce qu’il ne dit réellement. Il est notamment important de se souvenir qu’il s’applique aux systèmes d’axiomes récursifs qui couvrent au moins l’arithmétique des nombres naturels. Voyons d’abord le côté “récursif”, que j’ai soigneusement évité de traiter dans la vidéo.

Imaginez que je fasse la chose suivante : je prends TOUTES les propositions vraies de l’arithmétique, et je crée un système d’axiomes dans lequel chacune de ces propositions est un axiome. J’obtiens alors un système d’axiomes pas forcément très intéressant, mais qui semble violer le théorème de Gödel, puisque toute proposition vraie de l’arithmétique y est démontrable (eh oui, puisqu’elle en est un axiome !).

Ce système d’axiomes porte un nom, on l’appelle “True Arithmetics”, mais outre le fait qu’il est totalement inutile, il a un problème : si je vous donne une proposition quelconque, vous n’avez pas de moyen simple de dire si oui ou non cette proposition fait partie des axiomes du système. De fait un tel système d’axiome est totalement inutilisable !

C’est pour cela qu’en pratique, on s’impose de travailler avec des systèmes d’axiomes récursifs, c’est-à-dire faits d’axiomes qui sont potentiellement en nombre infini, mais tels que pour toute proposition, on puisse dire en un temps fini si oui ou non la proposition fait partie des axiomes.

Le théorème de Gödel porte justement sur les systèmes d’axiomes récursifs, et c’est pour cela que la True Arithmetics peut y échapper (mais vous l’aurez compris, en pratique un tel système n’est pas très utile.)

Passons maintenant à la seconde condition : le théorème de Gödel porte sur les systèmes d’axiomes (récursifs, donc) qui axiomatisent au minimum l’arithmétique. Cela signifie que des systèmes axiomatiques trop faibles pour couvrir l’arithmétique peuvent parfaitement échapper au théorème. C’est le cas notamment de l’arithmétique dite “de Presburger”, qui est celle qu’on obtient en considérant les nombres naturels munis de l’addition, mais sans la multiplication !

La raison pour laquelle la multiplication est indispensable pour que Gödel fonctionne est liée au fait que la réflexion de la méta-arithmétique dans l’arithmétique fait justement appel à la multiplication. Pour le voir, il faut s’attarder un peu sur le codage de Gödel.

Le codage de Gödel

Je ne vais pas faire ici une présentation parfaitement propre du codage de Gödel, mais je voudrais en tracer les grandes lignes. Notez d’aileurs qu’il en existe plusieurs variantes, mais le résultat est toujours le même.

Pour que les maths soient un tant soit peu compréhensibles, on utilise notre langue “naturelle” (le français, par exemple) pour énoncer des axiomes, des propositions ou des théorèmes. Et pourtant, si l’on voulait, on pourrait écrire tout cela en langage purement formel, en utilisant un nombre restreint de symboles mathématiques, par exemple les symboles :

\displaystyle +, -, \times, =, \in, \forall, \rightarrow, x, y, z, \cdots

Toute proposition mathématique peut s’écrire comme une formule constituée de ces symboles, c’est-à-dire comme une suite finie de symboles, respectant certaines règles.

J’ai présenté dans la vidéo le codage où on attribue un nombre à 3 chiffres (sans zéro) à chaque symbole, et on sépare les symboles d’une formule avec le zéro, et les différentes formules avec par exemple un double zéro.

Le codage original de Gödel est plus proche de celui-ci : on peut choisir de coder chaque symbole par un nombre entier, par exemple si on a 15 symboles, on peut choisir les nombres de 1 à 15.  Si une formule est consistuée successivement des symboles portant les nombres $latex s_1, s_2, s_3, s_4,$ etc., on peut par exemple la coder par le nombre :

\displaystyle 2^{s_1} \times 3^{s_2} \times 5^{s_3} \times 7^{s_4} \times 11^{s_5} \cdots

où l’on utilise les nombres premiers dans l’ordre (et vous voyez pourquoi on a absolument besoin de la multiplication !). Il existe d’autres codages possibles qui sont tout à fait équivalent pour démontrer le théorème de Gödel, mais le point important est qu’avec une telle procédure, à toute formule on peut associer un nombre entier, et réciproquement à partir de ce nombre entier, on peut reconstituer la formule de départ (grâce à l’unicité de la décomposition en facteurs premiers).

Maintenant qu’est-ce qu’une démonstration ? C’est une suite de formules qui s’enchaînent en respectant les règles de la logique. En utilisant le même mécanisme, à toute suite de formule (donc à toute suite de nombres) on peut associer un nombre. Au final, grâce au codage de Gödel, toute formule est codée par un nombre, et toute suite de formules est codée par un nombre.

Pour qu’une suite de formule constitue une démonstration d’une proposition, il faut que les formules s’enchainent selon les règles de la logique, ces dernières étant une liste de manipulation autorisées que l’on peut faire sur des formules. Voici un exemple d’une telle manipulation : si une formule commence par une double négation, alors on peut supprimer ces deux négations. La proposition \neg\neg P peut être transformée en P.

Or une fois qu’on a traduit nos formules en suite de nombres, ces règles de la logique se traduisent en propriétés purement arithmétiques. Reprenons notre exemple de l’élimination de la double négation en tête de formule. En codage de Gödel, mettons que le nombre associé au symbole de négation \neg soit 7, cela se traduit par le fait que si un nombre possède une décomposition en facteurs premiers commençant par 2^7 3^7 alors on peut le transformer en un autre nombre obtenu en supprimant ces facteurs.

J’ai pris l’exemple le plus simple, mais l’idée est là : dire qu’une suite de formule s’enchaine selon les règles de la logique se traduit par la satisfaction de certaines propriétés arithmétiques sur le nombre “codé de Gödel” qui représente cette suite de formules.

On peut alors définir D(x,y) qui est vraie si la suite de formules codée par le nombre x constitue une démonstration de la proposition codée par le nombre y. Le point clé dans l’affaire, c’est que la relation D(x,y) est une relation purement arithmétique ! En particulier le fait que les formules qui constituent la démonstration codée par x s’enchaînent selon les règles de la logique se traduit sous forme de propriétés purement arithmétiques.

Dire que la proposition codée par le nombre y est démontrable est alors équivalent à dire

C(y) = \exists x\ | \ D(x,y)

On a donc bien une proposition purement arithmétique C(y) qui est vraie si et seulement si la proposition codée par le nombre y est démontrable.

Je vous cache encore quelques détails sous le tapis, mais si vous voulez en savoir plus, vous trouverez sans peine des exposés plus complets sur le codage de Gödel (voir par exemple le livre de Nagel et Newman).

godel

La diagonalisation

Je l’ai expliqué dans la vidéo, l’astuce de Gödel consiste ensuite à exhiber UNE proposition en particulier, appelons-la G, codée par le nombre de Gödel g, telle que C(g) soit la négation de G. Cela signifie que G est démontrable si et seulement si elle est fausse.

Là aussi je vous épargne l’argument exact, vous pouvez le trouver dans plusieurs textes comme celui de Nagel et Newman, mais il repose sur une astuce de “diagonalisation” comme le fait par exemple Cantor pour trouver un nombre réel qui ne soit pas en bijection avec l’ensemble des entiers naturels.

Un point que je n’ai pas mentionné dans la vidéo, c’est que Gödel démontre également que si G est démontrable, alors sa négation formelle l’est également (et on retrouve l’esprit du paradoxe du menteur). Et c’est là qu’on se retrouve avoir le choix entre le rhume et la peste : soit la proposition est démontrable, et sa négation l’est aussi, et on a alors un système d’axiome incohérent; soit la proposition G n’est ni démontrable, ni réfutable, auquel car le système est incomplet. Mais si nous sommes dans ce cas, alors pour autant nous sommes en mesure d’affirmer que G est une proposition vraie de l’arithmétique puisqu’elle est démontrable si et seulement si elle est fausse. Mais bien évidemment la proposition non-G est une proposition fausse de l’arithmétique, qui est tout autant indécidable.

Bref, le théorème de Gödel nous dit qu’il existe des propositions vraies et indécidables, mais tout autant de propositions fausses et indécidables !

Compléter le système d’axiomes

A ce stade, on a donc construit une proposition vraie de l’arithmétique, mais indécidable, et ce quel que soit le système – cohérent – d’axiomes qu’on utilise. Très bien, cela signifie alors que l’on peut ajouter cette proposition à notre système d’axiomes, tout comme on peut ajouter sa négation si cela nous chante.

Cela peut paraître surprenant : si j’ajoute G, j’ajoute à mon système d’axiomes une proposition vraie de l’arithmétique, pas de soucis. Mais si j’ajoute sa négation, cela signifie que j’ajoute, sans créer de contradiction, une proposition FAUSSE de l’arithmétique à mon système d’axiomes. Mais un tel système d’axiomes n’axiomatise plus l’arithmétique, alors ? Et il axiomatise quoi ???

Pour cela, il faut se pencher sur la notion de modèle.

Les modèles

Dans ma vidéo, j’ai fait exprès de dire cette phrase incorrecte “un truc vrai, c’est un truc vrai”. J’ai bien insisté sur l’idée que la notion de démontrabilité n’était pas absolue, mais relative à un système d’axiome, et j’ai fait comme si la notion de “vérité” était, elle, absolue…alors qu’elle ne l’est pas ! Une proposition est démontrable (ou pas) dans un système d’axiomes, une proposition est vraie (ou fausse) dans ce qu’on appelle un modèle : la notion de vérité est elle aussi relative.

Un modèle, c’est un “truc” (je fais exprès d’être vague) qui à toute proposition bien construite attribue la valeur “vrai” ou “faux”. Précisons un peu cela.

Pour construire des formules, on a vu qu’il nous fallait un langage fait de symboles. Une formule est une suite de symboles qui respecte certaines “règles de grammaire”. Il existe des formules mal construites, comme la formule “==+=” qui utilise les symboles du langage, mais ne veut rien dire. Parmi les symboles autorisés, les formules peuvent utiliser des variables, comme x, y, z, … auxquelles on peut faire correspondre des “quantificateurs” : \forall, \exists. Il existe des formules comme

\displaystyle \exists y\ | \ x=y+z

qui sont des formules bien construites, mais pour lesquelles il existe des variables libres (ici, x et z). Des formules de ce genre ne peuvent pas recevoir des valeurs de vérité “vrai” ou “faux”, puisque que cela va dépendre du choix de x et z. On va appeler une “proposition” une formule bien construite du langage dont toutes les variables sont fixées par un quantificateur.

Un modèle, c’est une application qui à toute proposition du langage assigne une valeur de vérité, “vrai” ou “faux”.

Les modèles de la géométrie

Revenons quelques instants sur les axiomes d’Euclide. Je ne vais pas rentrer trop dans les détails car pour cela il faudrait les mettre sous une forme totalement formalisée, ce qui serait assez fastidieux. Mais vous savez sans doute que parmi ces axiomes il en existe un fameux, “le cinquième”, qui dit que pour toute droite et tout point hors de cette droite, il existe une unique parallèle à la droite passant par ce point (d’ailleurs si on regarde de près, cet axiome en contient en fait deux : existence et unicité de la droite).

Imaginons que l’on ait oublié cet axiome, ou qu’on l’ait rejeté en pensant qu’il pouvait se déduire des 4 autres comme Euclide et d’autes ont essayé de le démontrer. Cet axiome étant en fait indépendant des 4 premiers, il est indécidable dans le système restreint constitué seulement des 4 premiers axiomes. On peut donc parfaitement choisir sans créer de contradiction de le rajouter…ou de rajouter sa négation ! Si on ajoute cet axiome, on obtient une axiomatisation de la géométrie euclidienne. Mais si on ajoute sa négation (ou plus précisément la négation soit de son existence, soit de son unicité) on obtient un système d’axiomes parfaitement cohérent mais qui n’axiomatise PAS la géométrie euclidienne, et qui axiomatise un autre modèle : celui des géométries sphériques ou hyperbolique.

En bon physicien, je vais comparer la notion de modèle à celle d’univers physique dans lequel se produisent des phénomènes physiques (et donc les choses y sont vraies ou fausses), et celle de système d’axiomes aux équations que l’on va mettre pour essayer de capturer ces phénomènes, et qui sont par essence toujours des approximations qu’on peut compléter, mais sans jamais capturer la totalité de la réalité physique.

Maintenant que l’on a vu que si l’on rencontre une proposition indécidable d’un système d’axiomes, on peut ajouter soit cette proposition, soit sa négation au système, mais que dans ce cas on se retrouve à axiomatiser deux “modèles” différents, voyons ce qu’il se passe si on ajoute comme axiome une proposition indécidable, mais fausse de l’arithmétique.

Les arithmétiques non-standard

Si on s’amuse à faire ça, on se retrouve à axiomatiser un truc différent de l’arithmétique standard, que l’on peut appeler une arithmétique non-standard. A quoi cela peut-il ressembler ? Une proposition indécidable mais vraie de l’arithmétique aura forcément une forme du genre : pour tout entier n alors P(n) est vraie. Sa négation est alors : il existe n tel P(n) soit fausse. Si on ajoute un tel axiome, on axiomatise un modèle différent du modèle standard de l’arithmétique, et contient (au moins) en plus de nos bons vieux entiers naturels un élément (que l’on peut appeler comme on veut, disons \Omega) et pour lequel la propriété P(\Omega) est fausse.

Le théorème de complétude

Passons maintenant à ce qu’on appelle le théorème de complétude de Gödel, et que ce dernier a démontré pendant sa thèse, peu avant de sortir ses théorèmes d’incomplétude.

Choisissons un langage et prenons un système d’axiomes énoncé avec ce langage, c’est-à-dire un ensemble de propositions que l’on va déclarer comme axiomes (on appelle parfois cela “une théorie”). On peut s’amuser à déduire des théorèmes de cette théorie. Pour faire tout cela, on n’a pas besoin de la notion de modèle.

Maintenant considérons un modèle de cette théorie, c’est-à-dire un modèle formé sur le même langage et qui soit tel que toute proposition qui est axiome de la théorie soit également une vérité du modèle. Des modèles de ce genre, a priori on peut en imaginer des tas, il en existe certainement une infinité.

Ce que nous dit le théorème de complétude, et qui n’a rien d’évident, c’est que si une proposition donnée est vraie dans TOUS les modèles d’une théorie, alors elle est nécessairement un théorème de cette théorie. Une autre manière de le dire est que la vérité sémantique (celle issue des modèles) et équivalente à la vérité syntaxique (le fait qu’une proposition se déduise des axiomes).

Fermat et les axiomes

Quand j’ai écrit la vidéo, je n’étais pas au courant d’une subtilité concernant le théorème de Fermat et sa démonstration par Andrew Wiles. D’après ce billet de blog, la démonstration originale de Fermat par Wiles utilise en fait un système d’axiomes plus puissant que ZFC ! Plus précisément, il utilise les grands cardinaux. Apparemment ça ne posait pas de grands soucis aux mathématiciens, et d’ailleurs il semble que depuis quelques années on ait réussi à produire une démonstration qui se passe de ces axiomes, et qui n’utilise donc que ZFC.

Plus étonnant, le billet suggère qu’il est vraisemblable qu’une démonstration de Fermat puisse se faire purement dans Peano. Voir aussi cet article.

Le Bitcoin et la Blockchain

La vidéo du jour décrypte les mystères du bitcoin, et vous explique vraiment comment il marche, et ce qu’est cette mystérieuse blockchain.

Pour préparer cette vidéo, j’ai dû pas mal me documenter. J’ai trouvé beaucoup d’endroits où les grands principes du bitcoin sont expliqués, mais assez peu d’infos détaillées sur ce qu’il se passe vraiment « sous le capot ». A force de lecture, je pense avoir compris l’essentiel, et j’espère donc avoir donné à tout le monde les éléments nécessaires pour comprendre comment un système comme le bitcoin pouvait tenir debout, et en quoi le concept de la blockchain assure la décentralisation du système. Lire la suite

[Vidéo] Les codes secrets (et un peu de MCMC)

Ma vidéo du week-end traite des codes secrets et de la cryptographie RSA. Si j’en crois les chiffres, ça passionne plus les foules que la biologie cellulaire d’il y a deux semaines !

Un sujet connexe que j’ai hésité à aborder dans la vidéo concerne les techniques de décryptage par Markov Chain Monte Carlo (MCMC pour les intimes) que j’ai un peu découvertes en lisant un excellent papier intitulé The Markov Chain Monte Carlo revolution (P. Diaconis, Bulletin of the American Mathematical Society 46.2 (2009): 179-205.). Les MCMC sont des algorithmes assez génériques aujourd’hui utilisés un peu partout de la physique statistique jusqu’aux problèmes de génétique des populations ou de linguistique (par exemple mon billet sur l’origine des langues indo-européennes) Lire la suite

Le test de Turing-Parker : un ordinateur peut-il improviser comme Charlie Parker ?

charlie parker miles davisIl y a quelques semaines, il a beaucoup été question du fameux « test de Turing » de l’intelligence artificielle, où un algorithme essaye de tromper un humain au cours d’une conversation, en se faisant passer pour un autre humain.

Aujourd’hui je voudrais vous parler d’un autre domaine où les ordinateurs essayent de surpasser les humains : celui de l’improvisation musicale.

Il y a pas mal d’années – à l’époque où la musique occupait plus mes loisirs que la science – je jouais (entre autres) avec un excellent pianiste/informaticien qui m’avait parlé d’un algorithme capable d’imiter les improvisations de Charlie Parker.

Aujourd’hui j’ai voulu creuser cette question [Benjamin, si tu me lis, merci pour l’inspiration !] Lire la suite