Page 1 sur 2 1 DernièreDernière
Affichage des résultats 1 à 30 sur 37

question de logique



  1. #1
    ilelogique

    question de logique


    ------

    Bonjour,
    une théorie dont l'ensemble des énoncés décidables est récursive est-elle complète ?
    Merci,

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

  2. Publicité
  3. #2
    Médiat

    Re : question de logique

    Bonjour,

    Je ne vois aucune raison, pour qu'une théorie soit complète, il faut que tous les énoncés soient décidables.

    Peut-être faites-vous une confusion entre "énoncé décidable/indécidable" et "théorie décidable/indécidable".
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  4. #3
    ilelogique

    Re : question de logique

    Merci,
    non je ne crois pas confondre.
    En fait je me suis en effet trompé.
    Je pensais avancer cet argument pour justifier que AP n'est pas récursive mais je n'en ai pas tant besoin.
    Pour tout vous avouer, j'ose prétendre la chose suivante :
    Il existe dans l'arithmétique (AP) des énoncés dont la décidabilité n'est pas décidable.

    Je l'argumente ainsi :

    Nous savons grâce à Gödel que pour tout énoncé A de l'arithmétique (notée AP) il existe un prédicat Théo(A) qui code le fait que A soit un théorème de AP (on a «*théo(A)=il existe y tel que prov(A,Y)*») donc le prédicat «*Dec(A)=théo(A) ou théo(nonA)*» est un prédicat affirmant que A est décidable dans AP, il devrait être codable aussi. Or si j'appelle E l'ensemble des énoncés décidables et G celui des énoncés indécidables dans AP alors E étant récursivement énumérable mais non récursif, on a G qui n'est pas récursivement énumérable (sinon E serait récursif), donc si pour toute formule A on a Dec(A) qui est dans E alors, si la décidabilité au sens de Gödel implique celle au sens de Turing (ce qu'on peut raisonnablement croire...), il existe un algorithme (une machine de Turing) qui s'arrête à coup sûr et décide pour chaque formule A de la validité de Dec(A), si bien qu'on saurait pour toute formule A si elle est décidable ou non, ce qui est contradictoire avec l'incomplétude de la théorie, donc je déduis qu'il existe une formule A telle que Dec(A) est dans G, c'est à dire l'existence d'une formule dont la décidabilité n'est pas décidable... Ceci impliquerait bien sûr qu'il y aurait une formule dont la décidabilité de la décidabilité ne serait pas décidable et donc l'existence, par induction, d'une chaine infinie...

    Non ?
    S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une

  5. #4
    Médiat

    Re : question de logique

    Citation Envoyé par ilelogique Voir le message
    on saurait pour toute formule A si elle est décidable ou non, ce qui est contradictoire avec l'incomplétude de la théorie
    Je ne comprends pas ce point.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  6. A voir en vidéo sur Futura
  7. #5
    ilelogique

    Re : question de logique

    Oui vous avez raison, c'est plutôt contradictoire avec le fait que E n'est pas récursif, c'est ça ?
    S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une

  8. #6
    ilelogique

    Re : question de logique

    Ou bien qu'est-ce qui ne va pas dans la preuve ?
    S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une

  9. Publicité
  10. #7
    S321

    Re : question de logique

    Je suis assez d'accord avec Mediat, lorsque vous dites : "si bien qu'on saurait pour toute formule A si elle est décidable ou non, ce qui est contradictoire avec l'incomplétude de la théorie"
    c'est ce que vous cherchez à démontrer, vous ne pouvez pas l'utiliser.

    L’incomplétude de la théorie fait qu'il existe au moins une formule A qui n'est pas décidable. Ce que vous dites là c'est que c'est alors contradictoire de dire que que la décidabilité de toute formule est décidable, ie que si on a une formule B alors Dec(B) est décidable. Mais ce n'est pas contradictoire, cet argument n'est pas suffisant.
    On pourrait tout à fait imaginer qu'il existe une formule A indécidable et que pour tout B, Dec(B) est décidable. Du moment que A n'est pas de la forme Dec(B), mais ça n'est pas un problème.
    Wir müssen wissen, wir werden wissen.

  11. #8
    ilelogique

    Re : question de logique

    Oui il ne faut pas dire "incomplétude" mais "non récursif" ?
    En effet si Dec(A) est dans E pour tout A, alors il y aurait un algorithme décidant (en temps fini) pour toute formule F si F est dans E ou dans G, et E et G seraient récursifs, ce qui, je crois, est faux dans AP, non ?

    Et on a bien qu'il existe un énoncé dont la décidabilité n'est pas décidable, non ??
    S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une

  12. #9
    S321

    Re : question de logique

    Citation Envoyé par ilelogique Voir le message
    En effet si Dec(A) est dans E pour tout A, alors il y aurait un algorithme décidant (en temps fini) pour toute formule F si F est dans E ou dans G
    Encore une fois ce "alors" c'est ce que vous cherchez à démontrer, ça n'est pas du tout évident a priori.

    Essayez peut-être d'écrire une vraie démonstration plutôt qu'un assemblage d'idées mises côte à côte, le problème de vos démonstrations c'est qu'elles sont très difficiles à lire et à comprendre de quoi vous parlez et où vous allez. J'ai peur de vous dire des bêtises et en tout cas de ne pas pouvoir vous aider beaucoup si vous ne rédigez pas un peu mieux ce que vous essayez de montrer.
    Wir müssen wissen, wir werden wissen.

  13. #10
    ilelogique

    Re : question de logique

    Bonjour,
    je ne crois pas que le "alors" dont vous parlez soit ce que je souhaite prouver.
    j'essaie de redire :
    je me place dans une théorie contenant l'arithmétique AP.
    J'appelle E l'ensemble des énoncés décidables et G celui des énoncés indécidables. On sait que E est récursivement énumérable mais non récursif, donc G n'est pas récursivement énumérable.
    Pour tout énoncé F, je note dec(F) = théo(F) ou théo(nonF). Ce prédicat est codable au sens de Gödel puisqu'on sait que théo(F) l'est.
    Je suppose que pour tout F on a dec(F) qui est dans E.
    Dans ce cas, en supposant que la décidabilité de Gödel coïncide avec celle de Turing, il existe un algorithme qui peut dire en un temps fini pour tout énoncé F si dec(F) est vrai ou faux, cet algorithme dira donc pour tout énoncé F si il est dans E ou dans G.
    Donc G serait récursivement énumérable.
    Contradiction.
    Donc il existe un énoncé F tel que dec(F) est dans G.
    Il existe ainsi un énoncé dont la décidabilité n'est pas décidable.

    Qu'est-ce qui ne va pas dans ce que je dis svp ?
    S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une

  14. #11
    invite6754323456711
    Invité

    Re : question de logique

    Citation Envoyé par ilelogique Voir le message
    Bonjour,
    une théorie dont l'ensemble des énoncés décidables est récursive est-elle complète ?
    [HS]
    Comment traduis-tu ces réflexions, portant sur un domaine loin du sens commun, dans les spectacles basés sur le principe "Une démarche scientifique ne peut pas exister sans pensée critique" ?
    [/HS]

    Patrick

  15. #12
    maccadore

    Re : question de logique

    Par définition ce sont des énoncés impossibles à démontrer ainsi que leurs négations. Mais cette notion
    est toujours relative à un système de démonstrations (ou système formel), et il ne faut pas la
    confondre avec celle de problèmes indécidables qui elle, est absolue.
    Une fonction est calculable s'il existe une façon finie de la décrire qui permette effectivement d'en
    calculer toutes les valeurs.
    Lorsqu'on connait un algorithme pour résoudre un problème il est alors naturel de chercher à le généraliser (i.e. être plus tolérant dans les jeux de données acceptés).
    A l'inverse quand on sait qu'un problème est indécidable, on cherche alors à en trouver des sous-problèmes décidables.

  16. Publicité
  17. #13
    invite6754323456711
    Invité

    Re : question de logique

    Citation Envoyé par maccadore Voir le message
    Par définition ce sont des énoncés impossibles à démontrer ainsi que leurs négations. ...
    J'ai déjà lu cela quelque part avec les mêmes caractéristiques de présentation lié à un couper/coller sans reformatage

    Patrick

  18. #14
    ilelogique

    Re : question de logique

    Pour répondre à U sans fil : j'ai reconnu à mon deuxième message que je faisais erreur, merci de juger, svp, ma dernière proposition de preuve du fait qu'"il existe un énoncé dont la décidabilité n'est pas décidable", et non mes conneries, certes nombreuses...
    Non ?
    S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une

  19. #15
    ilelogique

    Re : question de logique

    Je ne crois pas dire tant de choses fausses dans mes spectacles, je tâche de me documenter au préalable, la preuve... Venez y assister pour juger ! Je vous invite tous de bon cœur le 22 mars à la BNF !!
    S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une

  20. #16
    invite6754323456711
    Invité

    Re : question de logique

    Citation Envoyé par ilelogique Voir le message
    Je ne crois pas dire tant de choses fausses dans mes spectacles, je tâche de me documenter au préalable, la preuve... Venez y assister pour juger ! Je vous invite tous de bon cœur le 22 mars à la BNF !!
    C'est un malentendu, ma question n'était pas une critique, mais un vrai intérêt sur ce genre d'exercice. Si vous passez dans le sud ouest de la France je viendrais avec grand plaisir.

    Patrick

  21. #17
    Deedee81
    Modérateur

    Re : question de logique

    Salut,

    Citation Envoyé par ilelogique Voir le message
    Je vous invite tous de bon cœur le 22 mars à la BNF !!
    Je ne savais pas qu'on organisait des spectacles à la Banque Nationale de France
    (bref, c'est quoi la BNF ?)
    Keep it simple stupid

  22. #18
    Amanuensis

    Re : question de logique

    Bibliothèque Nationale de France? Spectacle sur le site de la Bibliothèque François Mitterrand à Paris? (En tout cas, c'est comme ça qu'un parisien comprend "à la BNF"...)

    (Et il me semble qu'il n'y a pas de Banque Nationale de France, c'est juste "Banque de France"...)
    Dernière modification par Amanuensis ; 25/02/2014 à 07h03.
    Pour toute question, il y a une réponse simple, évidente, et fausse.

  23. Publicité
  24. #19
    ilelogique

    Re : question de logique

    Bonjour,
    oui c'est bien à la bibliothèque : http://www.apmep-iledefrance.org/
    Pas de souci, U100fil, avec plaisir, je peux vous tenir au courant par mail si vous le souhaitez...

    Sinon, je vous remets ma dernière proposition (désolé d'insister mais je dois savoir, pour un article, si je peux ou non affirmer qu'il existe des énoncés dont la décidabilité n'est pas décidable...) :
    je me place dans une théorie contenant l'arithmétique AP.
    J'appelle E l'ensemble des énoncés décidables et G celui des énoncés indécidables. On sait que E est récursivement énumérable mais non récursif, donc G n'est pas récursivement énumérable.
    Pour tout énoncé F, je note dec(F) = théo(F) ou théo(nonF). Ce prédicat est codable au sens de Gödel puisqu'on sait que théo(F) l'est.
    Je suppose que pour tout F on a dec(F) qui est dans E.
    Dans ce cas, en supposant que la décidabilité de Gödel coïncide avec celle de Turing, il existe un algorithme qui peut dire en un temps fini pour tout énoncé F si dec(F) est vrai ou faux, cet algorithme dira donc pour tout énoncé F si il est dans E ou dans G.
    Donc G serait récursivement énumérable.
    Contradiction.
    Donc il existe un énoncé F tel que dec(F) est dans G.
    Il existe ainsi un énoncé dont la décidabilité n'est pas décidable.

    Qu'est-ce qui ne va pas dans ce que je dis svp ?
    S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une

  25. #20
    Deedee81
    Modérateur

    Re : question de logique

    Citation Envoyé par Amanuensis Voir le message
    Bibliothèque Nationale de France? Spectacle sur le site de la Bibliothèque François Mitterrand à Paris? (En tout cas, c'est comme ça qu'un parisien comprend "à la BNF"...)

    (Et il me semble qu'il n'y a pas de Banque Nationale de France, c'est juste "Banque de France"...)
    Merci,
    (je devrais aller plus souvent en France )
    Keep it simple stupid

  26. #21
    S321

    Re : question de logique

    J'arrive beaucoup mieux à lire la preuve maintenant et elle me semble tout à fait valable, je ne vois plus de point douteux.
    Wir müssen wissen, wir werden wissen.

  27. #22
    Médiat

    Re : question de logique

    Bonjour,

    Citation Envoyé par ilelogique Voir le message
    il existe un algorithme qui peut dire en un temps fini pour tout énoncé F si dec(F) est vrai ou faux
    Etes-vous en train de dire que AP est décidable ?
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  28. #23
    Deedee81
    Modérateur

    Re : question de logique

    Bonjour,

    A lire :
    http://www.pourlascience.fr/ewb_page...lcul-32661.php

    Très intéressant. La méthode permet par exemple de calculer ce qui n'est pas nécessairement calculable par une machine de Turing (par exemple le problème de l'arrêt). Bien entendu Delahaye explique pourquoi.

    Très instructif.
    Keep it simple stupid

  29. #24
    ilelogique

    Re : question de logique

    Bonsoir,
    désolé, je n'avais pas vu que vous aviez répondu.

    Pour répondre à Médiat, on sait que E (l'ensemble des énoncés décidables de AP) est récursivement énumérable mais non récursif (donc E et à fortiori AP n'est pas décidable), donc il me semble que ça veut dire qu'il existe une machine de Turing qui pour tout énoncé dira après un temps fini si l'énoncé est dans E ou pas.

    non ?

    Qui ne valide pas ma preuve svp ?
    merci.

    Pour l'article cité, oui, ça a l'air intéressant mais on ne peut pas lire la suite sans acheter...
    S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une

  30. Publicité
  31. #25
    Médiat

    Re : question de logique

    Bonsoir,

    Citation Envoyé par ilelogique Voir le message
    on sait que E (l'ensemble des énoncés décidables de AP) est récursivement énumérable
    Vous avez une référence pour ce théorème ?

  32. #26
    Médiat

    Re : question de logique

    Bonjour,

    Citation Envoyé par Médiat Voir le message
    Vous avez une référence pour ce théorème ?
    Ne cherchez pas, j'ai lu trop vite (du coup c'est moi qui ai fait une confusion entre décidabilité logique et algorithmique).
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  33. #27
    ilelogique

    Re : question de logique

    Au quai,
    pas de sous si...
    Mais donc, quid ?
    validez-vous ou pas ?
    qu'apportez-vous contre ?
    ou bien est-il vrai ce que je propose ?
    Merci.
    S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une

  34. #28
    ilelogique

    Re : question de logique

    Il existe des énoncés dont la décidabilité n'est pas décidable...
    Ou bien pas ?
    S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une

  35. #29
    ilelogique

    Re : question de logique

    Excusez-moi d'insister, mais si personne ne me répond, dois-je en conclure :
    - Que vous êtes d'accord avec ma proposition ?
    - Que vous êtes en train de chercher à la réfuter ?
    - Que ça ne vous parait pas intéressant ?

    je la remets, au cas où... :


    On se place dans une théorie contenant l'arithmétique AP.
    J'appelle E l'ensemble des énoncés décidables et G celui des énoncés indécidables. On sait que E est récursivement énumérable mais non récursif, donc G n'est pas récursivement énumérable.
    Pour tout énoncé F, je note dec(F) = théo(F) ou théo(nonF). Ce prédicat est codable au sens de Gödel puisqu'on sait que théo(F) l'est.
    Je suppose que pour tout F on a dec(F) qui est dans E.
    Dans ce cas, en supposant que la décidabilité de Gödel coïncide avec celle de Turing, il existe un algorithme qui peut dire en un temps fini pour tout énoncé F si dec(F) est vrai ou faux, cet algorithme dira donc pour tout énoncé F si il est dans E ou dans G.
    Donc G serait récursivement énumérable.
    Contradiction.
    Donc il existe un énoncé F tel que dec(F) est dans G.
    Il existe ainsi, dans AP, un énoncé dont la décidabilité n'est pas décidable.
    S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une

  36. #30
    ilelogique

    Re : question de logique

    Je ne comprends pas,
    quelqu'un peut-il me dire, svp, pourquoi personne ne répond à ma question ?
    elle n'en est pas digne ??
    Merci,
    S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une

Page 1 sur 2 1 DernièreDernière

Discussions similaires

  1. Question de logique
    Par xgamma dans le forum Science ludique : la science en s'amusant
    Réponses: 1
    Dernier message: 10/04/2011, 14h53
  2. Question de logique
    Par vc74 dans le forum Mathématiques du supérieur
    Réponses: 16
    Dernier message: 10/10/2009, 18h27
  3. Question de logique :
    Par Korzibsk dans le forum Epistémologie et Logique (archives)
    Réponses: 5
    Dernier message: 21/03/2009, 19h57
  4. question de logique
    Par jbel dans le forum Électronique
    Réponses: 3
    Dernier message: 30/06/2006, 07h29