Répondre à la discussion
Page 2 sur 6 PremièrePremière 2 DernièreDernière
Affichage des résultats 31 à 60 sur 178

indécidabilité de la décidabilité




  1. #31
    invite6754323456711
    Invité

    Re : indécidabilité de la décidabilité

    Citation Envoyé par Jiav Voir le message

    Ok merci je comprend mieux ta question.
    Fait nous en profiter car pour moi il n'y a pas de meta-langage. La seconde question revient en fait à la même question que la première. Hilbert pensait aussi parler de méta-mathématique :

    Sur la question plus générale de la validité de la distinction mathématique / métamathématique, Wittgenstein avait fait remarquer : « Les «métamathématiques» de Hilbert se révéleront être des mathématiques sous un déguisement » [Ludwig Wittgenstein and the Vienna Circle : 136]. Car « Ce que fait Hilbert ce sont des mathématiques et non des méta-mathématiques. C'est un type de calcul différent, comme n'importe quel autre » [ibid. 121]. « Les preuves métamathématiques de Hilbert ne sont pas un type de calcul d'une essence plus élevée, mais plus simplement un type de calcul différent : « Je peux jouer avec les pièces du jeu d'échecs selon certaines règles. Mais je peux aussi bien inventer un jeu où je joue avec les règles elles-mêmes. Les pièces de mon jeu sont cette fois les règles du jeu d'échecs, et les règles du jeu sont, disons, les lois de la logique. Dans ce cas, j'ai affaire à un jeu supplémentaire, non pas à un métajeu » »
    Patrick

    -----


  2. Publicité
  3. #32
    Jiav

    Re : indécidabilité de la décidabilité

    Citation Envoyé par ilelogique Voir le message
    pour la première, oui, c'est trivial puisque tous les axiomes d'une théorie sont démontrés ipso-facto, si on rajoute l'énoncé dans la théorie, il devient un axiome et donc avec une démonstration de longueur 1.
    Certes, mais c'est la transitivité de la consistance que je trouve non trivial à priori.

    Fait nous en profiter
    Soit une formule F indécidable dans un système d'axiome A. ilelogique veut savoir si la proposition (F indécidable dans A) peut être décidable dans A.

    Citation Envoyé par ilelogique Voir le message
    Pour la seconde pas d'accord, je ne vois pas pourquoi la décidabilité ne serait pas décidable si l'énoncé n'est pas décidable.
    Ayé je pense:
    -Prenons peano et définissions cons(peano) comme la formule codant "peano est consistent". cons(peano) est indécidable dans peano par le second théorème d'incomplétude. Rien de nouveau sous le soleil.
    -Construisons peano+cons(peano) et définissons cons(peano+cons(peano)) comme la formule codant "(peano ajouté de l'affirmation de sa consistance) est consistent". cons(peano+cons(peano)) est indécidable dans peano+cons(peano) par le second théorème. Même truc sauf que:
    -si cons(peano+cons(peano)) est indécidable dans peano+cons(peano), alors il est aussi indécidable dans peano tout court.
    The opposite of a deep truth may well be another deep truth. Information is physical.

  4. #33
    invite6754323456711
    Invité

    Re : indécidabilité de la décidabilité

    Citation Envoyé par Jiav Voir le message
    ilelogique veut savoir si la proposition (F indécidable dans A) peut être décidable dans A.
    Je ne vois toujours pas la différence avec la démarche de Gödel dans la démonstration des théorèmes d’incomplétudes : AP |- (G <--> Non Theor(G)) http://www.di.ens.fr/users/longo/Pap...completude.pdf

    Patrick

  5. #34
    Amanuensis

    Re : indécidabilité de la décidabilité

    Citation Envoyé par ilelogique Voir le message
    je pense que personne ici n'a la réponse pour le moment,
    On vous la donne, mais personne ne l'a???

    attendons Médiat
    Parce que la même réponse venant d'une autre source peut être plus valable?

    ---

    La seule interprétation est que vous n'arrivez pas à voir la réponse valide comme valide. Mais alors pourquoi poser la question sur un forum, puisque cela vous amène à la discourtoisie consistant à dire "la réponse ne me va pas parce que vous n'êtes pas une source que j'accepte", et encore pire "personne ici n'a la réponse"? Pourquoi n'allez-vous pas directement demander à une "autorité" dont vous accepterez telle quelle la réponse?
    Pour toute question, il y a une réponse simple, évidente, et fausse.

  6. #35
    Médiat

    Re : indécidabilité de la décidabilité

    Bonjour,
    Pour pouvoir parler de l'indécidabilité tel que vous le faite, il faudrait en parler dans le cadre d'une théorie capable de formaliser cette indécidabilité ; et cela ne montrerait qu'une seule chose : que la théorie ne peut pas démontrer cette indécidabilité (mais il y a d'autres méthodes).
    L'exemple de Syracuse me paraît non pertinent, car ce n'est pas une conjecture qui porte sur AP, mais sur , dont la théorie n'est pas récursive ce qui rend la formalisation impossible.
    Dans AP Syracuse est manifestement fausse.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  7. #36
    karlp

    Re : indécidabilité de la décidabilité

    HS C'est un immense plaisir que celui de vous revoir très cher Médiat !!fin du HS

  8. #37
    Amanuensis

    Re : indécidabilité de la décidabilité

    Citation Envoyé par ù100fil Voir le message
    Je ne vois toujours pas la différence avec la démarche de Gödel dans la démonstration des théorèmes d’incomplétudes : AP |- (G <--> Non Theor(G)) http://www.di.ens.fr/users/longo/Pap...completude.pdf
    Je le trouve très bien, ce texte; merci Patrick de le faire découvrir (et à son auteur de l'avoir écrit...). Il me semble qu'on y trouve pas mal de réponses...
    Pour toute question, il y a une réponse simple, évidente, et fausse.

  9. Publicité
  10. #38
    Médiat

    Re : indécidabilité de la décidabilité

    Bonjour Patrick

    Je note avec joie que je ne suis pas le seul à trouver la phrase "énoncés vrais mais indémontrables", pas acceptable.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  11. #39
    Médiat

    Re : indécidabilité de la décidabilité

    Citation Envoyé par Médiat Voir le message
    Dans AP Syracuse est manifestement fausse.
    Je corrige : dans AP Syracuse n'est manifestement pas démontrable.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  12. #40
    ilelogique

    Re : indécidabilité de la décidabilité

    Bonjour à tous,
    oui le texte a l'air intéressant je vais le lire, merci.
    Je ne cherche pas spécialement une autorité pour me répondre (j'ai d'ailleurs envoyé la question à un ancien prof), c'est juste que je ne comprends pas trop vos réponses.
    je suis d'accord sur la première trivialité, ce n'en est pas une, il faut en effet s'assurer de la consistance.
    je vais tacher de dire encore comment je vois la question :
    Prenons un énoncé F écrit dans une théorie axiomatique T cohérente, dans un langage L avec un ensemble de règles de déduction R.
    Puisqu'il semble que Godel dans sa preuve a pu formaliser dans la théorie de l'arithmétique la décidabilité d'un énoncé (celui de la complétude de l'arithmétique non ?), je rajoute donc dans mes hypothèses que la formule dec(F), qui affirme la décidabilité de F dans T, soit exprimable dans L.
    Ma question est celle de la décidabilité de dec(F) ???
    Si j'entends bien que la décidabilité de la décidabilité d'une formule n'est pas forcément exprimable dans la théorie dans laquelle cette formule est énoncée, je demande si on peut au moins imaginer qu'une telle théorie et une telle formule puisse exister ?
    Voire que dans une telle théorie on puisse énoncer dec(dec(dec...F)...)) ???

    Pour ce qui est de la conjecture de Syracuse, il me semble qu'on ne sait pas encore si elle est démontrable ou non dans l'arithmétique, et que certains pensent qu'elle est indécidable (comme celle de goodstein), la question est : prouverons-nous son indécidabilité et surtout peut-on prouver que c'est faisable ??

    On a montré par exemple que la conjecture de goodstein est indécidable dans l'arithmétique mais on l'a prouvée avec les entiers non standards. La preuve de cette indécidabilité aurait-elle pu se faire au sein de l'arithmétique ?
    S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une

  13. #41
    Médiat

    Re : indécidabilité de la décidabilité

    Citation Envoyé par ilelogique Voir le message

    Pour ce qui est de la conjecture de Syracuse, il me semble qu'on ne sait pas encore si elle est démontrable ou non dans l'arithmétique, et que certains pensent qu'elle est indécidable (comme celle de goodstein),

    On a montré par exemple que la conjecture de goodstein est indécidable dans l'arithmétique mais on l'a prouvée avec les entiers non standards. La preuve de cette indécidabilité aurait-elle pu se faire au sein de l'arithmétique ?
    Syracuse n'est pas démontrable dans AP (il existe des contre exemples), elle est soit fausse soit indécidable.
    L'indécidabilité de Goodstein est bien démontrée au sein de AP, je ne vois pas le problème
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  14. #42
    ilelogique

    Re : indécidabilité de la décidabilité

    Oui pas de problème, je suis d'accord.
    mais ma question reste :
    Prenons un énoncé F écrit dans une théorie axiomatique T cohérente, dans un langage L avec un ensemble de règles de déduction R.
    Puisqu'il semble que Godel dans sa preuve a pu formaliser dans la théorie de l'arithmétique la décidabilité d'un énoncé (celui de la complétude de l'arithmétique non ?), je rajoute donc dans mes hypothèses que la formule dec(F), qui affirme la décidabilité de F dans T, soit exprimable dans L.
    Ma question est celle de la décidabilité de dec(F) ???
    Si j'entends bien que la décidabilité de la décidabilité d'une formule n'est pas forcément exprimable dans la théorie dans laquelle cette formule est énoncée, je demande si on peut au moins imaginer qu'une telle théorie et une telle formule puisse exister ?
    Voire que dans une telle théorie on puisse énoncer dec(dec(dec...F)...)) ???
    S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une

  15. #43
    Médiat

    Re : indécidabilité de la décidabilité

    AP doit convenir, et je ne vois rien de choquant à ce qu'une théorie ne puisse démontrer lesquels de ses énoncés sont indécidables.
    Il faudrait comme je vous l'ai suggéré dans mon premier message que vous formalisiez "f est indécidable", puis que vous trouviez un raisonnement montrant que ces énoncés sont toujours démontrables ou non (cf. Gödel).
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  16. #44
    Médiat

    Re : indécidabilité de la décidabilité

    Je précise que la méthode la plus courante pour démontrer l'indécidabilité d'un énoncé est de passer par la théorie des modèles.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  17. #45
    ilelogique

    Re : indécidabilité de la décidabilité

    ben oui mais si je faisais ça il me semble que je ne viendrai pas demander ici non ? lol.
    je demandais juste si on savait quelque chose sur la décidabilité de la décidabilité ???
    Je dois malheureusement partir quelques jours, je risque de ne plus trop réagir mais vous lirai avec joie dès mon retour,
    merci !
    S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une

  18. #46
    invite6754323456711
    Invité

    Re : indécidabilité de la décidabilité

    Citation Envoyé par ilelogique Voir le message
    la décidabilité de la décidabilité ???
    Dans la suite de peut ont définir définir, votre prochain post va t-il être la logique peut elle parler d'elle-même ?

    Patrick

  19. #47
    Jiav

    Re : indécidabilité de la décidabilité

    Citation Envoyé par ilelogique Voir le message
    mais ma question reste
    Comment cela elle reste? Tu as eu deux ou trois fois la même réponse, et c'est la deuxième fois que quelqu'un te fait remarquer que tu as eu une réponse.
    The opposite of a deep truth may well be another deep truth. Information is physical.

  20. #48
    ilelogique

    Re : indécidabilité de la décidabilité

    Existe-t-il un langage L, une théorie cohérente T sur L non triviale (contenant l'arithmétique par exemple) et une formule F de L, tels qu'il existe une formule de L dec(F) exprimant la décidabilité de F dans T, de sorte que dec(F) soit elle même indécidable dans T ?
    S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une

  21. #49
    invite7863222222222
    Invité

    Re : indécidabilité de la décidabilité

    Citation Envoyé par ilelogique Voir le message
    une théorie cohérente T sur L non triviale (contenant l'arithmétique par exemple
    Le 2nd théorème de Gödel, nous dit, que pour toute théorie T contenant l'arithmétique, si elle est cohérente, cette cohérence n'est pas démontrable dans T.
    Dernière modification par invite7863222222222 ; 19/07/2013 à 10h31.

  22. #50
    Médiat

    Re : indécidabilité de la décidabilité

    Bonjour,
    Dans le fil "contributions des forumeurs", le document "arithmétique" donne l'exemple de la formule Preuve(n,m) qui exprime que n est une preuve de m (il y a l'équivalent dans toutes les démonstrations du th de Gödel). Je vous laisse écrire Dec (m) à partir de là
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  23. #51
    ilelogique

    Re : indécidabilité de la décidabilité

    N'ayant pas pour but, et surtout ne me sentant pas les compétences, de rentrer dans un tel formalisme, je demande juste si il existe, selon vous, une telle situation ?
    Il me semble, pour faire informel que dec(F) serait une formule exprimant l'existence d'un entier n et d'une suite finie de formules (Fn) qui seraient déduites les unes des autres par les règles de déduction depuis les axiomes de T telle que Fn=F ou Fn=non ; c'est à dire que dec(F) exprimerait dans T l'existence d'une preuve de F ou d'une preuve de nonF. Il me semble que Gödel a exprimé une formule du même genre dans l'arithmétique pour sa preuve.

    Ma question touche alors la décidabilité de dec(F).

    Avez-vous connaissance d'une telle situation (où l'indécidabilité de la décidabilité d'une formule serait prouvée dans une certaine théorie) ???
    S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une

  24. #52
    ilelogique

    Re : indécidabilité de la décidabilité

    Si par exemple on sait que la théorie des groupes est indécidable (dans la mesure où les énoncés décidables sont récursivement énumérables alors que l'ensemble des énoncés indécidables ne l'est pas), ça ne change rien à ma question :
    c'est bien pour ça que j'ai parlé de 3 situations (minimum !) pour un énoncé :
    - Il est décidable (lui ou sa négation est prouvable)
    - Il n'est pas décidable (on a prouvé que ni lui ni sa négation n'est prouvable, il est donc "indépendant", comme l'axiome du choix dans les ensembles par exemple ou le 5e postulat en géométrie, etc.)
    - La question de sa décidabilité n'est pas décidable (on a prouvé que dec(F) est indécidable)

    C'est bien sur cette dernière classe que porte ma question :
    Existe-t-il selon vous un langage L, une théorie cohérente T sur L non triviale (contenant l'arithmétique par exemple) et une formule F de L, tels qu'il existe une formule de L dec(F) exprimant la décidabilité de F dans T, de sorte que dec(F) soit elle même indécidable dans T ?
    S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une

  25. #53
    invite6754323456711
    Invité

    Re : indécidabilité de la décidabilité

    Citation Envoyé par ilelogique Voir le message
    Ma question touche alors la décidabilité de dec(F).
    Si on répété la même réponse comme vous répétez la même question. On codifié "la décidabilité de dec(F)" pour la ramener au langage L .... Votre troisième cas ne se ramène t-il pas à ce qu'a déjà exprimé Gödel non ? Et ceci aussi bien pour la décidabilité de la décidabilité de la décidabilité ....

    Patrick
    Dernière modification par invite6754323456711 ; 19/07/2013 à 12h57.

  26. #54
    Médiat

    Re : indécidabilité de la décidabilité

    Citation Envoyé par ilelogique Voir le message
    c'est bien pour ça que j'ai parlé de 3 situations (minimum !) pour un énoncé :
    - Il est décidable (lui ou sa négation est prouvable)
    - Il n'est pas décidable (on a prouvé que ni lui ni sa négation n'est prouvable, il est donc "indépendant", comme l'axiome du choix dans les ensembles par exemple ou le 5e postulat en géométrie, etc.)
    - La question de sa décidabilité n'est pas décidable
    Le cas 3 ne peut être une propriété intrinsèque d'une formule dans une théorie : il suffit de trouver les bons modèles pour répondre à la question.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  27. #55
    ilelogique

    Re : indécidabilité de la décidabilité

    Re bonjour,
    je me suis réveillé d'une sieste avec ceci, je vous le soumets...
    Soit T une théorie sur un langage L.
    Soit E l'ensemble des énoncés de L qui sont décidables à partir de T et CE sont complémentaire dans l'ensemble des énoncés du langage L.
    Je suppose que E est récursivement énumérable mais non récursif (c'est le cas de la théorie des groupes, et sans doute celui de l'arithmétique (?)).
    Supposons enfin qu'à toute formule close F on puisse donc associer la formule dec(F) qui affirme la décidabilité de F dans T (dec(F) affirmerait donc l'existence d'une preuve de F ou de nonF, c'est à dire d'une suite finie de formules déduites de T par les règles de déduction dont la dernière formule serait F ou nonF)

    Si dec(F) était dans E (donc si dec(F) était décidable) pour toute formule F, alors il serait possible pour toute formule F de dire en un temps fini (de façon récursive) si la formule F est décidable ou pas, dans ce cas CE serait lui aussi récursivement énumérable et donc E serait récursif, contradiction.

    Donc il existe nécessairement une formule F telle que dec(F) n'est pas décidable (dec(F) est dans CE)

    Ceci a pour conséquence que dec(F) est indépendante de T, c'est à dire qu'on peut la rajouter à T, elle ou sa négation, sans changer la cohérence éventuelle de T. En ce sens que :
    Coh(T)=> coh(T U dec(F)) et que coh(T) => coh (T U nondec(F))

    On peut ainsi décider que F est décidable ou pas (et cela sans la valider ou l'invalider).

    Pas de raison qu'on ne puisse pas ensuite recommencer cela, non ?

    La question se pose encore pour les théories récursives ou celles qui ne sont même pas récursivement énumérables...

    bon, à suivre...
    S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une

  28. #56
    invite6754323456711
    Invité

    Re : indécidabilité de la décidabilité

    Citation Envoyé par ilelogique Voir le message
    Supposons enfin qu'à toute formule close F on puisse donc associer la formule dec(F) qui affirme la décidabilité de F dans T (dec(F) affirmerait donc l'existence d'une preuve de F ou de nonF,
    Qu'est-ce qui "interdirait" de continuer le processus sur dec (dec (F)) ?

    Cette hypothèse
    Citation Envoyé par ilelogique Voir le message
    Je suppose que E est récursivement énumérable mais non récursif
    ?

    Patrick
    Dernière modification par invite6754323456711 ; 19/07/2013 à 16h55.

  29. #57
    Jiav

    Re : indécidabilité de la décidabilité

    Citation Envoyé par ilelogique Voir le message
    Je suppose que E est récursivement énumérable mais non récursif (c'est le cas de la théorie des groupes, et sans doute celui de l'arithmétique (?)).
    Pourquoi ce point d'interrogation?

    Citation Envoyé par ilelogique Voir le message
    il existe nécessairement une formule F telle que dec(F) n'est pas décidable
    Hilbert sera tout chose de l'apprendre.

    Citation Envoyé par ilelogique Voir le message
    On peut ainsi décider que F est décidable ou pas (et cela sans la valider ou l'invalider).

    Pas de raison qu'on ne puisse pas ensuite recommencer cela, non ?
    On peut même faire plus rigolo. La cohérence de Peano n'est pas démontrable dans Peano, donc on peut ajouter à Peano l'affirmation de sa non cohérence, et le résultat sera cohérent. (du moins, autant que Peano ou Peano ajouté de l'affirmation de sa cohérence)
    The opposite of a deep truth may well be another deep truth. Information is physical.

  30. #58
    ilelogique

    Re : indécidabilité de la décidabilité

    Oui je pense qu'on peut continuer avec dec(dec(F)) etc.
    Mais cela peut se faire, sans ajouter d'axiome à T et donc pas de nouvelles exigences quant- au côté récursivement énumérable il me semble.
    Si on suppose en effet que pour toute formule close f alors dec(F) existe, on a dec(F) qui est close et donc dec(dec(F)) existe aussi, etc.
    Donc il me semble que dans toute théorie pour laquelle l'ensemble des énoncés décidables est récursivement énumérable et non récursif on peut trouver une formule F dont la décidabilité n'est pas décidable etc.
    Il y aura aussi une formule dont la décidabilité de la décidabilité ne sera pas décidable...

    Pour le point d'interrogation c'est que je ne suis pas sûr que l'ensemble des énoncés décidables dans Peano soit récursivement énumérable sans être récursif (je suppose que c'est un résultat classique non ?)

    Pour Peano et sa cohérence, marrant oui, suis ok.

    Je commence à voir un peu ma réponse !
    Merci
    S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une

  31. #59
    invite6754323456711
    Invité

    Re : indécidabilité de la décidabilité

    Citation Envoyé par ilelogique Voir le message
    Mais cela peut se faire, sans ajouter d'axiome à T
    Gödel n'a t-il pas construit grâce à un processus de codification des énoncés exprimés dans le langage de la théorie T afin d'utiliser la formalisation de la théorie dans elle-même sans ajout et tout en restant dans un cadre syntaxique ? En exemple le second théorème ne codifie t-il pas la "cohérence de la théorie" comme d'un énoncé (formule close) de celle-ci ?

    Dans une théorie récursivement axiomatisable, « être une preuve » n'est-il pas décidable ?

    Patrick

  32. #60
    ilelogique

    Re : indécidabilité de la décidabilité

    Oui, et alors ?
    si "être une preuve" est sans doute décidable dans la mesure où une preuve est une suite finie (certes déduite grâce à des schémas de règles, en quantité dénombrable) ça n'empêche pas il me semble.
    je ne vois pas, dans ce que j'ai mis, en quoi il y aurait besoin de modifier T.
    S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une

Page 2 sur 6 PremièrePremière 2 DernièreDernière

Discussions similaires

  1. Popper et indécidabilité
    Par Sylvestre dans le forum Mathématiques du supérieur
    Réponses: 0
    Dernier message: 28/09/2012, 08h14
  2. indécidabilité et conjecture de Goldbach
    Par metacarambar dans le forum Mathématiques du supérieur
    Réponses: 62
    Dernier message: 12/04/2012, 17h54
  3. Indécidabilité (suite)
    Par danslideal dans le forum Mathématiques du supérieur
    Réponses: 13
    Dernier message: 20/12/2010, 17h36
  4. Décidabilité de la commutativité
    Par danslideal dans le forum Mathématiques du supérieur
    Réponses: 21
    Dernier message: 20/12/2010, 14h49