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.

88 Comments

  1. Je ne connaissais pas du tout ces histoire sur Fermat. Merci ! 🙂

  2. Michaël Piotrkowski Reply

    David, une question m’interpelle, et je suis sur que tu as la réponse. Godel a démontré qu’un système d’axiomes arithmétique était incohérent (il existe des démonstrations de théorèmes faux) ou incomplet (il existe des théorèmes vrais indémontrables). Or sa démonstration se base elle aussi sur certains axiomes arithmétique. Donc si son théorème est démontrable (et il l’est car il l’a démontré), peut être que son théorème est faux ? En effet, rien ne nous dit que le système qu’il a utilisé n’est pas incohérent.

    Je voudrais ajouter que j’adore ce que tu fais, la pédagogie qui se dégage de ton travail est remarquable, je suis à chaque fois épaté. Merci pour tout.

    Michaël

    • En fait pour que son la preuve de son théorème soit fausse, il faudrait que toute axiomatique permettant de faire de l’arithmétique soit fausse (vu que la preuve se base sur toute axiomatique permettant de faire de l’arithmétique). Mais dans ce cas le théorème (qui dit que toute axiomatique permettant de faire de l’arithmétique est soit incomplète soit incohérente) serait quand même vrai puisque l’axiomatisation de l’arithmétique serait incohérente 😉

      N.B : on utilise en maths des axiomes sur les objets mathématiques (ceux de Peano pour l’arithmétique par exemple) mais aussi des règles logiques qui nous disent comment combiner ces axiomes entre eux. Si on imaginait des règles logiques totalement différentes, le théorème de Gödel ne tiendrait plus forcément (mais avec des règles totalement différentes il n’est pas dit que l’on puisse faire des mathématiques très intéressantes 😉 )

      P.S : j’espère que je n’ai pas embrouillé les choses, mes excuses si c’est le cas.

      • Michaël Piotrkowski Reply

        Attention, je ne me demande pas si la démonstration du théorème est fausse ou non, je sais que sa démonstration est totalement valable. Je dis simplement que sa théorie étant une théorie découlante d’un système axiomatique, il est possible que sa théorie, bien que démontrée, soit fausse (dans le cas d’un système axiomatique incohérent).

      • Une remarque : la preuve des théorèmes d’incomplétude peut être effectuée dans un système logique bien en deçà de Peano (cf http://mathoverflow.net/questions/118183/what-axioms-are-used-to-prove-godels-incompleteness-theorems#comment303770_118189 par exemple), sur lequel les théorèmes eux-mêmes ne s’appliquent pas. Puisque ces théorèmes ne s’appliquent pas, il est tout à fait possible que les systèmes axiomatiques en question soient capables de prouver leur propre cohérence ! Je n’ai pas la réponse complète, mais je sais qu’il existe de tels systèmes axiomatiques (capables de prouver leur propre cohérence). Je ne sais pas si c’est le cas des systèmes nécessaires à la preuve de Gödel.

    • Attention, le fait qu’on puisse démontrer des théorèmes faux n’est pas équivalent au fait que la théorie est incohérente.

    • J’adorerais avoir la réponse à votre remarque… Ça donne un peu le vertige mais c’est vraiment passionnant!

    • Je suis d accord avec Michael, le théorème de godel ne peut pas s appliquer a lui lui-même. Je pense que cela tient au fait que ce théorème ne s applique qu a des théorèmes mathématiques a partir desquels ont peut creer d autres théorèmes mathématiques, Or le théorème de godel ne peut pas etre la source d un autre théorème.

  3. A propos de Fermat, j’ai dévoré un livre qui s’intitule « le dernier théorème de Fermat » de « Simon Singh ». ça ne s’adresse pas spécifiquement aux pures matheux, et ça raconte l’histoire des outils mathématiques qu’il a fallut utiliser pour parvenir à la démonstration pendant 3 siècles de tentatives.

    • Excellentissisme livre, ou comment lire un pan de l’histoire des maths du point du vue d’un de ces plus célèbre « personnage » j’ai nommé « le dernier théorème de Fermat » ! Attention tout de même ce livre pourrait vous faire aimer les maths. 🙂

  4. Pingback: Les théorèmes d’incomplétude de Gödel | Science étonnante | L'Avis d'un Geek

  5. Pingback: Les théorèmes d’incompl&eac...

  6. Je viens ici poser une question à propos d’un truc qui m’as toujours fais chier à propos des théorèmes de gödel.
    C’est le fait de pouvoir ajouter l’énoncé ou son contraire quand c’est indécidable.
    Pour la géométrie euclidienne ça se comprends facilement. On ajoute l’axiome quand on est dans un espace euclidien , et son contraire pour la géométrie sphérique ou hyperbolique.
    Mais pour des trucs du genre suite de syracuse. Certains se demande si c’est indécidable. de savoir si il existe une telle suite qui ne termine pas par 4 2 1 (une suite a temps de vol infini).
    Si c’est indécidable , je ne me vois pas considérer les deux arithmétiques qui en découlerai. la conjecture est ou vrai ou fausse, soit il existe un entier qui permet d’avoir un vol infini , soit il n’existe pas. Donc ajouter A ou non A comme axiome pour moi me semble une erreur , puisque l’un des deux est vrai et l’autre faux
    Donc j’ai bien l’impression pour ce genre de problème il existe bien une valeur de vérité indépendante de la théorie utilisée.
    Le fait qu’on arrive pas à la démontrer avec un ensemble d’axiome classique à cause de son indécidabilité , ne me semble pas une raison pour dire qu’on peut ajouter a ce système d’axiome l’énoncé ou son opposé.
    Et dans ce cas là comme savoir lequel de ces deux énoncé (A ou non(A) ) est choisir (du fait de sa vérité) si on arrive pas à le démontrer dans un système d’axiome qui nous semble naturel?

    • David Reply

      Il me semble que la réponse est dans le texte !
      La valeur de vérité est liée à la notion de modèle. Si on ajoute un axiome faux d’un modèle, on passe dans un autre modèle.

      • Je précise ma question. Dans le cas du fameux axiome d’euclide c’est vrai dans le modèle du plan faux dans le modèle sphérique ou hyperbolique .
        Dans le cas des suites de syracuse , elle ne semble exister que dans un modèle , celui de notre réalité (ça commence à devenir fumeux là )
        Ce que je veux dire , c’est que je peux les calculer ces suites , les toucher. dans le modèle de notre réalité , il me semble que la conjecture est ou vrai ou fausse (même dans le cas ou elle est indécidable) . Donc ajouter le contraire de ce qui est vrai dans le modèle de notre réalité ça nous amène ou? A quelque chose qui est cohérent mathématiquement mais faux dans le réel? Euclide pouvait bien comprendre qu’il est possible de faire de la géométrie sur une sphère ou une hyperbole (même s’il ne savait pas que c’était ce que définissait son axiome ) , mais je n’arrive pas a comprendre ce que représenterai une arithmétique qui supposerait vrai quelque chose de faux dans notre monde.
        J’ai comme l’impression au fait, que ces axiomes , il y a « un bon choix a faire » . Je prends l’axiome du choix parce qu’il corresponds à ma réalité , je ne prends pas l’hypothèse du continu parce qu’il ne semble pas correspondre à ma réalité. Mon choix d’axiomatique serait peut être faux , mais seulement parce que je n’aurais pas choisi le bon axiome à un moment donné , et non pas parce que deux choix d’axiomatique différent définirait de manière égale ma réalité.
        Bref je sais que j’amalgame un peu modèle et réalité , que notre univers est peut être torique , sphérique et non pas euclidien , mais ce n’est pas trop grave , parce que un univers sphérique reste localement euclidien (ce qui donne de l’intérêt a faire de la géométrie euclidienne.)
        Je ne sais pas si j’ai bien réussi a expliciter mon malaise concernant Gödel , mais si vous pouviez d’une quelconque manière éclaircir mes idées je vous en serait grandement reconnaissant

    • Un modèle non standard de l’arithmétique peut par exemple contenir tous les entiers « standards », c’est-à-dire habituels, plus d’autres éléments, dits non-standards. C’est-à-dire qu’il existe un ensemble E, qui contient strictement les entiers naturels mais aussi d’autres éléments, et qui vérifie tous les axiomes de Peano. On peut définir la suite de Syracuse sur ce nouvel ensemble (comme E vérifie les axiomes de Peano, on peut parler d’addition, etc., même sur les éléments non-standards) et regarder si la suite « converge » toujours vers le cycle 4→2→1. Si la convergence de la suite de Syracuse est indécidable (ce que bien sûr personne ne sait actuellement), alors il existe un tel ensemble E tel que la suite converge vers le cycle, et un autre E’ tel qu’elle ne converge pas.

      Note : Un modèle non standard « explicite » de l’arithmétique est fourni par les nombres dits hypernaturels : https://en.wikipedia.org/wiki/Hyperinteger.

  7. Salut David,

    Soit une proposition P indécidable dans un système d’axiomes S. On peut construire deux nouveaux systèmes d’axiomes : S U P et S U (non-P). L’un de ces systèmes est-il nécessairement incohérent ?

  8. Bonjour,

    Une question me torture : quel serait un exemple de proposition indécidable en partant des axiomes de la physique ?

    J’ai toujours aimé penser que la totalité de la connaissance d’une théorie physique était contenue dans ses postulats, et qu’on pouvait en déduire toute vérité physique (dans le domaine d’application de la théorie en question). Je suppose donc que j’ai tort ? Il existera toujours des choses vraies non-deduisibles des postulats ? Si oui à quoi ressemblerait ces « choses » ??

    Sinon supers videos !

    • quel serait un exemple de proposition indécidable en partant des axiomes de la physique ?

      La plupart deslois dites émergentes. Par exemple les équations de Navier-Stokes ou le second principe de la thermodynamique à partir des postulats de la mécanique quantique.

    • Il me semble que c’est encore Gödel qui donne la réponse mais dans une autre de ses contributions. Gödel à Princeton avait pour ami (il en avait peu) Einstein. S’étant fait expliquer la relativité, il a construit un modèle de la relativité où le temps est circulaire.
      Lire palle Yourgrau: « Einstein/Gödel Quand deux génies refont le monde » Dunod (2005).

  9. Vous avez l’air de dire dans votre vidéo qu’une proposition indécidable est soit vrai soit fausse ( votre camembert coupé en deux). Mais j’avais toujours cru comprendre qu’une proposition indécidable est tout simplement indécidable. On peut au choix la mettre dans la catégorie vraie ou la catégorie fausse suivant le « besoin ».

    • La notion de « vrai » et « faux » dépend du modèle sous-jacent. Cependant, pour une proposition arithmétique, il y a un modèle privilégié qui est sous-entendu lorsqu’on parle de vérité, qui est celui de nos bons vieux entiers naturels. Donc « vrai » signifie « vrai pour les entiers naturels ».

      • La question sous-jacente est alors « c’est quoi les entiers naturels » ? Pour savoir tout ce qui y est vrai ou faux, il faudrait savoir comment on les définit…
        Le modèle sous-jacent induit par ZF ? Oui, mais dans ce cas on peut se poser la même question pour le modèle de ZF histoire d’avoir le plein camembert…
        Le plus petit modèle de PA ? Hmmm, maintenant c’est « plus petit » qu’il faut définir…

  10. Salut ! Tout d’abord merci pour vos travaux d’excellente qualité, je doute assez fortement qu’il soit aisé de vulgariser ce genre de notion.
    Cela dit il reste à mes yeux quelque chose d’assez flou. D’après Gödel, on peut ajouter une proposition indécidable à nos axiomes ou bien son contraire sans que cela ne perturbe la cohérence du système. Mais est-ce qu’il suffit qu’un système soit cohérent pour être « objectivement » considéré comme vrai ? Je sais bien qu’il est absurde de parler d’objectivité vis à vis de la vérité puisque vous soulignez justement que la vérité est relative au modèle qu’on étudie. Mais ce qui me dérange c’est qu’en raisonnant comme cela, il est possible de créer une infinité de systèmes d’axiome cohérent et aucun n’aurait donc plus de valeur qu’un autre.
    Je m’explique : prenons un système d’axiome quelconque, et regardons l’un de ses axiomes en particulier. Cet axiome est donc un indécidable de ce système (car sinon, la proposition que cet axiome défend serait donc démontrable en utilisant uniquement les autres axiomes, et considérer cette proposition comme un axiome serait donc inutile). Si cet axiome est indécidable, alors le remplacer par son contraire ne perturbe pas la cohérence du système. Donc il est possible de remplacer n’importe quel axiome de n’importe quel système par son contraire et à chaque fois sans créer d’incohérence. Ma question, donc : qu’est-ce qui nous permet d’affirmer que les systèmes qu’on utilise habituellement (Peano, ZFC) ont plus de valeur que les autres ? Pourquoi on utilise ces systèmes là en physique et pas d’autres pour décrire notre monde ?

    Je ne sais pas si je suis très clair. Si nier un axiome d’Euclide nous permet de fonder une autre géométrie qui permet elle aussi de décrire une réalité, est-ce qu’on peut se permettre de nier n’importe quel axiome tout en retombant sur un système qui permet lui aussi de décrire une réalité ?

    Voilà, j’ai peut-être mal compris certaines choses, merci d’avance pour votre réponse.

    • Pour l’arithmétique, voilà comment ça marche. Supposons que l’on ait une proposition A non démontrable, qui est vrai dans le modèle des entiers naturels auquel on est habitué: 0, 1, 2, 3, 5, 6, …. Supposons que maintenant on ajoute « non A » aux axiomes, bien sûr le modèle 0, 1, 2, 3, 5, 6, …. n’est pas un modèle de non A, mais non A a un modèle plus grand qui contient 0, 1, 2, 3, 5, 6, …. mais aussi des entiers non standards que je note §, ¢, © et plein d’autres. C’est dans ces entiers non standards que A devient faux. Donc je garde mes 0, 1, 2, 3, 5, 6, …. mais j’ai ajouté en plus plein d’autres entiers. Et donc à la question « qu’est-ce qui nous permet d’affirmer que les systèmes qu’on utilise habituellement (Peano, ZFC) ont plus de valeur que les autres ? » je réponds « Il a plus de valeur parce qu’il est toujours là et parce qu’il correspond à l’intuition que nous avons des entiers depuis l’école élémentaire ».

      • « vrai dans le modèle des entiers naturels auquel on est habitué »
        Tu admets l’existence d’un tel modèle ou tu es capable de le définir un peu plus formellement ?

      • …Mon sous-entendu était que non, à priori tu ne peux pas…
        …Du coup je serais curieux de voir comment tu fais 😀

      • Un modèle connu est celui de von Neumann. 0 est l’ensemble vide Ø, 1 est le singleton {Ø}, 2 est l’ensemble {Ø,{Ø}}, et ainsi de suite, si  »n » est représenté par l’ensemble  »e » alors  »n+1 » est représenté par l’ensemble  »e U {e} ». Sur cet ensemble il n’est pas trop difficile de définir les opérations de base +, * etc. On a ainsi un modèle des entiers qui est bien le modèle 0,1, 2, 3, 4, 5, 6…

      • Bien, donc tu induis un modèle de l’arithmétique par la théorie des ensembles.
        Cependant, je ne vois pas quel modèle de la théorie des ensembles tu utilises (tu parles d’ensemble vide, d’union, de singletons, mais je sais pas plus ce que c’est que +, 0 ou 3 à priori…)
        Et tu as besoin d’un tel modèle pour rendre formel ta définition du modèle de l’arithmétique, non ?

      • J’ai défini 0 comme l’ensemble vide noté Ø. 3 est 2 U {2} autrement dit {Ø,{Ø},{Ø,{Ø}}}. + est défini par récurrence.

      • …En disant ça, tu présuppose que cet ensemble existe et qu’il est unique. Qu’il soit unique je veux bien (par extensionnalité). Par contre je suis pas convaincu de son existence. Tu pourrais prouver qu’il existe, cet ensemble vide ? Sans ça, toute cette construction n’a pas tellement de sens, non ?

      • L’une des premières conséquences du schéma d’axiome de compréhension de ZF est le fait qu’il existe un et un seul ensemble qui n’a aucun élément et que l’on appelle l’ensemble vide et que l’on note Ø.

        N.B. Nous sortons du domaine des théorèmes d’incomplétude de Gödel et entrons dans la théorie des ensembles.

      • Pour utiliser le schéma d’axiome de compréhension afin d’aboutir à l’ensemble vide, il faut encore que la proposition « il existe un ensemble » soit vraie.
        Bon j’ai joué à moitié inutilement à l’idiot pour faire dire quelque chose : pour faire tout ça, on a besoin d’un modèle de ZF. Du modèle de ZF que l’on choisit dépend certains résultats. Par exemple si l’axiome des grands cardinaux ou l’axiome du choix est vrai ou non dans le modèle que l’on choisit, certains résultats peuvent ou non être vrai dans le modèle que tu présentes (et ce indépendamment de la manière dont tu réalises le modèle de Peano à partir de la théorie des ensembles). La véracité d’un tel résultat est alors indépendante du fait que le modèle contient des entiers non-standards ou non.
        NB: Je n’ai pas d’exemple de tel résultat sous la main. Selon le billet, il fut un temps où le théorème de Fermat semblait pouvoir être un tel théorème, mais visiblement plus maintenant.

  11. Bonjour,

    « Faut quand même dire que ce théorème a été abusé et déformé pour lui faire dire n’importe quoi ».
    D’ailleurs, tu fais le contresens le plus classique sur les théorèmes de Gödel en disant « il existe en mathématique des propositions vraies mais indémontrables »…

    En mathématique, on a justement recours à la méthode axiomatique pour définir la notion de « vrai ».
    L’idée est de dire « si dans le vrai tu mets les axiomes de ma théorie, alors tu y mets aussi tous ses théorèmes ». Et quand on dit que l’on formalise entièrement les mathématiques actuelles dans ZFC, on dit que la communauté mathématique accepte comme vrai ce qui est un théorème de ZFC. et comme faux les affirmations X telles que non X est un théorème de ZFC. Et pour le reste ? Ben pour le reste, on sait pas, justement…

    Mais retournons la question : c’est quoi le « vrai » ? Serais-tu capable d’en donner une définition ? Dans ta vidéo tu dis « le vrai, c’est le vrai »… Un peu circulaire comme définition…
    Le larousse me dit : « Se dit d’une affirmation conforme à la réalité ou qui n’implique pas contradiction et à laquelle l’esprit ne peut que souscrire »
    En physique, on pose comme vrai ce qui est le monde extérieur, et on mesure le vrai, et on le modélise par des maths.

    Le cinquième axiome d’Euclide est-il « vrai » ? Au début on pensais oui. D’ailleurs, il est vrai dans la mécanique Newtonienne (ou plutot la mécanique Newtonienne se base dessus). Un jour, des mathématiciens se sont dit « et si il était pas vrai ? » et on fait des théories dessus. Plus tard, Einstein a annoncé une théorie utilisant un modèle réfutant le cinquième axiome d’Euclide pour sa relativité générale.

    Le mathématicien ne se soucie pas de comment est le monde extérieur, puisqu’il imagine des mondes qui n’ont rien à voir mais qui sont cohérent. Il pose donc comme vrai ce qui sort de ses axiomes, car il ná rien d’autre pour s’appuyer dessus. Ainsi, il y a philosophiquement autant de définitions de vrai que de théories non contradictoires. Cela se résume très bien quand on dit « en arithmétique, il n’est pas vrai qu’entre deux nombre (strictement), il en existe toujours un troisième, cependant c’est vrai dans R ».

    Ainsi, quand on démontre que CH est indémontrable dans ZFC, on montre qu’il est parfaitement plausible d’avoir CH ou non CH comme « vrai ». Par le razoir d’okham, on se plait alors à mettre CH dans notre système axiomatique, et donc à travailler dans ZFC+GCH (G pour generalized). Cependant cela pose une question métamathématique, et beaucoup de mathématiciens travaillent juste dans ZFC, parcequ’il y a des modèles de ZFC dans lequel CH est faux mais qui n’ont pas l’air complètement absurde pour autant. AInsi (pour en revenir à la définition du Larousse) il est faux de dire « on ne peut qu’accepter CH ». C’est encore plus flagrant pour l’axiome du choix, ou l’axiome du tiers exclus, et beaucoup de gens travaillent sans justement parce qu’ils n’y souscrivent pas. « Existe-t-il des sous-ensembles de R non mesurables ? ». Sans l’axiome du choix, il est possible d’avoir comme vrai cette proposition…

    Ce que dit Gödel, c’est juste que peu importe comment on veut modéliser le vrai, on trouvera toujours des proposition indécidables qui amèneront le débat métamathématique « doit-on l’inclure dans le vrai ? l’exclure ? »

    Tu parles de grands cardinaux… On a toute une hiérarchie de grand cardinaux. Le zéroième, cést qu’il existe un ensemble infini. Souvent, pas trop de problème avec celui là (même si il peut entrainer des débats en philosophie des mathématiques). Le premier c’est le classique : il existe un cardinal inaccessible. Doit- on l’accepter ? Le razoir d’okham semble dire que non, mais des fois on en a besoin pour des théorèmes…
    Et pis après on en a d’autres, toute une tripotée.
    http://boolesrings.org/victoriagitman/files/2013/06/ramseydiagram.jpg

    Pour chacun, la question se pose : doit-on l’accepter ?
    Si tu remarque bien, en haut tu as « 0=1″… Eh oui, monter trop haut dans les grands cardinaux donne l’incohérence. Mais où s’arrêter ? lesquels sont vrais et lesquels sont faux ? On a pas vraiment de réponse à cette question. Du coup, à chaque fois qu’on a une preuve, on indique les axiomes qu’on utilise, qu’on sache quelle vérité on utilise…

    • Un meilleur exemple pour vraiment comprendre ce que ca veut dire indécidable : un groupe est-il abélien ? La réponse est « ca dépend, certains le sont, d’autres non »
      La proposition « pour tous a, b, ab=ba » est donc indémontrable en théorie des groupes. Elle est ni vraie, ni fausse. Ca dépend du modèle.

    • David Reply

      ***
      « Faut quand même dire que ce théorème a été abusé et déformé pour lui faire dire n’importe quoi ».
      D’ailleurs, tu fais le contresens le plus classique sur les théorèmes de Gödel en disant « il existe en mathématique des propositions vraies mais indémontrables »…

      En mathématique, on a justement recours à la méthode axiomatique pour définir la notion de « vrai ».
      ***

      Non désolé, pas du tout d’accord avec cela. C’est un commentaire juste sur la vidéo ou bien vous avez aussi lu le billet ?
      J’y explique (peut-être pas de manière assez claire) que la notion de « démontrable » est relative à un système d’axiomes alors que celle de « vrai » à un modèle. Donc je persiste à dire que « il existe en mathématique des propositions vraies mais indémontrables » est correct. Je le dis dans la vidéo, et grâce au billet je peux préciser « il existe des propositions vraies [du modèle de l’arithmétique] mais indémontrables [dans le système axiomatique de Peano] »

      ***
      Mais retournons la question : c’est quoi le « vrai » ? Serais-tu capable d’en donner une définition ? Dans ta vidéo tu dis « le vrai, c’est le vrai »… Un peu circulaire comme définition…
      ***

      Encore une fois, il me semble que vous n’avez pas lu le billet, ou alors que j’ai été vraiment peu clair car je réponds très exactement à cette question.

      • Bonjour,

        Effectivement, j’ai surtout répondu à la vidéo et pas au billet. (que j’ai trop vite passé avant de répondre).

        Vous avez raison, il y a une différence à faire entre le sémantique et le syntaxique. Le syntaxique se demande ce qui est prouvable et le sémantique se demande ce qui est vrai.
        Par le théorème de complétude de Gödel, cependant, en logique du premier ordre, ces deux notions sont les mêmes : Une proposition est démontrable pour une théorie si et seulement si elle est vrai dans tout modèle de cette théorie.

        Je persiste à dire cependant que vous n’avez précisé nulle part ce qui était « vrai » en arithmétique. En fait nulle part n’a été défini ce qu’était l’arithmétique… Cette définition est relative au modèle de l’arithmétique que l’on utilise, et quel est-il ? Un modèle de Peano ? Quelconque ?
        En mathématiques usuelles, On prend comme modèle de Peano l’ensemble des ordinaux finis dans ZFC.
        Reste de nouveau la question : qu’est-ce qui est « vrai » dans ZFC ?

        Il est de coutume d’admettre qu’il existe un modèle de ZF. Dans celui là, la formule de Gödel (de ZF) est soit vraie, soit fausse. Cependant, on ne sait pas si elle l’est ou non, justement car on a admis l’existence de ce modèle.
        Donc la formule de Gödel de ZF est une formule de l’arithmétique, elle est soit vraie, soit fausse en arithmétique, mais on ne peut pas en dire plus, car notre modèle de ZF nous a été magiquement donné…

        Ce qui me gène dans le billet, c’est la phrase suivante :
        « 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. »
        L’argumentation utilisée est basée sur le tiers exclus « G fausse -> G démontrable -> absurde donc G vraie », et cette argumentation serait tout à fait valide dans la logique inhérente de Peano, ce qui permettrais alors de donner une démonstration de G…

        En allant au dela, on pourrait se dire « prenons n’importe quel modèle M de Peano. Dans ce modèle, G est soit vraie soit fausse. G dit que G ne peux pas être démontrée par PA, et M le prouve. Donc G est vraie dans M » et hop, on a G vraie dans tout modèle de Peano, et par complétude, G est démontrable dans Peano…

        Petite note ici : comme à chaque fois que je me penche sur le théorème d’incomplétude, je bouillonne de maux de tête et je finis par ne plus être sûr de rien dans ce que je dis. Je suis un peu dans cet état en ce moment, alors je poste, je vais prendre un café, en discuter un peu, essayer de mettre les choses au clair… Ce que je dis est donc à prendre avec des pincettes…

        • David Reply

          Ok je pense qu’on est globalement d’accord alors !
          (modulo mes propres bouillonnements de tête 🙂 )
          Il y a effectivement un point sur lequel je me rends compte que je ne suis pas au clair, celle du modèle de l’arithmétique dans lequel la « réflexion de la méta-arithmétique » s’opère.
          (mais je crois que c’est lié au fait que le concept de « modèle », en tant que tel, est historiquement postérieur à Gödel, non ?)

      • Je pense que le cœur du problème est que G ne dit pas « G n’est pas démontrable » mais plutôt « la formule codée par n n’est pas démontrable », avec n le code de G. Voire quelque chose d’encore plus tricky… Du coup, si on change de modèle, n est-il toujours le code de G ?
        Sinon la théorie des modèles en tant que telle est contemporaine de la vie de Gödel, donc après l’incomplétude. Cependant, l’approche de modéliser une théorie dans une autre se retrouve dans les fondements de la géométrie d’Hilbert, dans les toutes dernières années du 19e siècle. C’est donc plus cette approche qui a donné les theoremes d’incomplétude que l’inverse…

      • La notion de modèle est connue dans les années 20. En particulier, elle sert pour définir la cohérence (la consistance en franglais). En particulier la modèle de von Neumann des entiers apparaît dans un article de 1923.

      • On peut construire formellement _sans magie_ un modèle de ZF. Comme pour les entiers, il faut un support (en général pour les modèles dits « syntaxiques », des classes d’équivalence de formules pour une relation d’équivalence adéquate), puis une interprétation des opérations: l’appartenance, l’inclusion, le singleton, etc. Ensuite on vérifie que ce modèle satisfait les axiomes de ZF.

      • On peut construire formellement _sans magie_ un modèle de ZF
        Mais tu fais ca dans quelle théorie/quel modèle ?

  12. Mes félicitations ! Je suis une bille en math, mais j’ai quand même réussi à piger des trucs (bon pas tout, j’ai trop de lacune, mais tout de même), si ce n’est pas une preuve de la qualité de votre vulgarisation, je ne sais pas ce que c’est ^^

    • Le théorème de Gödel ne repose pas sur le tiers exclus (A v ¬A) mais sur une proposition qui dit que A & ¬A est contradictoire, autrement dit ¬(A & ¬A).

  13. Francoisc Reply

    La ‘vulgarisation’ élèvée au rang « d’art »!
    Tout est dit…
    Juste quelques ‘pauses’, pour mieux savourer les passages délicats…
    Prochaines étapes: l’axiome du choix? La cryptographie quantique?
    Merci encore pour l’excellence de ce travail!

  14. Pingback: Les théorèmes d’incompl&eac...

  15. Merci pour le billet et la vidéo ! Une question : plusieurs fois, à la fois en texte et vidéo, tu mentionnes que ces théorèmes « s’appliquent aux systèmes d’axiomes récursifs qui couvrent au moins l’arithmétique des nombres naturels ».

    → Peux-tu préciser ce qui se cache derrière ce « au moins » ? Puisque cela suggère l’existence d’une « échelle », quelle est cette échelle ? Sous-questions :

    – A-t-elle un nom et quels sont ses éléments ? Des « systèmes axiomatiques » ?
    – Considérant au moins deux éléments de l’échelle, comment les ordonne-t-on ?
    – Qu’y a-t-il en dessous / au-dessus de l’arithmétique des nombres naturels ?

    • Il faut pour faire fonctionner la démonstration des théorèmes de Gödel disposer d’un certain nombre d’outils mathématiques. Ces outils sont disponibles dans certaines théories et pas dans d’autres. Donc les théorèmes de Gödel s’appliquent dans les théories qui disposent des outils nécessaires.

      Un exemple de théorie qui suffit est l’arithmétique de Peano, et une qui ne suffit pas est celle de Presburger.

      • Et je précise : Peano = « entiers naturels avec addition et multiplication » alors que Presburger = « entiers naturels avec addition seulement » (en très caricaturé).

  16. Comme d’hab, super vidéo ! Bon, pour une fois je n’ai pas appris grand chose parce que je connais bien le sujet, mais tu t’en es super bien sorti à mon goût dans tes explications (j’ai déjà tenté de vulgariser ces théorèmes, et je m’en sors rarement bien…).

    Un point de commentaire : tu parles dans le billet de l’importance de l’encodage de Gödel. Historiquement, ça ne fait absolument aucun doute. Mais fondamentalement, c’est moins clair. C’est « juste » une façon habile de procéder, mais tout encodage ferait l’affaire. Ou comme le dit l’excellent Scott Aaronson, « from a modern computer-science perspective, Gödel numbering is a barf-inducingly ugly hack! » (http://www.scottaaronson.com/blog/?p=710).

    • David Reply

      Oui d’ailleurs j’ai fait exprès de présenter deux encodage différents dans le billet et dans la vidéo !
      (je crois que je préfère celui de la vidéo : on code les symboles par des nombres à trois chiffres sans zéro, on sépare les symboles par un zéro et les formules par un double zéro)

  17. Récemment, il a été prouvé que S(7918), la durée de vie d’un castor afféré à 7918 états ne peut pas être calculée en prenant pour base de système ZFC, parce qu’il existe une machine de Turing à 7918 états dont il est impossible de démontrer avec ZFC si elle s’arrête ou pas. Du moins, c’est ce que j’ai compris de l’article en question : A relatively small Turing machine whose behavior in independant of set theory [Adam Yedidia & Scott Aaronson, 2016].
    Du coup, j’ai une question à propos de ZFC que j’ai du mal à formuler de manière rigoureuse parce-que je ne suis pas mathématicien. Dans l’article que je viens de citer, on parle d’une valeur *inconnue* (i.e., le nombre d’étapes de calcul d’une machine de Turing à 7918 états qui met le plus de temps à s’arrêter, parmi celles qui s’arrêtent, en partant d’une bande initialement remplie de 0) qui ne peut pas être déterminée avec ZFC. Mais existe-t-il des résultats mathématiques *connus*, parfaitement démontrés avec un autre système d’axiomes considéré comme consistant, mais non démontrables avec ZFC ? Autrement dit, ZFC est-il le socle de toutes les connaissances mathématiques actuelles ?

    • « Autrement dit, ZFC est-il le socle de toutes les connaissances mathématiques actuelles ? »
      Pour répondre un peu de manière pragmatique, le théorème d’incomplétude dit clairement qu’on ne peut avoir de socle à toutes les mathématiques. Actuelles ou futures.

      L’hypothèse du continu (CH) n’est pas prouvable dans ZFC. On a prouvé que si ZFC était consistant, alors ZFC+CH l’est aussi, et ZFC+notCH aussi. La question est alors de se dire « quel est le plus naturel ? ». En général, en maths on va travailler dans ZFC+GCH (pour Generalized Continuum Hypothesis) qui prouve CH.

      Se pose la même question pour les questions de grands cardinaux.

      Mais je pense que quand tu disais « consistant », tu pensais plutôt à une notion de naturel… Et là même pour l’axiome du choix les gens sont pas tous d’accord… Certains préfèrent travailler juste dans ZF. D’ailleurs les intuitionnistes réfutent aussi le tiers exclus (en théorie des types ça se fait beaucoup).

    • Il existe des axiomes de grands cardinaux que l’on peut ajouter à ZFC et qui permettent de démontrer des propositions indécidables dans ZFC
      Je cite: https://fr.wikipedia.org/wiki/Grand_cardinal
      L’affirmation de l’existence d’un tel cardinal peut donc être vu comme un renforcement (strict) de ZFC, et l’utilisation d’un tel axiome comme une mesure de ce qu’on doit ajouter à ZFC pour pouvoir démontrer tel ou tel résultat ; comme le dit Dana Scott, on peut les voir comme un moyen de préciser quantitativement la phrase « si on veut plus de résultats, il faut supposer davantage de choses »

  18. La réponse à la dernière question et non. En effet, des logiciens, des mathématiciens et des informaticiens considèrent deux alternatives à ZFC.
    1. La théorie des ensembles non bien fondés, qui est une théorie des ensembles avec un axiome d’anti-fondation.
    2. La théorie des types (notamment, la théorie des types homotopiques).
    Ce qui est sûr est qu’il existe des résultats qui se démontrent plus facilement dans ces deux théories que dans ZFC. Et bien sûr l’anti-fondation ne se démontre pas dans ZFC avec axiome de fondation.

  19. Thibault Michel Reply

    Super vidéo! Merci. Dans l’explication de ce qu’est un axiome récursif, tu suggère qu’il existe des systèmes d’axiomes récursifs avec un nombre infini d’axiomes. Comment faire dans ce cas pour montrer, en un temps fini, si une proposition quelconque fait partie ou non des axiomes ?
    Autrement dit, y a-t-il une démonstration de l’existence de systèmes infinis d’ axiomes récursifs ?

  20. La définition d’un sous-ensemble récursif d’un ensemble E est précisément qu’il existe un procédé qui dit en un temps fini si un élément donné appartient ou non au sous-ensemble. L’ensemble E tout entier est récursif. Si E est infini, E répond à la question.

  21. Une question d’un candide
    Est que ça pourrait dire que certains des problèmes du prix du millénaire pourraient ne pas être démontrables ?

    • Pourquoi pas ! Certaines conjectures sont susceptibles d’un tel sort. Cependant une analyse fine de la structure de l’énoncé de la proposition à démontrer peut permettre d’exclure cette possibilité.

  22. Si – qu’une proposition soit vraie – est – soit vrai soit faux – rend déjà la proposition indécidable alors quelle démonstration peut être vraie sachant qu’elle sera le résultat des propriétés inhérentes à ces propositions ? On voit bien que la valeur que l’on accorde à une proposition ou au résultat d’une démonstration qui l’utiliserait conditionne ce que l’on juge de cohérence d’un système . D’une certaine façon on peut même voir un jugement de valeur caché derrière chaque étape jugée correcte où apparaîtrait : ligne 1 vraie, ligne 2 vraie .. . Je crois qu’il faut au moins une proposition indubitablement vraie et toujours indubitablement vraie ( et aux yeux de qui ? ) pour qu’un seul résultat fasse loi et soit reconductible en toute nécessité . Je n’en vois pas qui ne soit pas au moins pour partie déficiente si elle doit remplir cette condition .

    • Je pense que tu rentres dans un débat très complexe (cf prédicat de vérité chez Tarski et axiomatisation en général d’un point de vue philosophie, Frege, Russel, Wittgenstein ; je pense que je peux te conseiller la lecture du Tractacus).
      L’idée du mathématicien pour éviter ce débat est d’adopter un point de vue ifthenist (« si-alors-iste ») : si mes axiomes sont vrais et que les règles de logiques que je me suis fixé sont vrais, alors le résultat de mon théorème est vrai. Il y a donc effectivement un paquet de choses prises pour acquises dès le début.
      Et le mathématicien n’est pas un Descartes : il appartient à la philosophie de décider si les axiomes choisis sont vrais ou non. Le mathématicien ne fait que le lien entre les axiomes, la logique, et les résultats, et il n’avance rien de plus que son point de vue iftheniste.
      Et le résultat de Gödel est d’autant plus frappant que même sous ce point de vue très simple cherchant à esquiver toute complication, les problèmes sont déjà là…

  23. Je ne suis pas bien sûr d’avoir bien compris ce qu’est un modèle. J’imagine qu’un modèle d’une théorie doit attribuer la valeur « vrai » à tous les axiomes de cette théorie ainsi qu’à tous les théorèmes, à minima. Il doit aussi certainement y avoir des contraintes « de cohérence ». Ce qui amène la question de l’existence d’un tel modèle : Le fait de « forcer » la valeur de chaque proposition – y compris celles qui sont indécidables – à « vrai » ou « faux » risque d’amener des incohérences dans une théorie qui au départ n’en avait pas.

    Sinon, je reviens sur ce qui vous avez écrit à propos du théorème de complétude :

    Vous dites « 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 » tout en affirmant que ça n’a rien d’évident.

    Pourtant, la contraposée de cette affirmation est :

    « Si une proposition n’est pas un théorème d’une théorie, alors il existe au moins un modèle de cette théorie dans lequel la proposition est fausse. »

    ce qui semble plutôt logique :

    Pour une théorie donnée, si une proposition n’est pas un théorème, alors deux cas sont possibles : ou bien sa négation est un théorème, ou bien elle est indécidable. Le premier cas implique que la proposition est fausse dans tous les modèles de la théorie. Le deuxième cas implique que la négation de la proposition peut être rajoutée aux axiomes de la théorie tout en gardant un système d’axiomes cohérent et donc, en prenant un modèle de ce nouveau système axiomes (ou de cette nouvelle théorie, c’est pareil) on obtient un modèle de la théorie de départ dans lequel la proposition est fausse.

    Y a-t-il une erreur dans ce raisonnement ? Ou alors justement la difficulté est-elle d’assurer l’existence d’un modèle pour n’importe quelle théorie ?

    • Je me permets d’apporter mon grain de sel car depuis que j’ai visionné la vidéo associée à cet article, il y a quelques mois, je me suis intéressé aux notions de théorie et d’incomplétude que je ne maîtrisais pas à l’époque. Je suis maintenant convaincu qu’on ne peut vraiment comprendre la notion d’énoncé (ou proposition) indécidable dans une théorie (on peut aussi dire : énoncé indépendant d’une théorie) que si on a une compréhension limpide de ce qu’est une interprétation en logique du premier ordre. Et pour cela, il faut comprendre ce qu’est une interprétation d’un symbole fonctionnel, une interprétation d’un symbole de prédicat, et ce qu’est un domaine d’interprétation. Ensuite, un modèle d’une formule est simplement une interprétation qui satisfait cette formule, c’est à dire pour laquelle cette formule est vraie au regard de la sémantique des connecteurs (et, ou, non…) et quantificateurs (il existe, pour tout). Dans cette vidéo https://youtu.be/AFLRh_rO1t4 , j’essaie d’expliquer ces notions en termes simples.
      Ceci étant dit, je ne parviens pas à trouver d’erreur dans votre raisonnement, et je n’arrive pas non plus à cerner ce qui vous pose problème lorsque vous dites « Pourtant, la contraposée… » Le mot « Pourtant » me laisse penser que quelque chose vous chiffonne, mais quoi ? Peut être que je n’ai pas les idées claires ce soir :-).
      Pour répondre à la dernière question, oui, il est difficile de déterminer si une théorie a au moins un modèle. C’est un problème indécidable, mais attention, dans un sens différent de celui d’énoncé indécidable dans une théorie. Le même mot est malheureusement utilisés pour dire deux choses très différentes. Déterminer si une théorie admet au moins un modèle est indécidable dans le sens où il n’existe aucun algorithme capable de faire cela pour toute théorie.

    • J’aime à penser qu’un modèle est un ensemble dans lesquels les axiomes de la théorie sont vrais.
      Par exemple, R, Z, Q sont des modèles de la théorie des groupes, mais N ne l’est pas. (je ne sais pas si la théorie des groupes te parle, sinon dis moi ton niveau et je pourrais chercher un autre exemple plus adapté).

      Le fait que tous les théorèmes de la théorie y soient vérifiés s’appelle justement la cohérence de la logique que l’on utilise : si les axiomes sont vrais, alors les théorèmes aussi, car notre logique n’est pas bidon !

      Il existe bien d’autres logiques que la logique du premier ordre. On a tendance à toutes les choisir cohérentes (parce que sans cohérence c’est vraiment la merde).

      La cohérence c’est donc dire que le vrai syntaxique (déduisible des axiomes) est aussi vrai sémantique (vrai dans les modèles).
      L’autre sens, (si c’est vrai dans tous les modèles, alors c’est prouvable) s’appelle la complétude (de la logique).

      Et toutes les logiques ne sont pas complètes ! La logique du second ordre (qui permet une quantification plus élargie que la logique du premier ordre), par exemple, ne l’est pas. Il y a des théories du second ordre dans lesquelles il existe un énoncé vrai mais non prouvable !

      Ton erreur se situe (je crois) dans l’interprétation d’ « indécidable ».

       » Le deuxième cas implique que la négation de la proposition peut être rajoutée aux axiomes de la théorie tout en gardant un système d’axiomes cohérent »
      Ça c’est l’indécidable sémantique : la proposition et sont contraire sont ajoutables à la théorie et les deux théories ainsi construites auront un modèle.
      L’indécidable syntaxique est : il n’existe aucune preuve de ce résultat.

      Ces deux notions d’indécidable sont équivalentes par le théorème de complétude.

      Du coup, quand tu dis « deux cas, soit on peut le prouver, soit on peut pas » c’est juste, mais quand tu extrapole « on peut pas » par « il existes des modèles qui vont bien » tu utilise de la complètude que tu cherche à démontrer…

  24. « Le fait que tous les théorèmes de la théorie y soient vérifiés s’appelle justement la cohérence de la logique que l’on utilise : si les axiomes sont vrais, alors les théorèmes aussi, car notre logique n’est pas bidon ! »
    Non cela s’appelle la ‘correction’ de la théorie, car elle dit que les raisonnements sont ‘corrects’ (donc pas bidons). La cohérence est un concept différent; Une théorie est cohérente si elle a au moins un modèle, autrement dit s’il y a au moins une proposition qui n’est pas vraie.

    • Pédagogiquement parlant, car n’oublions pas que la vidéo de départ a une vocation pédagogique, le lien entre « la théorie a au moins un modèle » et « il y a au moins une proposition qui n’est pas vraie » n’a rien d’évident.

      L’explication la plus simple (et d’ailleurs la seule) que j’aie trouvée pour établir que « la théorie a au moins un modèle » dit la même chose que « il y a au moins une proposition qui n’est pas vraie » est la suivante. Ce serait sympa de me signaler les erreurs et aspérités :-).

      Il faut bien comprendre que quand on dit qu’une proposition P est vraie dans une théorie T, cela signifie que P est conséquence logique de T, ou autrement dit que tout modèle de T est un modèle de P, ou autrement dit que l’ensemble des modèles de T, que je note M(T) est inclus dans l’ensemble des modèles de P, que je note M(P). [Ici il faut faire un dessin des ensembles M(P) et M(T), le second à l’intérieur du premier.]

      Si la théorie T a au moins un modèle, alors toute proposition P incohérente (i.e., qui n’a pas de modèle) n’est pas conséquence logique de T (n’est pas vraie dans T) parce-que M(T), qui est n’est pas vide, n’est pas inclus dans M(P), qui est vide.
      Si la théorie T est incohérente, c’est-à-dire que M(T) est vide, alors toute proposition P est conséquence logique de T (est vraie dans T) parce-que l’ensemble vide est inclus dans tous les ensembles.

      Maintenant, dans une théorie T, « La proposition P est fausse » ne dit pas la même chose que « La proposition P n’est pas vraie ». « P est fausse » dit que « non P est vrai », c’est-à-dire non P est conséquence logique de T, c’est-à-dire M(T) est inclus dans M(non P). Il y a des cas où certains modèles de T sont des modèles de P, et d’autres pas : M(T) n’est ni inclus dans M(P), ni dans M(non P). P n’est alors ni vraie, ni fausse dans T. Elle est indécidable dans T, ou autrement dit indépendante de T.

      Quand on dit qu’une théorie T « formalise » l’arithmétique standard sur les entiers naturels, cela signifie juste que la structure mathématique qui spécifie cette arithmétique, notons-là (N,+,*), est un des modèles de T. Gödel nous dit qu’il existe des propositions P qui sont vraies dans (N,+,*), ou autrement dit qui sont satisfaites par (N,+,*), mais qui sont indépendantes de T, autrement dit, il y a d’autres modèles de T qui falsifient P, i.e, dans lesquels P est fausse. Aucune théorie ne peut « cerner » parfaitement l’arithmétique standard.

      Une des clés de la compréhension est de bien distinguer « La proposition P est vraie dans le modèle M » (i.e., est satisfaite par ce modèle) et « la proposition P est vraie dans la théorie T » (i.e., est une conséquence logique de cette théorie).

  25. Bonjour,

    Je repose ma question, que j’ai déjà posée dans un autre billet, mais je ne me souviens plus lequel: pour mettre du code LaTeX dans ton billet , est-ce que tu as une plugin spécial dans ton WordPress? Merci pour la réponse, et cette fois je vais essayer de me souvenir de l’endroit où j’ai posé la question 🙂

    • David Reply

      Bonjour,

      J’écris tout simplement de la manière suivante

      $latex \theta=2$

      donc comme en LaTeX on met le code mathématique entre $, mais en ajoutant le mot « latex » après le $ qui ouvre l’expression.

      • Merci beaucoup! C’est beaucoup plus simple que dans Drupal, où j’ai du mettre une plugin. J’essaierai.

  26. Bon j’essaie ici, 1 \over 2 et voila. Tu pourras supprimer mes commentaires , c’était pour voir si ça marchait.

    • David Reply

      Il faut écrire la formule entre $ comme en latex, mais tu écris immédiatement « latex » après le premier $.

      $latex

  27. Bonjour,
    j’aurais une question de néophyte concernant la « portée de la théorie ».
    J’ai cru comprendre ici et là que quand on dit que « son théoréme démontre que quelques soit le systéme/modéle logique que l’on puisse imaginer celui-ci engendrera toujours des propriétés logiques qui ne pourront pas être démontrer uniquement à partir de lui (de ses règles de base) » on va trop loin. On fait dire plus de chose à son théoréme qu’il n’en dit réellement.
    Qu’en faites son théoréme s’applique uniquement au domaine mathématique, et en plus « seulement » au systéme avec des axiomes récursifs et suffisament « construits » pour décrire l’arithmétique. ( Je suis pas sur de bien comprendre ce que signifie récursif ici, en faites plus précisément « une phrase aprés l’autre » je pense comprendre la définition elle-même mais je vois pas du tout ce que cela impliquerai pour un systéme d’être récursif ou non !?)
    Sauf que ..probablement une mauvaise interprétation des mathématiques de ma part.. j’imaginerai volontiers que TOUT les systémes logiques imaginables puissent être traduis de façon mathématique !? Du coup le théoréme s’appliquerait également à tout les systémes logiques !?

    Aprés en lisant les commentaires, en particuliers ceux fesant référence au théoréme de complétude (que je ne connaissait pas), même si je ne saisi pas tout car malheureusement ça fait appel a des notions que je n’ai pas, j’ai l’impretion qu’il y a une autre interprétation possible du théoréme.
    A l’origine je l’interprétais en me disant, et pardonnez par avance ma vision probablement naïve …Tiens, pour simplifier imaginons que l’on soit un « dieu-mathématique » ! Donc on est là dans le néant logique, et pis on decide de créer un truc. On créer la fonction « faire 1 pas en avant », ce qui contiens dèjà en soi la notion d’avant et aprés, le 0 et le 1. A quoi l’on rajoute la notion que l’on peut toujours faire un pas en avant quelques soit la position où l’on se trouve et que cela va nous déplacer de façon ordonné : et Paf ! Ca fait des nombres entiers (comme pour les chocapics !). Et bien là, j’imaginais que, même si on n’avait même pas encore défini ce que pourrait être la multiplication, les nombres premiers et leurs propriétés singulières étaient déjà là ! Comme une conséquence logique involontaire. Et que ce que disait le théoréme c’est que certaines de ces « conséquences logiques invonlontaires » serait impossible à démontrer en utilisant uniquement la logique de création de ce « monde mathématique ». Que quelques part les démonstrations serait trop « linéaires », ou un truc du genre, pour suivre toutes de ses conséquences logiques involontaires.
    Hors en lisant les commentaires j’ai crus comprendre que l’on pouvait aussi se représenter l’affaire un peu comme des ramifications d’un arbre !? Qu’en faites les propositions indécidables ne serait pas des conséquence logiques involontaires (donc néssairement vrai avec ses axiomes à la base sauf que.. pas d’bol, c’est indémontrable) mais plutôt des endroits ou le systéme logique peut se diviser pour décrire différente alternative possible (une où la proposition est vrai une autre où elle est fausse), « d’autre monde mathématique » pour ainsi dire. Comme dans le cas de la géométrie euclidienne ou sphérique, où l’impossibilité de déduire de façon logique combien de droite paralléle à une autre passe par un point venait du fait qu’il y a plusieurs possibilités, que ce nombre n’est pas une conséquence logique direct des axiomes de base.
    Au final c’est une vision quand même bien différente ! Là les indémontrables ne sont pas une conséquence logiques nécéssairement vrai (ou fausse) mais malheureusement indémontrables ils sont des embranchements ! Des endroits où « le monde mathématique que l’on est train de s’imaginer » peut prendre une possibilité ou une autre tout en étant encore cohérent dans les deux cas ! Du coup si c’est ça le théoréme de Gödel pourrait presque se traduire par « Pour définir 1 monde et un seul un dieu-mathématique aurra toujours des choix à faire ». Il dit qu’il y aurra toujours des embranchements, des possibilités opposés restant à définir/choisir.
    Ceci n’est qu’une interprétation possible parmis tant d’autres ou bien c’est bien ça que décrivent les théoréme d’incomplétude et de complétude ?
    Et aussi, concernant ma première question sur la portée de ses théorémes, est ce que tout systéme logiques peut être « mathématiser » ? Et si oui est ce que ça n’étends pas la portée à tout les systémes logiques (sous réserve que leurs « mathématisations » aient les minima mathématique requis : récurssif, contenant l’arithmétique) ?

  28. Vos considérations sont un peu touffues, mais je répondrai à deux questions.
    1. Une proposition non démontrable correspond-elle à une proposition qui peut être soit considérée comme vraie dans un extension du système logique, soit considérée comme fausse dans une autre extension du système logique? La réponse est NON. Le théorème de Gödel dit « il y a des propositions ‘vraies’ qui ne peuvent pas être démontrées ». Si elles sont vraies on n’a pas le choix des extensions.
    2. Tout système logique est-il mathématisable ? La réponse est « Ça dépend ce qu’on appelle un système logique ».

    • Lorsque j’ai lu ce billet et vu la vidéo associée il y a un an et demi, j’étais dans le flou complet. Il me manquait plusieurs clés de compréhension, dont une essentielle, à savoir qu’un énoncé mathématique peut être vrai *indépendamment de toute théorie*. Dans les mois qui ont suivis, j’ai enquêté en lisant des cours disponibles sur le WEB et en interrogeant des spécialistes, dont la plupart n’ont pas répondu à mes mails, mais j’ai pu obtenir quand même de précieux éclaircissements. Je pense avoir réussi à comprendre certaines choses et j’ai voulu en faire profiter d’autres curieux en réalisant cette vidéo sur le sujet : https://www.youtube.com/watch?v=UlZAatzfRE8
      J’y présente les axiomes d’une théorie comme des sortes de « filtres » qui éliminent certaines interprétations indésirables d’une « soupe primordiale mathématique » contenant toutes les interprétations possibles du langage de la théorie, sans jamais pouvoir capturer *complètement* les propriétés de l’arithmétique standard. J’espère ne pas trop dire de choses qui seraient choquantes pour un spécialiste. Tous les retours sont les bienvenus.

      • Pierre Lescanne Reply

        J’aime bien votre vidéo. Elle donne un éclairage très intéressant.

  29. Pingback: Les théorèmes d'incomplétude de Gödel — Science étonnante #37 | JetBip

  30. Pingback: La pensée critique – DEO#11 – Tranxen.fr

  31. Pingback: Les théorèmes d'incomplétude de Gödel — Science étonnante #37 – MovieCS

  32. Pingback: Gödel: mon article 2) La réalité des objets immatériels, le platonisme de Gödel | Thomassonjeanmicl's Blog

Reply To Matt Cancel Reply

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.