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

[BGT]

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.

[Médiat]

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

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.

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

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

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 :

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/

[BGT]

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

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.

[invité87654321234567]

Bonsoir,

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

cordialement,

[erik]

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.

[Médiat]

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 .

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

[Turgon]

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.

[Médiat]

Bonjour

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.

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.

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. Arithmétique

[rik 2]

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?

[Médiat]

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.

[Médiat]

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"

[rik 2]

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.

[Médiat]

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.

[karlp]

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

[Médiat]

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