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

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

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

Des propositions indécidables

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

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

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

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

La portée du théorème

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

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

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

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

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

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

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

Le codage de Gödel

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

godel

La diagonalisation

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

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

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

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

Compléter le système d’axiomes

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

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

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

Les modèles

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

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

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

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

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

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

Les modèles de la géométrie

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

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

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

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

Les arithmétiques non-standard

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

Le théorème de complétude

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

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

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

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

Fermat et les axiomes

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

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

64 réflexions sur “Les théorèmes d’incomplétude de Gödel

  1. 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.

      • 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.

  2. 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. 🙂

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

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

  5. 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?

    • 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.

  6. 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 ?

  7. 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).

  8. 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…

  9. 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 ?

      • …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.

  10. 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.

    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.

    • ***
      « 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…

      • 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 ?

  11. 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 ^^

  12. 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!

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

  14. 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é).

  15. 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).

    • 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)

  16. 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 »

  17. 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.

  18. 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 ?

  19. 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.

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s