Théorème d'incomplétude de Gödel
Page 1 sur 2 1 DernièreDernière
Affichage des résultats 1 à 30 sur 45

Théorème d'incomplétude de Gödel



  1. #1
    inviteafa56da9

    Théorème d'incomplétude de Gödel


    ------

    Je dois avouer que je pose ma question ici en espérant que Mediat passera dans le coin !

    Jusqu'à hier, il était clair pour moi que le (premier) théorème d'incomplétude disait que dans toute théorie qui va bien (réc. énum. et "contenant" l'arithmétique), il existait des énoncés indémontrables, i.e. on a des modèles dans lesquels est vrai et d'autres dans lesquels il est faux.

    J'ai feuilleté hier un bouquin sur Gödel dans lequel il était énoncé sous la forme "si la théorie est cohérente, il existe des énoncés VRAIS indémontrables". Ma question porte sur la démonstration de ceci qui me fait me poser des questions : on construit un énoncé E qui dit "je suis indémontrable". Jusque là tout va bien. Mais ensuite, l'auteur écrit :
    - Si E est démontrable, alors sa négation est vraie.
    - Mais si non(E) est vrai, alors E est faux.
    - Donc si E est démontrable, alors E est faux.
    - Mais si E est démontrable, alors E est vrai !
    - Donc si on suppose la cohérence de la théorie, E ne peut pas être démontrable.
    - Mais E dit qu'il n'est pas démontrable, donc E est vrai.

    Dans ce raisonnement, j'ai l'impression que la notion de vérité ne fait pas appel à un quelconque modèle, ce qui me trouble. Mais un énoncé vrai dans tous les modèles, il est pas démontrable ?

    Bon, en gros, je me suis un peu embrouillé le cerveau avec cette histoire, et moi qui croyais que le théorème d'incomplétude de Gödel n'avait plus de secret pour moi, et bien ça me vexe . J'appelle donc a l'aide pour me sortir de ce mauvais pas !

    Pour info, le bouquin en question : "Incompleteness: The Proof and Paradox of Kurt Gödel", de Rebecca Goldstein.

    -----

  2. #2
    Médiat

    Re : Théorème d'incomplétude de Gödel

    Citation Envoyé par BGT Voir le message
    Je dois avouer que je pose ma question ici en espérant que Mediat passera dans le coin !
    Dès que je vois le nom de Gödel je sors mon clavier

    Citation Envoyé par BGT Voir le message
    Jusqu'à hier, il était clair pour moi que le (premier) théorème d'incomplétude disait que dans toute théorie qui va bien (réc. énum. et "contenant" l'arithmétique), il existait des énoncés indémontrables, i.e. on a des modèles dans lesquels est vrai et d'autres dans lesquels il est faux.
    Parfaitement correct.

    Citation Envoyé par BGT Voir le message
    J'ai feuilleté hier un bouquin sur Gödel dans lequel il était énoncé sous la forme "si la théorie est cohérente, il existe des énoncés VRAIS indémontrables".
    Formulation "marketing" absolument inacceptable

    Citation Envoyé par BGT Voir le message
    Ma question porte sur la démonstration [...]
    Le coeur de la démonstration de Gödel est que l'on peut coder les propositions et leur démonstration avec des entiers (donc dans le modèle standard de l'arithmétique), tant que l'on ne fait pas apparaître ce point, on ne fait pas des mathématiques (modestement, dans mon document sur l'arithmétique, je donne une explication de la preuve de Gödel, sans cacher les points clé).

    Citation Envoyé par BGT Voir le message
    Pour info, le bouquin en question : "Incompleteness: The Proof and Paradox of Kurt Gödel", de Rebecca Goldstein.
    Je me souviendrais de ne pas le conseiller

    Je viens de voir une critique sur le net :
    Citation Envoyé par Solomon Feferman
    Even Rebecca Goldstein’s book, whose laudable aim is to provide non-technical expositions of the incompleteness theorems (there are two) for a general audience and place them in their historical and biographical context, makes extravagant claims and distorts their significance [...]
    Those who are fascinated by Gödel’s theorems--and the general idea of limits to what we can know—may still hunger for a more universal view of their possible significance. But they should not be satisfied with Goldstein’s ‘vast and messy’ goulash, hers is not a recipe for true understanding
    http://math.stanford.edu/~feferman/
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  3. #3
    inviteafa56da9

    Re : Théorème d'incomplétude de Gödel

    Merci Mediat ! Voilà le point clé de mon incompréhension (je graisse) :

    Citation Envoyé par Médiat Voir le message
    Le coeur de la démonstration de Gödel est que l'on peut coder les propositions et leur démonstration avec des entiers (donc dans le modèle standard de l'arithmétique)
    Le "vrai" signifie donc bien "vrai dans tel modèle" ! J'aurais pu (dû ?) trouver moi-même. Je précise que Rebecca Goldstein esquisse une ébauche de preuve assez détaillée, et que ce que j'ai raconté n'est qu'en introduction d'une partie plus technique, pour faire comprendre l'idée. [EDIT] Je précise ça par rapport à la réflexion de Mediat disant que tant qu'on ne parle pas du fait qu'on utilise des entiers, on ne fait pas de mathématiques. Dans le bouquin, les maths viennent après. [/EDIT]

    Sinon, j'ai feuilleté très rapidement le bouquin donc j'aurais du mal à juger définitivement ce qu'il vaut (en particulier, la partie "preuve du théorème" n'est qu'une (petite) partie du bouquin, et il y a un historique qui ne me semble pas inintéressant). En tout état de cause, malgré l'immensité du talent mathématique de Feferman que personne ne peut nier, j'ai tendance à prendre ces avis avec des pincettes car je ne l'ai jamais trouvé très nuancé dans ces critiques... Par exemple à propos de Chaitin (qui est hautement critiquable comme personnage), il écrit parfois des choses manifestement fausses, sans doute emporté par sa (compréhensible) détestation du personnage.

  4. #4
    invite9cd736bc

    Re : Théorème d'incomplétude de Gödel

    Bonsoir,

    Si vous voulez des nouvelles de Médiat :
    Le mot de code est : "Gödel",

    cordialement,

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

    Re : Théorème d'incomplétude de Gödel

    Citation:
    J'ai feuilleté hier un bouquin sur Gödel dans lequel il était énoncé sous la forme "si la théorie est cohérente, il existe des énoncés VRAIS indémontrables".
    Formulation "marketing" absolument inacceptable
    J'affirme comme théorème que toute proposition (formelle, informelle, propositionnelle ou sous barbiturique) contenant le terme VRAI provoquera une poussée d'urticaire cholinergique chez Médiat.

    Corolaire : les gens qui ne sont pas d'accord avec ce théorème sont totalement inconsistant.


  7. #6
    Médiat

    Re : Théorème d'incomplétude de Gödel

    Citation Envoyé par erik Voir le message
    J'affirme comme théorème que toute proposition (formelle, informelle, propositionnelle ou sous barbiturique) contenant le terme VRAI provoquera une poussée d'urticaire cholinergique chez Médiat.
    D'abord, j'ai appris un mot donc, merci, et j'ai bien compris l'intention, mais je précise néanmoins que l'expression "vrai dans le modèle XXX" ne stimule pas mon acétylcholine .

    Citation Envoyé par erik Voir le message
    Corolaire : les gens qui ne sont pas d'accord avec ce théorème sont totalement inconsistant
    Là je n'ai rien à redire puisque c'est "VRAI" .
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  8. #7
    Turgon

    Re : Théorème d'incomplétude de Gödel

    Bonjour.

    Je suis un total novice pour ce qui est de Gödel et de ses théorèmes. J'aimerais quelques précisions sur le codage des propositions par les entiers.

    Si je ne me trompe pas, le codage qu'emploie Gödel utilise l'existence et l'unicité de la décomposition en produit de facteur premiers de tout nombre entier.
    Donc (ou peut être est-ce relativement indépendant), comme le dit Médiat, les théorèmes d'incomplétudes présupposent la possibilité de codage des propositions dans le modèle standard des entiers.

    Est-il donc juste de dire que les théorèmes de Gödel sont faits sous l'hypothèse de la non contradiction de l'arithmétique (puisqu'un théorème de l'arithmétique est utilisé) et sous l'hypothèse de l'existence d'un modèle dit "standard" (adjectif dont je n'ai pas bien comprit la définitions).

    Merci d'avance.

  9. #8
    Médiat

    Re : Théorème d'incomplétude de Gödel

    Bonjour
    Citation Envoyé par Turgon Voir le message
    Si je ne me trompe pas, le codage qu'emploie Gödel utilise l'existence et l'unicité de la décomposition en produit de facteur premiers de tout nombre entier.
    Ce qui n'est pas un problème puisque justement on travaille dans une théorie supposée consistante contenant l'arithmétique, donc cette existence et unicité de la décomposition est bien un théorème.

    Citation Envoyé par Turgon Voir le message
    Donc (ou peut être est-ce relativement indépendant), comme le dit Médiat, les théorèmes d'incomplétudes présupposent la possibilité de codage des propositions dans le modèle standard des entiers.
    Oui, parce que si c'est possible dans le modèle standard, c'est vrai dans tous les modèles.

    Citation Envoyé par Turgon Voir le message
    Est-il donc juste de dire que les théorèmes de Gödel sont faits sous l'hypothèse de la non contradiction de l'arithmétique (puisqu'un théorème de l'arithmétique est utilisé) et sous l'hypothèse de l'existence d'un modèle dit "standard" (adjectif dont je n'ai pas bien comprit la définitions).
    Si l'arithmétique (de Peano) n'est pas consistante, alors cette théorie n'a plus aucun intérêt. par contre si elle est consistante, elle admet un modèle, et il en existe un (appelé modèle standard), qui s'injecte élémentairement (toutes les formules atomiques (sans quantificateurs, ni connecteurs) vraies dans ce modèle sont vérifiées par leurs images par l'injection dans les autres modèles).

    cf. http://forums.futura-sciences.com/ma...ml#post1980944
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  10. #9
    rik 2

    Re : Théorème d'incomplétude de Gödel

    Je viens de lire un texte qui faisait allusion au théorème de Gödel appliqué à la physique (mais je ne le retrouve pas, dommage car la problématique était très bien posée); or donc ce théorème peut-il s'appliquer à la physique?

  11. #10
    Médiat

    Re : Théorème d'incomplétude de Gödel

    Citation Envoyé par rik 2 Voir le message
    Je viens de lire un texte qui faisait allusion au théorème de Gödel appliqué à la physique (mais je ne le retrouve pas, dommage car la problématique était très bien posée); or donc ce théorème peut-il s'appliquer à la physique?
    Bonjour,

    Le théoème de Gödel a été mis à bien des sauces, la plupart totalement indigestes voire toxiques, donc je me méfie avant d'en savoir plus.

    Sinon :
    1) On peut utiliser (en physique, en littérature ou en cosmétique ) le théorème d'incomplétude de Gödel comme une analogie, à condition de ne pas considérer que c'est une démonstration, et en annonçant clairement qu'on le cite en tant qu'analogie, sinon c'est de la malhonnêteté intellectuelle.

    2) Certaines théories physiques (toutes ?), peuvent s'axiomatiser dans un langage du premier ordre, si certaines vérifient les autres conditions du théorème de Gödel, alors il s'applique, sinon : non.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  12. #11
    Médiat

    Re : Théorème d'incomplétude de Gödel

    Citation Envoyé par rik 2 Voir le message
    Je viens de lire un texte qui faisait allusion au théorème de Gödel appliqué à la physique (mais je ne le retrouve pas, dommage car la problématique était très bien posée); or donc ce théorème peut-il s'appliquer à la physique?
    Je viens de décoincer, j'avais lu ce texte il y a 6 mois environ : est-ce que vous ne faites pas allusion au texte de Stephen W. Hawking : "Gödel and the End of Physics", texte dans lequel Hawking :
    1) utilise ses convictions platoniciennes comme argument pour justifier l'auto-référence, ce qui n'est pas scientifiquement recevable,
    2) cite le théorème de Gödel de façon très approximative (mais moins fausse que d'habitude ),
    3) conclut un paragraphe de façon mathématiquement inacceptable : "The theories we have so far are both inconsistent and incomplete.", puisque inconsistante et incomplète sont incompatible.
    4) précise "the analogy of Godel’s theorem", du coup c'est acceptable
    5) conclut le texte par "Godel’s theorem ensured there would always be a job for mathematicians.", ce qui me ravit, car j'ai déjà écrit cela sur FSG plusieurs fois pour contrer l'argument : "Le théorème de Gödel rend les mathématiques inutiles"
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  13. #12
    rik 2

    Re : Théorème d'incomplétude de Gödel

    j'ai retrouvé!
    "certains philosophes des sciences ont utilisé les théorèmes de Gödel sur l'incomplétude de l'arithmétique (et donc de tout système logique contenant l'arithmétique) pour affirmer qu'il est impossible de tout savoir sur l'univers physique en termes de lois mathématiques de la Nature, car on ne peut établir tous les énoncés vrais, et seulement ceux-là, de l'arithmétique, pas plus qu'on ne peut décider si tous les énoncés arithmétiques sont vrais ou faux. Voici ce qu'en pense Stanley Jaki:
    " (...) Pour le physicien spéculatif, cela implique qu'il y a des limites à la certitude, que même les concepts de la physique théorique ont des limites, tout comme dans d'autres domaines spéculatifs."
    Cependant il est possible que la réalité physique, même si sa finalité est mathématique, n'utilise pas toute l'arithmétique et, de ce fait, puisse être complète. Cette réalité pourrait se situer à l'intérieur d'une des branches décidables des mathématiques qui ne soit pas aussi riche que l'arithmétique."
    John D. Barrow; La grande théorie; Champs/Flammarion. p.57, il en parle aussi p. 52.
    Je suis rik.

  14. #13
    Médiat

    Re : Théorème d'incomplétude de Gödel

    Bonjour,

    Je suis très choqué par la phrase "même si sa finalité [de la réalité physique] est mathématique", il y a peut-être un problème de traduction, mais parler de la finalité de la réalité physique ne me paraît pas très scientifique, et la qualifier (la finalité) de mathématique, je ne vois vraiment pas ce que cela veut dire.

    Par contre je suis parfaitement d'accord avec "Cette réalité pourrait se situer à l'intérieur d'une des branches décidables des mathématiques qui ne soit pas aussi riche que l'arithmétique", qui montre que l'auteur a suffisamment compris le théorème de Gödel.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  15. #14
    karlp

    Re : Théorème d'incomplétude de Gödel

    Citation Envoyé par Médiat Voir le message
    Bonjour,

    Par contre je suis parfaitement d'accord avec "Cette réalité pourrait se situer à l'intérieur d'une des branches décidables des mathématiques qui ne soit pas aussi riche que l'arithmétique", qui montre que l'auteur a suffisamment compris le théorème de Gödel.
    Bonjour à tous

    Il est très étonnant pour le profane que je suis de lire qu'il serait possible que les mathématiques nécessaires à la physique (ai-je bien compris ? la référence à cette "finalité mathématique me laisse également dubitatif) soient moins riches que l'arithmétique (je croyais naïvement que l'arithmétique de Peano était relativement faible).
    Je dois me contenter de faire confiance aux spécialistes.

    Ma question est la suivante: s'il était avéré que les mathématiques nécessaires à la physique sont obligatoirement plus puissantes que l'arithmétique de Peano, pourrions nous alors affirmer que la physique est incomplète ? (cela me semble a priori évident mais la lecture de M. Bouveresse m'a appris à me méfier).

    Cordialement

  16. #15
    Médiat

    Re : Théorème d'incomplétude de Gödel

    Bonjour
    Peano n'est pas si faible que cela (sinon pas de théorème d'incomplétude), même si elle est plus simple que Peano au second ordre ou une bonne vieille théorie des ensembles.

    Si la physique peut se résumer (dans sa partie formelle) à des théories du premier ordre, je peux comprendre que les axiomes devront être récursivement énumérables, et donc si au moins l'une contient l'arithmétique, alors elle sera essentiellement incomplète.

    Mais ce n'est pas gênant : si on tombe sur un indécidable, il suffit de faire l'expérience (le physicien en a le droit et même le devoir), et on ajoute l'axiome qui va bien.

    Je sais que je simplifie jusqu'à la caricature, mais même cette caricature illustre bien cette non toxicité de l'incomplétude : soit on sait faire une expérience qui permet de trancher et on tranche, soit on ne sait pas faire, et il n'est pas utile de faire un choix.

    Cordialement
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  17. #16
    karlp

    Re : Théorème d'incomplétude de Gödel

    Citation Envoyé par Médiat Voir le message

    (1) Si la physique peut se résumer (dans sa partie formelle) à des théories du premier ordre, je peux comprendre que (1-1)les axiomes devront être récursivement énumérables, et donc si au moins l'une contient l'arithmétique, alors elle sera essentiellement incomplète.

    Mais ce n'est pas gênant : (1-2) si on tombe sur un indécidable, il suffit de faire l'expérience (le physicien en a le droit et même le devoir), et on ajoute l'axiome qui va bien.
    (2) Je sais que je simplifie jusqu'à la caricature, mais même cette caricature illustre bien cette non toxicité de l'incomplétude : soit on sait faire une expérience qui permet de trancher et on tranche, soit on ne sait pas faire, et il n'est pas utile de faire un choix.

    Cordialement
    Merci Médiat pour votre réponse

    (1-1) Je croyais comprendre ce qu'est un ensemble récursivement énumérable (de façon incertaine je dois le confesser). Ce ne doit pas être le cas puisque je ne comprends pas ce que signifie une liste d'axiomes récursivement énumérable (je croyais que c'était à partir d'une axiomatique qu'un ensemble pouvait être récursivement énumérable) . Pouvez vous m'éclairer ou me guider vers un texte de votre connaissance ? (je vais chercher de mon côté).

    (1-2) Vous me faites la même réponse que Doumit (psychanalyste), ce qui me conduit au:
    (2) Sur la question de l'interprétation de l'indécidabilité d'une formule, il semblerait que d'aucuns jugent la chose regrettable (est-ce ce que vous entendez par "toxique" ?); tandis que d'autres s'en réjouissent. Je serai plutôt de ces derniers (pour des raisons philosophiques et morales, secondaires ici)

  18. #17
    Médiat

    Re : Théorème d'incomplétude de Gödel

    Bonjour,

    (1-1) Qu’un ensemble (d’axiomes ou non) soit récursivement énumérable, cela veut dire que nous disposons d’un mécanisme (algorithme) qui permet de lister tous les axiomes, même s’il y en a une infinité, et même d’un point de vue pratique, cela veut dire que l’on peut écrire explicitement l’axiome dont on a besoin, même s’il existe dans l’axiomatique sous la forme d’un schéma d’axiomes.
    Pour essayer d’être plus clair, si on prend le schéma de récurrence :
    Pour toute formule à une variable libre n :
    .
    On voit que dans ce schéma, je ne quantifie pas sur la formule, c’est interdit en logique du premier ordre (j’ai bien écrit pour toute et non ), et sans dire ce qu’est exactement , à part qu’il s’agit d’une formule, or il existe des algorithmes qui génèrent la construction des formules ; et puis quand un élève de lycée se trouve face à une formule précise, il sait (devrait savoir) écrire l’axiome, pour l'appliquer. Nous sommes bien dans le cas récursivement énumérables.

    Un système d’axiomes qui ne serait pas récursivement énumérables (comme l’ensemble de toutes les formules « vraies dans le modèle standard de l’arithmétique », ne peut pas être « manipulé par un être humain.

    (2) En disant que cette incomplétude n’est pas « toxique », je voulais effectivement bien dire qu’elle n’est absolument pas gênante, je n’irais pas jusqu’à dire que je m’en réjouis (dans le cas de la physique (en mathématiques je m'en réjouis : je ne serai jamais au chômage )), cela me laisse indifférent, car je sais que ce n’est pas plus une frontière infranchissable que ne l’est l’horizon.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  19. #18
    karlp

    Re : Théorème d'incomplétude de Gödel

    2) C'est à peu près la même raison ("il n'y aura pas de chômage" qui se traduit pour moi par "il y aura toujours des objets nouveaux pour notre désir - de connaissance-") qui fait que l'indécidabilité est source de réjouissance.

    1)Ce que vous me dîtes semble confirmer que je comprenais bien le sens de "récursivement énumérable".
    Il faut que je prenne le temps de réfléchir à l'application de cette expression à un ensemble d'axiomes. L'exemple que vous donnez de l'élève qui doit pouvoir retrouver l'axiome nécessaire à l'application d'une formule m'indique une direction à laquelle je n'avais pas songé.

  20. #19
    Médiat

    Re : Théorème d'incomplétude de Gödel

    Citation Envoyé par karlp Voir le message
    2) C'est à peu près la même raison ("il n'y aura pas de chômage" qui se traduit pour moi par "il y aura toujours des objets nouveaux pour notre désir - de connaissance-") qui fait que l'indécidabilité est source de réjouissance.
    En physique, je n'ai pas ce problème, j'ai encore de la marge, avant d'atteindre les limites de la complétude (traduisez : je suis nul).

    Sinon la traduction ("il n'y aura pas de chômage" qui se traduit pour moi par "il y aura toujours des objets nouveaux pour notre désir - de connaissance-") est exactement ce que je voulais dire (pour les mathématiques).
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  21. #20
    pelkin

    Re : Théorème d'incomplétude de Gödel

    Citation Envoyé par Médiat Voir le message
    En physique, je n'ai pas ce problème, j'ai encore de la marge, avant d'atteindre les limites de la complétude (traduisez : je suis nul).
    Pas grave, il suffit d'appliquer le théorème d'incomplétude !

    Citation Envoyé par Médiat Voir le message
    Sinon la traduction ("il n'y aura pas de chômage" qui se traduit pour moi par "il y aura toujours des objets nouveaux pour notre désir - de connaissance-") est exactement ce que je voulais dire (pour les mathématiques).
    Dont acte !

    Amicalement

  22. #21
    Médiat

    Re : Théorème d'incomplétude de Gödel

    Citation Envoyé par pelkin Voir le message
    Pas grave, il suffit d'appliquer le théorème d'incomplétude !
    C'est plutôt le Nullstellensatz en ce qui me concerne

    Amicalement
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  23. #22
    Matmat

    Re : Théorème d'incomplétude de Gödel

    Citation Envoyé par Médiat Voir le message
    C'est plutôt le Nullstellensatz en ce qui me concerne

    Amicalement
    théorème : Créez un fil sur Hilbert et personne ne vous répondra , créez un fil sur Godel , on finira toujours par vous parler de Hilbert

  24. #23
    PlaneteF

    Re : Théorème d'incomplétude de Gödel

    Bonsoir,

    Je "déterre" ce "vieux" fil, ... je suis tombé dessus par hasard et je voulais juste apporter une correction sur le morceau de phrase ci-dessous :

    Citation Envoyé par BGT Voir le message
    (...) il existait des énoncés indémontrables, i.e. on a des modèles dans lesquels est vrai et d'autres dans lesquels il est faux.
    Un énoncé qui n'est pas démontrable dans une théorie veut dire qu'il existe (au moins) un modèle de la théorie qui ne satisfait pas cet énoncé, ... mais cela ne veut pas forcément dire qu'il existe un modèle qui satisfait cet énoncé. Pour que la phrase en citation soit correcte il faut remplacer "indémontrable" par "indécidable".


    Cordialement
    Dernière modification par PlaneteF ; 02/09/2014 à 18h32.

  25. #24
    PlaneteF

    Re : Théorème d'incomplétude de Gödel

    Citation Envoyé par PlaneteF Voir le message
    Pour que la phrase en citation soit correcte il faut remplacer "indémontrable" par "indécidable".
    De son côté, pour que cette phrase soit elle-même exacte, il suffit de remplacer "il faut" par "il suffit de" (après tout, d'une manière générale, pour rendre une phrase exacte, il n'y a pas qu'une seule modification possible ).
    Dernière modification par PlaneteF ; 03/09/2014 à 14h09.

  26. #25
    Schrodies-cat

    Re : Théorème d'incomplétude de Gödel

    Il faut remonter à la démonstration de Gödel pour éviter d'en altérer le sens.
    Certains ont déjà parlé de la possibilité de coder par des nombres entiers les énoncés de l'arithmétique.
    (notons qu'à l'époque, l'informatique n'existait pas et que coder les éléments d'un langage complexe par des objets élémentaires n'était pas une évidence)
    Gödel est allé plus loin en représentant la démontrabilité dans une théories données d'un énoncé par une propriété arithmétique portant sur le nombre entier représentant cet énoncé.
    Dernier coup de génie, après ce travail laborieux, il construit un énoncé, pour toute théorie contenant l'arithmétique, qui signifie qu'il est lui même indémontrable.
    Appelons P -pour paradoxe- cet énoncé:
    P signifie que P est indémontrable.
    Supposons que non P, cela signifie que P n'est pas indémontrable, donc que P est démontrable, ce dont on déduit P, contradiction !
    Donc P.
    Naïvement, on dira que P est vrai ... donc P est indémontrable .
    Mais alors, en mathématiques, pour dire que quelque chose est vrai, il faut le démontrer, donc si c'est indémontrable ???

    En fait, si j'ai compris quelque chose (envoyez moi au galères si vous estimez que ce n'est pas le cas), Il me semble que la déduction : P démontrable donc P fait appel implicitement à l’hypothèse que la théorie dans laquelle ont travaille est non contradictoire. Il faudrait sans doute formaliser cela plus avant.
    Gödel et von Neumann ont rapidement compris cela, avec à la clef un deuxième théorème d'incomplétude qui dit que la non contradiction d'une théorie ne peut être démontrable dans cette théorie.

    Note: on peut montrer que l'arithmétique de Peano est non contradictoire dans le cadre de la théorie des ensemble en utilisant le fait que l'ensemble des entiers naturels en forment un modèle, mais c'est un peu facile de se placer dans une théorie plus puissante, et donc dont la non contradiction est encore moins certaine, pour montrer la non contradiction d'une théorie.

    En tous cas, les mathématiciens espèrent que l'arithmétique de Peano ou la théorie ZF des ensemble sont non contradictoires, mais sans pouvoir être surs que c'est vrai.

    Quand au sens (?) du mot vrai en mathématiques, je reviendrai sur cela si j'en ai l'occasion.
    Il n'est pire sot que qui ne veut pas comprendre .

  27. #26
    Schrodies-cat

    Re : Théorème d'incomplétude de Gödel

    P.S. A la réflexion, il faut peut être remplacer dans ce qui précède non contradiction par oméga-consistance.
    Il n'est pire sot que qui ne veut pas comprendre .

  28. #27
    Médiat

    Re : Théorème d'incomplétude de Gödel

    Bonjour,

    Citation Envoyé par Schrodies-cat Voir le message
    Il me semble que la déduction : P démontrable donc P fait appel implicitement à l’hypothèse que la théorie dans laquelle ont travaille est non contradictoire.
    P est démontrable veut dire qu'il existe une liste finie de formules (dans un ordre précis, non forcément linéaire) dont les atomes sont des axiomes et le plus grand élément est P, l'ordre entre deux formules directement liées, s'exprimant par l'existence d'une règle d'inférence qui permet de passer de l'une à l'autre.

    Dans une théorie inconsistante toutes les formules sont donc démontrables (certains logiciens anglophones utilisent "all" à la place de FAUX, pour cette raison)
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  29. #28
    Schrodies-cat

    Re : Théorème d'incomplétude de Gödel

    Citation Envoyé par Médiat Voir le message
    Bonjour,


    P est démontrable veut dire qu'il existe une liste finie de formules (dans un ordre précis, non forcément linéaire) dont les atomes sont des axiomes et le plus grand élément est P, l'ordre entre deux formules directement liées, s'exprimant par l'existence d'une règle d'inférence qui permet de passer de l'une à l'autre.

    Dans une théorie inconsistante toutes les formules sont donc démontrables (certains logiciens anglophones utilisent "all" à la place de FAUX, pour cette raison)
    En fait il faut préciser ce que signifie ici "P est démontrable" cela signifie que "il existe une démonstration de P" est un théorème, mais ce théorème permet-il d'écrire effectivement une démonstration de P,qui permettrait de faire de P un théorème., autrement dit, cette démonstration d'existence est-elle constructive ? C'est la qu'intervient l'hypothèse d'oméga-consistance.
    Il n'est pire sot que qui ne veut pas comprendre .

  30. #29
    invite78516567821
    Invité

    Re : Théorème d'incomplétude de Gödel

    Voici l'énoncé exact du théorème de Gödel (1931) :
    A chaque classe récursive oméga-consistante k correspondent des signes de classe r récursifs que ni v Gen r ni Neg (v Gen r) n'appartient à Flg (k) (v étant la variable libre de r).

    Peut-être que le fait de comprendre ce texte pourrait-il être un préalable utile à toute discussion concernant ce théorème .

  31. #30
    Médiat

    Re : Théorème d'incomplétude de Gödel

    Bonjour (la politesse n'est pas optionnelle sur ce site)

    A quoi sert de donner une version de 1931 qui utilise des concepts et du vocabulaire complètement démodés, alors que Gödel lui-même a donné une version de ce théorème en terme plus moderne en 1963 ?
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

Page 1 sur 2 1 DernièreDernière

Discussions similaires

  1. Précisions sur le théorème d'incomplétude de Gödel...
    Par invite05799208 dans le forum Mathématiques du supérieur
    Réponses: 26
    Dernier message: 08/09/2010, 08h13
  2. théorème de Gödel
    Par invite9bf717fa dans le forum Mathématiques du supérieur
    Réponses: 37
    Dernier message: 05/12/2009, 16h38
  3. Théorème d'incomplétude
    Par invitef8661968 dans le forum Mathématiques du supérieur
    Réponses: 14
    Dernier message: 16/09/2009, 04h49
  4. Théorème de Gödel
    Par invite441ba8b9 dans le forum Lectures scientifiques
    Réponses: 5
    Dernier message: 13/01/2006, 02h07
  5. Theorème de Gödel
    Par invite5eb13cb6 dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 23/04/2004, 11h14