Décider de l'indécidabilité

Bonsoir,

Questions naïves:
Est-ce qu'on peut toujours décider si une proposition est démontrable,
est-ce qu'on peut toujours décider si une proposition est indécidable ?
Je pense que c'est non, mais est-ce que cela a été prouvé ?

Merci d'avance

Réponses

  • Bonsoir marco.

    Effectivement, ta première question est non seulement naïve, mais incomplète : "Une proposition" = "une proposition donnée" ou "toute proposition" ? dans le premier cas, si on a une démonstration, tu as ta réponse. dans le deuxième cas, il est évident qu'il est impossible de le savoir, car la notion de "proposition" est trop floue pour relever de la notion de démonstration.
    Car la question de base est "que veut dire démontrable ?". Est-ce que "Il existe un ensemble vide" est démontrable ?
    En fait, pour l'instant, tes deux questions sont surtout mal posées. Mais si tu veux arriver à les poser correctement, il va falloir étudier la logique, la théorie des modèles et lire les longs textes que Christophe ne va pas manquer de t'écrire. Christophe, à toi :)-D

    Cordialement
  • Bonsoir Gérard,

    Oui, je voulais dire "toute proposition" ou "une proposition quelconque" au lieu d' "une proposition donnée" et je me plaçais dans l'arithmétique de Peano, par exemple.

    Cordialement
  • En fait, dans le cas de l'arithmétique de Peano, il y a les équations diophantiennes, dont on ne peut décider si elles ont des solutions. Donc cela répond à la première question, il me semble. (Non, pas sûr...)
  • marco a écrit:
    Est-ce qu'on peut toujours décider si une proposition est démontrable ?
    Est-ce qu'on peut toujours décider si une proposition est indécidable ?
    Je pense que c'est non, mais est-ce que cela a été prouvé ?

    C'est deux fois la même question, la réponse est non, c'est démontré par le théorème de Gödel, du moins si par proposition tu signifies (par exemple) un énoncé dans Péano.

    En effet, suppose que pour toute proposition, tu puisse décider de sa décidabilité. Prends alors Péano, rajoute comme axiomes toutes les propositions P qui sont indécidables (tu sais que tu peux le faire, puisque tu connais précisément ces propositions), et boum, tu obtiens une théorie consistante qui englobe l'arithmétique mais qui n'a plus d'énoncé indécidable. Ce qui est en contradiction avec le second théorème d'incomplétude.
  • Le barbu rasé écrivait:
    Prends alors
    > Péano, rajoute comme axiomes toutes les
    > propositions P qui sont indécidables (tu sais que
    > tu peux le faire, puisque tu connais précisément
    > ces propositions), et boum, tu obtiens une théorie
    > consistante

    Ca m'étonne... Pourquoi consistante??
  • db a écrit:
    Pourquoi consistante??

    :S
    Aussi consistante que Péano, quoi. C'est juste le théorème de complétude.

    Si une proposition P est indécidable dans une théorie consistante T, alors il y a des modèles de T qui valident P (et des modèles de T qui valident non P). En particulier, ces premiers modèles valident T+P, qui est donc consistante.
  • Mmm, je vois la faille dans mon argumentaire, il faut rajouter les propositions indécidables une à une, et la question de la décidabilité de l'indécidabilité ne se pose donc plus à chaque fois dans Péano, mais dans des théories de plus en plus grosses...

    J'ai donc seulement répondu à la question : "peut-on décider de l'indécidabilité de toute proposition dans toute théorie qui contient Péano ?". Mmm...
  • Si P est indécidable, alors T+P est consistante (moyennant l'hypothèse que T est consistante), ok.
    Mais toi, tu rajoutes TOUTES les propositions indécidables. En particulier, si tu rajoutes P, tu rajoutes aussi non P, ce qui est mal barré pour rester consistant.
    Plus généralement, si P et Q sont indécidables, c'est vrai que T+P et T+Q sont consistantes, mais il n'y a aucune raison pour que T+P+Q soit consistante.
  • Yes sir.

    Une idée pour réparer l'argumentation ? Je suis à peu près sûr d'avoir lu Girard s'emporter sur le fait qu'on ne pouvait "évidemment" pas décider de l'indécidabilité dans ZF (ou plus généralement dans n'importe quelle théorie qui contient l'arithmétique), donc que la réponse est non.

    Suite à ta remarque sur le fait qu'il te semble que je rajoute à la fois P et non P, je précise mon argumentaire (qui répond bien à la question de mon message précédent) :
    1) je liste toutes les propositions
    2) je parcours ma liste, dès que je tombe sur un indécidable P, je le rajoute à ma théorie (ce qui ne change pas la notion de proposition, donc la liste, mais change la notion de décidabilité, donc quand je tomberai sur non(P) dans ma liste, il sera décidable)
    3) quand le parcours de la liste est terminé, j'ai ma théorie consistante contenant Péano et sans indécidable.
  • Nos messages se sont croisés : mon dernier message répondait à celui qui précédait celui qui précédait le mien. Celui qui précédait le mien est très clair; nous sommes donc bien d'accord.
    En fait, j'avoue que je n'ai pas réfléchi à la question de Marco : je suis tombé sur ce que tu as écrit et j'ai réagi.
    La question, c'est : l'ensemble des propositions indécidables est-il récursivement énumérable? C'est ça?
    Et Girard aurait dit quelque part (où?) que "évidemment non"; et maintenant, il faudrait réfléchir un peu (?) pour savoir pourquoi c'est une conséquence du théorème d'incomplétude?
  • Ca n'est pas plutôt l'indécidabilité du problème de l'arrêt qui permettrait de dire "évidemment non"?
  • à Marco, réponse: non aux 2 questions, preuve demain, je tape une touche ttes les 5 secondes-là tellement j'en tiens une bonne.

    Mais tu devrais essayer de le faire en exercice, c'est assez simple (pour toi, puisque post2)... quand tu sais qu'une équation diophantienne est indécidable, tu sais en fait qu'elle n'a pas de solution, donc ton post2 répond par lui-même à tes 2 questions (en supposant que les théories habituelles sont consistantes)
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • ton post3, je veux dire
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • Je crois que je me suis trompé dans l'interprétation du problème : c'est "l'ensemble des propositions indécidables est-il récursif?" et on doit arriver à montrer que non.
    Le problème "l'ensemble des propositions indécidables est-il récursivement énumérable?" est un autre problème. Et là, maintenant, je ne vois pas.
  • Ah, je n'avais pas vu le message de Christophe. Pourquoi passer la nuit à se casser la tête si Christophe nous donne la réponse demain?
    Christophe, tu veux bien en profiter pour répondre à l'autre problème : "l'ensemble des propositions indécidables est-il récursivement énumérable?" Merci.
    En fait, je n'ai pas trop la tête à ça, car juste avant, j'avais ouvert le Lambek et Scott un peu au hasard (oui, je suis désoeuvré ce soir) et j'étais tombé sur un truc qui m'a beaucoup surpris. J'ouvre un autre fil à ce sujet (je suis venu ici pour faire un peu de pub à mon fil, en particulier pour être sûr que Le barbu rasé ait envie d'y jeter un oeil - ça parle de catégories, il manque un forum "Catégories", je vais poster ça en "Les-mathematiques").
  • Il manque effectivement un forum Catégories !! Je suis allé sur ton fil, mais deufeufeu a déjà tout cassé :P.

    Je ne sais pas où Girard a écrit ça (je ne suis même pas sûr qu'il l'ait fait), je me rappelle juste que l'énonciateur de cette phrase la considérait comme une évidence. Tu as probablement raison en supposant que l'argument essentiel doit être le problème de l'arrêt ou quelque chose comme ça. Peux-tu expliciter pourquoi la question de marco peut se réécrire "l'ensemble des propositions indécidables est-il récursif?". Je ne suis pas très à l'aise avec les ensembles récursifs. Quant aux réponses de Christophe, encore faudra-t-il les comprendre...
  • Il y a une liste francaise pour les catégories : http://groups.google.fr/group/catsinfo?pli=1
  • Quant aux réponses de Christophe, encore faudra-t-il les comprendre...

    bin, pour une fois que mon post faisait 4 lignes...

    Supposons que l'ensemble des énoncés indécidables (du langage de Peano) soit récursivement énumérable. Soit P un énoncé quelconque.

    Tu lances ton premier programme pour savoir si P est indécidable (qui ne diverge (ne s'arrête pas) que ssi P n'est pas indécidable). En même tps tu en lances un deuxième qui essaie de prouver P et un troisième qui essaie de prouver nonP.

    Dans tous les cas tu auras la bonne réponse (l'un des 3 s'arrêtera et te la donnera), et avec ce procédé tu résous toutes les équations diophantiennes (ou si tu ne veux pas admettre Matiasevic, les énoncés à quantificateurs universels bornés), qui ont la gentillesse d'être telles que indécidable implique pas de solutions.

    Mais le pire c'est que Marco avait "trouvé" à son 3e post
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • Merci, Christophe.

    A est récursif si, et seulement si, A et complémentaire de A sont récursivement énumérables.

    Par exemple, l'ensemble des énoncés prouvables est récursivement énumérable, mais non récursif. Si l'ensemble des énoncés indécidables était récursivement énumérable, alors l'ensemble des énoncés prouvables serait récursif, car l'ensemble des énoncés dont la négation est prouvable est aussi récursivement énumérable (mais non récursif).
  • Merci Christophe, j'ai compris. :)-D
Connectez-vous ou Inscrivez-vous pour répondre.