{"id":8181,"date":"2016-12-09T17:05:40","date_gmt":"2016-12-09T16:05:40","guid":{"rendered":"https:\/\/sciencetonnante.wordpress.com\/?p=8181"},"modified":"2016-12-09T17:05:40","modified_gmt":"2016-12-09T16:05:40","slug":"theoreme-godel","status":"publish","type":"post","link":"https:\/\/scienceetonnante.com\/blog\/2016\/12\/09\/theoreme-godel\/","title":{"rendered":"Les th\u00e9or\u00e8mes d&rsquo;incompl\u00e9tude de G\u00f6del"},"content":{"rendered":"<p>Aujourd\u2019hui je m\u2019attaque \u00e0 un gros morceau : les th\u00e9or\u00e8mes de G\u00f6del !<\/p>\n<p><iframe title=\"Les th\u00e9or\u00e8mes d&#039;incompl\u00e9tude de Go\u0308del \u2014 Science \u00e9tonnante #37\" width=\"770\" height=\"433\" data-src=\"https:\/\/www.youtube.com\/embed\/82jOF4Q6gBU?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen src=\"data:image\/svg+xml;base64,PHN2ZyB3aWR0aD0iMSIgaGVpZ2h0PSIxIiB4bWxucz0iaHR0cDovL3d3dy53My5vcmcvMjAwMC9zdmciPjwvc3ZnPg==\" class=\"lazyload\" data-load-mode=\"1\"><\/iframe><\/p>\n<p>Il y aurait des pages \u00e0 \u00e9crire pour compl\u00e9ter cette vid\u00e9o, et ci-dessous je vous commente certains points et fait quelques remarques, mais bien \u00e9videmment ceci ne saurait constituer une pr\u00e9sentation exhaustive de la chose !<!--more--><\/p>\n<h3>Des propositions ind\u00e9cidables<\/h3>\n<p>Je l\u2019ai dit dans la vid\u00e9o, on ne rencontre pas a priori de propositions ind\u00e9cidables tous les jours. Et pourtant, une question relativement simple comme l\u2019hypoth\u00e8se du continu est ind\u00e9cidable dans ZFC.<\/p>\n<p>Parmi les choses ind\u00e9cidables dans Peano, mais prouvables dans des syst\u00e8mes plus fort (comme ZFC), on peut citer :<\/p>\n<ul>\n<li><a href=\"https:\/\/en.wikipedia.org\/wiki\/Goodstein%27s_theorem\" target=\"_blank\" rel=\"noopener\">Le th\u00e9or\u00e8me de Goodstein<\/a><\/li>\n<li>Le th\u00e9or\u00e8me de Paris-Harrington<\/li>\n<li>Le th\u00e9or\u00e8me des arbres de Kruskal.<\/li>\n<\/ul>\n<p>Il existe aussi toute <a href=\"https:\/\/en.wikipedia.org\/wiki\/List_of_statements_independent_of_ZFC\" target=\"_blank\" rel=\"noopener\">une liste de questions ind\u00e9cidables dans ZFC<\/a>.<\/p>\n<p>Par exemple, il existe des propositions comme <a href=\"https:\/\/en.wikipedia.org\/wiki\/Whitehead_problem\" target=\"_blank\" rel=\"noopener\">le probl\u00e8me de Whitehead<\/a> qui est une question de th\u00e9orie des groupes pas trop trop tordue, mais qui est quand m\u00eame ind\u00e9cidable de ZFC.<\/p>\n<h3>La port\u00e9e du th\u00e9or\u00e8me<\/h3>\n<p>Je l\u2019ai dit \u00e0 la fin de la vid\u00e9o, on a souvent tendance \u00e0 faire dire au th\u00e9or\u00e8me de G\u00f6del bien plus que ce qu\u2019il ne dit r\u00e9ellement. Il est notamment important de se souvenir qu\u2019il s\u2019applique aux syst\u00e8mes d\u2019axiomes r\u00e9cursifs qui couvrent au moins l\u2019arithm\u00e9tique des nombres naturels. Voyons d\u2019abord le c\u00f4t\u00e9 \u201cr\u00e9cursif\u201d, que j\u2019ai soigneusement \u00e9vit\u00e9 de traiter dans la vid\u00e9o.<\/p>\n<p>Imaginez que je fasse la chose suivante : <strong>je prends TOUTES les propositions vraies de l\u2019arithm\u00e9tique, et je cr\u00e9e un syst\u00e8me d\u2019axiomes dans lequel chacune de ces propositions est un axiome<\/strong>. J\u2019obtiens alors un syst\u00e8me d\u2019axiomes pas forc\u00e9ment tr\u00e8s int\u00e9ressant, mais qui semble violer le th\u00e9or\u00e8me de G\u00f6del, puisque toute proposition vraie de l\u2019arithm\u00e9tique y est d\u00e9montrable (eh oui, puisqu\u2019elle en est un axiome !).<\/p>\n<p>Ce syst\u00e8me d\u2019axiomes porte un nom, on l\u2019appelle <em>\u201cTrue Arithmetics\u201d<\/em>, mais outre le fait qu\u2019il est totalement inutile, il a un probl\u00e8me : si je vous donne une proposition quelconque, vous n\u2019avez pas de moyen simple de dire si oui ou non cette proposition fait partie des axiomes du syst\u00e8me. De fait un tel syst\u00e8me d\u2019axiome est totalement inutilisable !<\/p>\n<p>C\u2019est pour cela qu\u2019en pratique, on s\u2019impose de travailler avec des syst\u00e8mes d\u2019axiomes r\u00e9cursifs, c\u2019est-\u00e0-dire faits d\u2019axiomes 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.<\/p>\n<p>Le th\u00e9or\u00e8me de G\u00f6del porte justement sur les syst\u00e8mes d\u2019axiomes r\u00e9cursifs, et c\u2019est pour cela que la True Arithmetics peut y \u00e9chapper (mais vous l\u2019aurez compris, en pratique un tel syst\u00e8me n\u2019est pas tr\u00e8s utile.)<\/p>\n<p>Passons maintenant \u00e0 la seconde condition : le th\u00e9or\u00e8me de G\u00f6del porte sur les syst\u00e8mes d\u2019axiomes (r\u00e9cursifs, donc) qui axiomatisent au minimum l\u2019arithm\u00e9tique. Cela signifie que des syst\u00e8mes axiomatiques trop faibles pour couvrir l\u2019arithm\u00e9tique peuvent parfaitement \u00e9chapper au th\u00e9or\u00e8me. C\u2019est le cas notamment de <strong>l\u2019arithm\u00e9tique dite \u201cde Presburger\u201d,<\/strong> qui est celle qu\u2019on obtient en consid\u00e9rant les nombres naturels munis de l\u2019addition, mais sans la multiplication !<\/p>\n<p>La raison pour laquelle la multiplication est indispensable pour que G\u00f6del fonctionne est li\u00e9e au fait que la r\u00e9flexion de la m\u00e9ta-arithm\u00e9tique dans l\u2019arithm\u00e9tique fait justement appel \u00e0 la multiplication. Pour le voir, il faut s\u2019attarder un peu sur le codage de G\u00f6del.<\/p>\n<h3>Le codage de G\u00f6del<\/h3>\n<p>Je ne vais pas faire ici une pr\u00e9sentation parfaitement propre du codage de G\u00f6del, mais je voudrais en tracer les grandes lignes. Notez d\u2019aileurs qu\u2019il en existe plusieurs variantes, mais le r\u00e9sultat est toujours le m\u00eame.<\/p>\n<p>Pour que les maths soient un tant soit peu compr\u00e9hensibles, on utilise notre langue \u201cnaturelle\u201d (le fran\u00e7ais, par exemple) pour \u00e9noncer des axiomes, des propositions ou des th\u00e9or\u00e8mes. Et pourtant, si l\u2019on voulait, on pourrait \u00e9crire tout cela en langage purement formel, en utilisant un nombre restreint de symboles math\u00e9matiques, par exemple les symboles :<\/p>\n<p style=\"text-align:center;\">\\(\\displaystyle +, -, \\times, =, \\in, \\forall, \\rightarrow, x, y, z, \\cdots \\)<\/p>\n<p>Toute proposition math\u00e9matique peut s\u2019\u00e9crire comme une formule constitu\u00e9e de ces symboles, c\u2019est-\u00e0-dire comme une suite finie de symboles, respectant certaines r\u00e8gles.<\/p>\n<p>J&rsquo;ai pr\u00e9sent\u00e9 dans la vid\u00e9o le codage o\u00f9 on attribue un nombre \u00e0 3 chiffres (sans z\u00e9ro) \u00e0 chaque symbole, et on s\u00e9pare les symboles d&rsquo;une formule avec le z\u00e9ro, et les diff\u00e9rentes formules avec par exemple un double z\u00e9ro.<\/p>\n<p>Le codage original de G\u00f6del 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 \u00e0 15.\u00a0 Si une formule est consistu\u00e9e successivement des symboles portant les nombres $latex\u00a0<span class=\"math\">s_1, s_2, s_3, s_4,$<\/span>\u00a0etc., on peut par exemple la coder par le nombre :<\/p>\n<p style=\"text-align:center;\"><span class=\"math\">\\(\\displaystyle 2^{s_1} \\times 3^{s_2} \\times 5^{s_3} \\times 7^{s_4} \\times 11^{s_5} \\cdots\\)<\/span><\/p>\n<p>o\u00f9 l\u2019on utilise les nombres premiers dans l\u2019ordre (et vous voyez pourquoi on a absolument besoin de la multiplication !). Il existe d\u2019autres codages possibles qui sont tout \u00e0 fait \u00e9quivalent pour d\u00e9montrer le th\u00e9or\u00e8me de G\u00f6del, mais le point important est qu\u2019avec une telle proc\u00e9dure, \u00e0 toute formule on peut associer un nombre entier, et r\u00e9ciproquement \u00e0 partir de ce nombre entier, on peut reconstituer la formule de d\u00e9part (gr\u00e2ce \u00e0 l\u2019unicit\u00e9 de la d\u00e9composition en facteurs premiers).<\/p>\n<p>Maintenant qu\u2019est-ce qu\u2019une d\u00e9monstration ? C\u2019est une suite de formules qui s\u2019encha\u00eenent en respectant les r\u00e8gles de la logique. En utilisant le m\u00eame m\u00e9canisme, \u00e0 toute suite de formule (donc \u00e0 toute suite de nombres) on peut associer un nombre. Au final, <strong>gr\u00e2ce au codage de G\u00f6del, toute formule est cod\u00e9e par un nombre, et toute suite de formules est cod\u00e9e par un nombre<\/strong>.<\/p>\n<p>Pour qu\u2019une suite de formule constitue une d\u00e9monstration d\u2019une proposition, il faut que les formules s\u2019enchainent selon les r\u00e8gles de la logique, ces derni\u00e8res \u00e9tant une liste de manipulation autoris\u00e9es que l\u2019on peut faire sur des formules. Voici un exemple d\u2019une telle manipulation : si une formule commence par une double n\u00e9gation, alors on peut supprimer ces deux n\u00e9gations. La proposition <span class=\"math\">\\(\\neg\\neg P\\)<\/span> peut \u00eatre transform\u00e9e en <span class=\"math\">\\(P\\)<\/span>.<\/p>\n<p>Or une fois qu\u2019on a traduit nos formules en suite de nombres, ces r\u00e8gles de la logique se traduisent en propri\u00e9t\u00e9s purement arithm\u00e9tiques. Reprenons notre exemple de l\u2019\u00e9limination de la double n\u00e9gation en t\u00eate de formule.\u00a0En codage de G\u00f6del, mettons que le nombre associ\u00e9 au symbole de n\u00e9gation <span class=\"math\">\\(\\neg\\)<\/span> soit 7, cela se traduit par le fait que si un nombre poss\u00e8de une d\u00e9composition en facteurs premiers commen\u00e7ant par <span class=\"math\">\\(2^7 3^7\\)<\/span> alors on peut le transformer en un autre nombre obtenu en supprimant ces facteurs.<\/p>\n<p>J\u2019ai pris l\u2019exemple le plus simple, mais l\u2019id\u00e9e est l\u00e0 : dire qu\u2019une suite de formule s\u2019enchaine selon les r\u00e8gles de la logique se traduit par la satisfaction de certaines propri\u00e9t\u00e9s arithm\u00e9tiques sur le nombre \u201ccod\u00e9 de G\u00f6del\u201d qui repr\u00e9sente cette suite de formules.<\/p>\n<p>On peut alors d\u00e9finir <span class=\"math\">\\(D(x,y)\\)<\/span> qui est vraie si la suite de formules cod\u00e9e par le nombre x constitue une d\u00e9monstration de la proposition cod\u00e9e par le nombre y. Le point cl\u00e9 dans l\u2019affaire, c\u2019est que la relation <span class=\"math\">\\(D(x,y)\\)<\/span> est une relation purement arithm\u00e9tique ! En particulier le fait que les formules qui constituent la d\u00e9monstration cod\u00e9e par x s\u2019encha\u00eenent selon les r\u00e8gles de la logique se traduit sous forme de propri\u00e9t\u00e9s purement arithm\u00e9tiques.<\/p>\n<p>Dire que la proposition cod\u00e9e par le nombre y est d\u00e9montrable est alors \u00e9quivalent \u00e0 dire<\/p>\n<p style=\"text-align:center;\"><span class=\"math\">\\(C(y) = \\exists x\\ | \\ D(x,y)\\)<\/span><\/p>\n<p>On a donc bien une proposition purement arithm\u00e9tique <span class=\"math\">\\(C(y)\\)<\/span> qui est vraie si et seulement si la proposition cod\u00e9e par le nombre y est d\u00e9montrable.<\/p>\n<p>Je vous cache encore quelques d\u00e9tails sous le tapis, mais si vous voulez en savoir plus, vous trouverez sans peine des expos\u00e9s plus complets sur le codage de G\u00f6del (voir par exemple le livre de Nagel et Newman).<\/p>\n<p><a href=\"https:\/\/scienceetonnante.com\/2016\/12\/godel.jpg\"><img decoding=\"async\" class=\"aligncenter size-full wp-image-8193 lazyload\" data-src=\"https:\/\/scienceetonnante.com\/2016\/12\/godel.jpg\" alt=\"godel\" width=\"308\" height=\"499\" src=\"data:image\/svg+xml;base64,PHN2ZyB3aWR0aD0iMSIgaGVpZ2h0PSIxIiB4bWxucz0iaHR0cDovL3d3dy53My5vcmcvMjAwMC9zdmciPjwvc3ZnPg==\" style=\"--smush-placeholder-width: 308px; --smush-placeholder-aspect-ratio: 308\/499;\" \/><\/a><\/p>\n<h3>La diagonalisation<\/h3>\n<p>Je l\u2019ai expliqu\u00e9 dans la vid\u00e9o, l\u2019astuce de G\u00f6del consiste ensuite \u00e0 exhiber UNE proposition en particulier, appelons-la G, cod\u00e9e par le nombre de G\u00f6del g, telle que C(g) soit la n\u00e9gation de G. Cela signifie que G est d\u00e9montrable si et seulement si elle est fausse.<\/p>\n<p>L\u00e0 aussi je vous \u00e9pargne l\u2019argument exact, vous pouvez le trouver dans plusieurs textes comme celui de Nagel et Newman, mais il repose sur une astuce de \u201cdiagonalisation\u201d comme le fait par exemple Cantor pour trouver un nombre r\u00e9el qui ne soit pas en bijection avec l\u2019ensemble des entiers naturels.<\/p>\n<p>Un point que je n\u2019ai pas mentionn\u00e9 dans la vid\u00e9o,<strong> c\u2019est que G\u00f6del d\u00e9montre \u00e9galement que si G est d\u00e9montrable, alors sa n\u00e9gation formelle l\u2019est \u00e9galement<\/strong> (et on retrouve l\u2019esprit du paradoxe du menteur). Et c\u2019est l\u00e0 qu\u2019on se retrouve avoir le choix entre le rhume et la peste : soit la proposition est d\u00e9montrable, et sa n\u00e9gation l\u2019est aussi, et on a alors un syst\u00e8me d\u2019axiome incoh\u00e9rent; soit la proposition G n\u2019est ni d\u00e9montrable, ni r\u00e9futable, auquel car le syst\u00e8me est incomplet. Mais si nous sommes dans ce cas, alors pour autant nous sommes en mesure d\u2019affirmer que G est une proposition vraie de l\u2019arithm\u00e9tique puisqu\u2019elle est d\u00e9montrable si et seulement si elle est fausse. Mais bien \u00e9videmment la proposition non-G est une proposition fausse de l&rsquo;arithm\u00e9tique, qui est tout autant ind\u00e9cidable.<\/p>\n<p>Bref, <strong>le th\u00e9or\u00e8me de G\u00f6del nous dit qu&rsquo;il existe des propositions vraies et ind\u00e9cidables, mais tout autant de propositions fausses et ind\u00e9cidables !<\/strong><\/p>\n<h3>Compl\u00e9ter le syst\u00e8me d\u2019axiomes<\/h3>\n<p>A ce stade, on a donc construit une proposition vraie de l\u2019arithm\u00e9tique, mais ind\u00e9cidable, et ce quel que soit le syst\u00e8me \u2013 coh\u00e9rent \u2013 d\u2019axiomes qu\u2019on utilise. Tr\u00e8s bien, cela signifie alors que l\u2019on peut ajouter cette proposition \u00e0 notre syst\u00e8me d\u2019axiomes, tout comme on peut ajouter sa n\u00e9gation si cela nous chante.<\/p>\n<p>Cela peut para\u00eetre surprenant : si j\u2019ajoute G, j\u2019ajoute \u00e0 mon syst\u00e8me d\u2019axiomes une proposition vraie de l\u2019arithm\u00e9tique, pas de soucis. Mais si j\u2019ajoute sa n\u00e9gation, <strong>cela signifie que j\u2019ajoute, sans cr\u00e9er de contradiction, une proposition FAUSSE de l\u2019arithm\u00e9tique \u00e0 mon syst\u00e8me d\u2019axiomes.<\/strong> Mais un tel syst\u00e8me d\u2019axiomes n\u2019axiomatise plus l\u2019arithm\u00e9tique, alors ? Et il axiomatise quoi ???<\/p>\n<p>Pour cela, il faut se pencher sur la notion de mod\u00e8le.<\/p>\n<h3>Les mod\u00e8les<\/h3>\n<p>Dans ma vid\u00e9o, j\u2019ai fait expr\u00e8s de dire cette phrase incorrecte <em>\u201cun truc vrai, c\u2019est un truc vrai\u201d<\/em>. J\u2019ai bien insist\u00e9 sur l\u2019id\u00e9e que la notion de d\u00e9montrabilit\u00e9 n\u2019\u00e9tait pas absolue, mais relative \u00e0 un syst\u00e8me d\u2019axiome, et j\u2019ai fait comme si la notion de \u201cv\u00e9rit\u00e9\u201d \u00e9tait, elle, absolue\u2026alors qu\u2019elle ne l\u2019est pas ! Une proposition est d\u00e9montrable (ou pas) dans un syst\u00e8me d\u2019axiomes, une proposition est vraie (ou fausse) dans ce qu\u2019on appelle un mod\u00e8le : la notion de v\u00e9rit\u00e9 est elle aussi relative.<\/p>\n<p>Un mod\u00e8le, c\u2019est un \u201ctruc\u201d (je fais expr\u00e8s d\u2019\u00eatre vague) qui \u00e0\u00a0toute proposition bien construite attribue la valeur \u201cvrai\u201d ou \u201cfaux\u201d. Pr\u00e9cisons un peu cela.<\/p>\n<p>Pour construire des formules, on a vu qu\u2019il nous fallait un langage fait de symboles. Une formule est une suite de symboles qui respecte certaines \u201cr\u00e8gles de grammaire\u201d. Il existe des formules mal construites, comme la formule \u201c==+=\u201d qui utilise les symboles du langage, mais ne veut rien dire. Parmi les symboles autoris\u00e9s, les formules peuvent utiliser des variables, comme x, y, z, \u2026 auxquelles on peut faire correspondre des \u201cquantificateurs\u201d : <span class=\"math\">\\(\\forall, \\exists\\)<\/span>. Il existe des formules comme<\/p>\n<p style=\"text-align:center;\"><span class=\"math\">\\(\\displaystyle \\exists y\\ | \\ x=y+z\\)<\/span><\/p>\n<p>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\u00e9rit\u00e9 \u201cvrai\u201d ou \u201cfaux\u201d, puisque que cela va d\u00e9pendre du choix de x et z. On va appeler une \u201cproposition\u201d une formule bien construite du langage dont toutes les variables sont fix\u00e9es par un quantificateur.<\/p>\n<p>Un mod\u00e8le, c\u2019est une application qui \u00e0 toute proposition du langage assigne une valeur de v\u00e9rit\u00e9, \u201cvrai\u201d ou \u201cfaux\u201d.<\/p>\n<h3>Les mod\u00e8les de la g\u00e9om\u00e9trie<\/h3>\n<p>Revenons quelques instants sur les axiomes d\u2019Euclide. Je ne vais pas rentrer trop dans les d\u00e9tails car pour cela il faudrait les mettre sous une forme totalement formalis\u00e9e, ce qui serait assez fastidieux. Mais vous savez sans doute que parmi ces axiomes il en existe un fameux, \u201cle cinqui\u00e8me\u201d, qui dit que pour toute droite et tout point hors de cette droite, il existe une unique parall\u00e8le \u00e0 la droite passant par ce point (d\u2019ailleurs si on regarde de pr\u00e8s, cet axiome en contient en fait deux : existence et unicit\u00e9 de la droite).<\/p>\n<p>Imaginons que l\u2019on ait oubli\u00e9 cet axiome, ou qu\u2019on l\u2019ait rejet\u00e9 en pensant qu\u2019il pouvait se d\u00e9duire des 4 autres comme Euclide et d\u2019autes ont essay\u00e9 de le d\u00e9montrer. Cet axiome \u00e9tant en fait ind\u00e9pendant des 4 premiers, il est ind\u00e9cidable dans le syst\u00e8me restreint constitu\u00e9 seulement des 4 premiers axiomes. On peut donc parfaitement choisir sans cr\u00e9er de contradiction de le rajouter\u2026ou de rajouter sa n\u00e9gation ! Si on ajoute cet axiome, on obtient une axiomatisation de la g\u00e9om\u00e9trie euclidienne. Mais si on ajoute sa n\u00e9gation (ou plus pr\u00e9cis\u00e9ment la n\u00e9gation soit de son existence, soit de son unicit\u00e9) on obtient <strong>un syst\u00e8me d\u2019axiomes parfaitement coh\u00e9rent mais qui n\u2019axiomatise PAS la g\u00e9om\u00e9trie euclidienne<\/strong>, et qui axiomatise un autre mod\u00e8le : celui des g\u00e9om\u00e9tries sph\u00e9riques ou hyperbolique.<\/p>\n<p>En bon physicien, je vais comparer la notion de mod\u00e8le \u00e0 celle d\u2019univers physique dans lequel se produisent des ph\u00e9nom\u00e8nes physiques (et donc les choses y sont vraies ou fausses), et celle de syst\u00e8me d\u2019axiomes aux \u00e9quations que l\u2019on va mettre pour essayer de capturer ces ph\u00e9nom\u00e8nes, et qui sont par essence toujours des approximations qu\u2019on peut compl\u00e9ter, mais sans jamais capturer la totalit\u00e9 de la r\u00e9alit\u00e9 physique.<\/p>\n<p>Maintenant que l\u2019on a vu que si l\u2019on rencontre une proposition ind\u00e9cidable d\u2019un syst\u00e8me d\u2019axiomes, on peut ajouter soit cette proposition, soit sa n\u00e9gation au syst\u00e8me, mais que dans ce cas on se retrouve \u00e0 axiomatiser deux \u201cmod\u00e8les\u201d diff\u00e9rents, voyons ce qu\u2019il se passe si on ajoute comme axiome une proposition ind\u00e9cidable, mais fausse de l\u2019arithm\u00e9tique.<\/p>\n<h3>Les arithm\u00e9tiques non-standard<\/h3>\n<p>Si on s\u2019amuse \u00e0 faire \u00e7a, on se retrouve \u00e0 axiomatiser un truc diff\u00e9rent de l\u2019arithm\u00e9tique standard, que l\u2019on peut appeler une arithm\u00e9tique non-standard. A quoi cela peut-il ressembler ? Une proposition ind\u00e9cidable mais vraie de l\u2019arithm\u00e9tique aura forc\u00e9ment une forme du genre : pour tout entier n alors P(n) est vraie. Sa n\u00e9gation est alors : il existe n tel P(n) soit fausse. Si on ajoute un tel axiome, on axiomatise un mod\u00e8le diff\u00e9rent du mod\u00e8le standard de l\u2019arithm\u00e9tique, et contient (au moins) en plus de nos bons vieux entiers naturels un \u00e9l\u00e9ment (que l\u2019on peut appeler comme on veut, disons <span class=\"math\">\\(\\Omega\\)<\/span>) et pour lequel la propri\u00e9t\u00e9 <span class=\"math\">\\(P(\\Omega)\\)<\/span> est fausse.<\/p>\n<h3>Le th\u00e9or\u00e8me de compl\u00e9tude<\/h3>\n<p>Passons maintenant \u00e0 ce qu\u2019on appelle le th\u00e9or\u00e8me de compl\u00e9tude de G\u00f6del, et que ce dernier a d\u00e9montr\u00e9 pendant sa th\u00e8se, peu avant de sortir ses th\u00e9or\u00e8mes d\u2019incompl\u00e9tude.<\/p>\n<p>Choisissons un langage et prenons un syst\u00e8me d\u2019axiomes \u00e9nonc\u00e9 avec ce langage, c\u2019est-\u00e0-dire un ensemble de propositions que l\u2019on va d\u00e9clarer comme axiomes (on appelle parfois cela \u201cune th\u00e9orie\u201d). On peut s\u2019amuser \u00e0 d\u00e9duire des th\u00e9or\u00e8mes de cette th\u00e9orie. Pour faire tout cela, on n\u2019a pas besoin de la notion de mod\u00e8le.<\/p>\n<p>Maintenant consid\u00e9rons un mod\u00e8le de cette th\u00e9orie, c\u2019est-\u00e0-dire un mod\u00e8le form\u00e9 sur le m\u00eame langage et qui soit tel que toute proposition qui est axiome de la th\u00e9orie soit \u00e9galement une v\u00e9rit\u00e9 du mod\u00e8le. Des mod\u00e8les de ce genre, a priori on peut en imaginer des tas, il en existe certainement une infinit\u00e9.<\/p>\n<p>Ce que nous dit le th\u00e9or\u00e8me de compl\u00e9tude, et qui n\u2019a rien d\u2019\u00e9vident, c\u2019est que <strong>si une proposition donn\u00e9e est vraie dans TOUS les mod\u00e8les d\u2019une th\u00e9orie, alors elle est n\u00e9cessairement un th\u00e9or\u00e8me de cette th\u00e9orie.<\/strong> Une autre mani\u00e8re de le dire est que la v\u00e9rit\u00e9 s\u00e9mantique (celle issue des mod\u00e8les) et \u00e9quivalente \u00e0 la v\u00e9rit\u00e9 syntaxique (le fait qu\u2019une proposition se d\u00e9duise des axiomes).<\/p>\n<h3>Fermat et les axiomes<\/h3>\n<p>Quand j&rsquo;ai \u00e9crit la vid\u00e9o, je n&rsquo;\u00e9tais pas au courant d&rsquo;une subtilit\u00e9 concernant le th\u00e9or\u00e8me de Fermat et sa d\u00e9monstration par Andrew Wiles. D&rsquo;apr\u00e8s <a href=\"http:\/\/blog.computationalcomplexity.org\/2014\/01\/fermats-last-theorem-and-large.html\" target=\"_blank\" rel=\"noopener\">ce billet de blog<\/a>, la d\u00e9monstration originale de Fermat par Wiles utilise en fait un syst\u00e8me d&rsquo;axiomes plus puissant que ZFC ! Plus pr\u00e9cis\u00e9ment, il utilise les grands cardinaux. Apparemment \u00e7a ne posait pas de grands soucis aux math\u00e9maticiens, et d&rsquo;ailleurs il semble que depuis quelques ann\u00e9es on ait r\u00e9ussi \u00e0 produire <a href=\"https:\/\/www.sciencenews.org\/article\/mathematician-puts-fermats-last-theorem-axiomatic-diet\" target=\"_blank\" rel=\"noopener\">une d\u00e9monstration qui se passe de ces axiomes<\/a>, et qui n&rsquo;utilise donc que ZFC.<\/p>\n<p>Plus \u00e9tonnant, le billet sugg\u00e8re qu&rsquo;il est vraisemblable qu&rsquo;une d\u00e9monstration de Fermat puisse se faire purement dans Peano. Voir aussi <a href=\"http:\/\/www.cwru.edu\/artsci\/phil\/Proving_FLT.pdf\" target=\"_blank\" rel=\"noopener\">cet article<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Aujourd\u2019hui je m\u2019attaque \u00e0 un gros morceau : les th\u00e9or\u00e8mes de G\u00f6del ! Il y aurait des pages \u00e0 \u00e9crire pour compl\u00e9ter cette vid\u00e9o, et ci-dessous je vous commente certains points et fait quelques remarques, mais bien \u00e9videmment ceci ne saurait constituer une pr\u00e9sentation exhaustive de la chose !<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[45,4],"tags":[2,81],"class_list":{"0":"post-8181","1":"post","2":"type-post","3":"status-publish","4":"format-standard","6":"category-informatique","7":"category-mathematiques","8":"tag-arithmetique","9":"tag-logique"},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"post_mailing_queue_ids":[],"_links":{"self":[{"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/posts\/8181","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/comments?post=8181"}],"version-history":[{"count":0,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/posts\/8181\/revisions"}],"wp:attachment":[{"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/media?parent=8181"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/categories?post=8181"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/tags?post=8181"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}