Ambiguïté : "Gödel a établi que certaines vérités mathématiques sont indémontrables."

[invite6754323456711]

Bonsoir,

Gregory Chaitin écrit dans un article de la recherche "Gödel a établi
que certaines vérités mathématiques sont indémontrables." http://www.cs.auckland.ac.nz/CDMTCS/...recherche2.pdf

Yann Ollivier écrit que c'est une non interprétation :

« Le théorème de Gödel prouve qu'il y a des vérités indémontrables. »

Pour la première affirmation, non : si la phrase "G" de Gödel était vraie (i.e. vérifiée dans tout modèle de "S"), alors elle serait démontrable, en vertu, précisément, du théorème de complétude du même Gödel. Il y a donc des modèles de "S" où "G" est fausse.

....

http://www.yann-ollivier.org/goedel/goedel.php

A première lecture, les différents niveaux d'imbrication de Yann ne m'apparaisse pas très limpide à cette heure ci de la nuit.

Comment reformuler la phrase pour la rendre correcte ?

Patrick
-----

[Médiat]

Combien de fois faudra-t-il que j'aborde ce sujet avec toi ?
A l'évidence Chaitin (ou le rédacteur ou le traducteur) est un platonicien pour qui "vrai" veut dire "vrai dans le modèle standard" (que dire des théories n'ayant pas de modèles que l'on puisse qualifier de standard (en fait le modèle premier qui n'existe pas pour toutes les théories) ?). Façon de dire les choses que je combats régulièrement à cause des confusions (ce fil en donne une preuve de plus) qu'il peut engendrer (en général je précise que cette façon de dire les choses est plus spectaculaire et plus vendeuse que l'autre, ce qui est une préoccupation qui ne devrait pas toucher un mathématicien (je ne dis pas que c'est le cas de Chaitin)).

Il va de soi que je suis en plein accord avec Yann Ollivier (que je soupçonne d'être, lui aussi, formaliste), à la fois sur la formulation et sur l'avis que la formulation platonicienne crée une contradiction avec le théorème de complétude de ce même Gödel ; cette façon de définir "vrai" par "vrai dans tous les modèles" tuant à la racine ces confusions.

Les deux phrases sont donc correctes, l'une par un platonicien et qui crée des confusions et des incompréhensions, l'autre par un formaliste qui a peut-être le défaut de demander plus de connaissance (mais je ne vois pas cela comme un défaut) et qui a le mérite inestimable d'être sans ambiguïté.

Pour les niveaux d'imbrications, n'ayant pas lu l'article entièrement, je me garderais d'en faire l'exégèse, mais je peux remarquer que cette façon de faire devrait éviter à ceux qui les ont compris d'écrire, ce que j'ai lu encore récemment (en épistémologie : http://forums.futura-sciences.com/ep...ml#post2537383), puisqu'à l'évidence pour que le théorème de Gödel s'applique, il faut être capable de formaliser les 2 niveaux (1 et 2), ce qui est impossible avec beaucoup de théories.

[invite9cd736bc]

Il est vrai que Châtain fait dire à Gödel plus que son théorème d'incomplétude ne peut en dire. Gödel relativise l'imcomplétude, en la situant pas rapport à un ensemble d'axiomes, et de règles de déduction. Châtain quand à lui donne une version plus forte de l'incomplétude en affirmant qu'il existe des vérités mathématiques indémontrables.
Comme le fait remarquer Châtain :Comprendre, démontrer, c'est pouvoir comprimer/réduire l'information. Dans le fait de pouvoir "démontrer" il y a l'idée implicite qu'un fait est forcément dépendant d'un autre, que les faits trouvent leur raison d'être relativement aux autres. Or ce que Chatain montre avec son nombre oméga, est qu'il existe de vérités non-démontrables qui sont des vérités-en-soi. Il faut entendre par là des vérités irréductibles, incompressibles, aléatoire..C'est comme cela et c'est tout. Ce sont des tautologies, des faits qui se résument strictement à eux-mêmes.
En ce sens, il me semble que Châtain donne une version étendue de l'incomplétude mathématique. Il donne par ailleurs une définition du hazard. Les faits du hasard sont tautologiques, historiques, irréductibles. Toute explication des faits relevant du hasard sont donc de pures interprétations. Cela montre aussi l'intérêt d'autres approches des mathématiques, plus intuitives, pouvant même s'appuyer sur l'expérimentation.

[invite6754323456711]

Il va de soi que je suis en plein accord avec Yann Ollivier (que je soupçonne d'être, lui aussi, formaliste), à la fois sur la formulation et sur l'avis que la formulation platonicienne crée une contradiction avec le théorème de complétude de ce même Gödel ; cette façon de définir "vrai" par "vrai dans tous les modèles" tuant à la racine ces confusions.

Les deux phrases sont donc correctes, l'une par un platonicien et qui crée des confusions et des incompréhensions, l'autre par un formaliste.

C'est bien cette confusion qui m'a posé problème. La notion de vérité je l'entendais au sens donné dans la théorie des modèles (universellement valide, loi logique : vrai dans tout modèle)

"Vrai" dans un modèle standard (Platonicien) signifie t-il satisfaisable (possiblement vraie lorsqu’elle est vraie dans au moins un modèle) ?


Une autre confusion peut apparaitre aussi avec les notions : théorème de complétude de Godel et complétude d'une théorie.

Dixit Wikipédia : Le théorème de complétude dit qu'il existe des théories axiomatiques complètes de la logique du premier ordre.

Dixit un échange lu sur un autre forum :

Théorème de complétude de Godel :

Il est "clair" que si T est consistante, alors elle est coherente; la reciproque n'est pas forcement vraie. Le theoreme de completude
de Godel (rien n'a voir avec la completude d'une theorie) affirme qu'avec l'Axiome du Choix, "consistante" est equivalente a "coherente".

Complétude d'une théorie

Maintenant, une theorie peut etre complete, c'est a dire que, pour F une formule, soit elle demontre F, soit elle demontre non-F.

De plus le sens donné aux notions de non-condradictoire - consistance - cohérence semblent dépendre de l'interlocuteur

Une theorie T est juste un ensemble de formules closes dans un langage donne. T peut etre consistante, c'est a dire qu'il existe
un modele de T ou coherente, c'est a dire que T ne peut pas demontrer une formule et son contraire.

On dira qu'une théorie est non contradictoire s'il existe un modèle dans lequel elle est vraie. On dira qu'elle est consistante (ou cohérente) si elle ne permet pas de prouver à la fois une formule et sa négation.

Ainsi qu'avec le vocabulaire décidable

Une theorie peut etre decidable (rien n'a voir avec la decidabilite d'une formule...), c'est a dire qu'il existe un algorithme qui permet de savoir si, pour une formule F donne, T demontre F.

Patrick

[A voir en vidéo sur Futura]

[Médiat]

"Vrai" dans un modèle standard (Platonicien) signifie t-il satisfaisable (possiblement vraie lorsqu’elle est vraie dans au moins un modèle) ?

Une formule "vraie" dans le modèle standard est forcèment "vraie" dans au moins un modèle (ce qui ne l'empêche pas,éventuellement, d'être "vraie" dans tous).

Une autre confusion peut apparaitre aussi avec les notions : théorème de complétude de Godel et complétude d'une théorie.

Effectivement ces deux définitions sont très différentes.

Dixit Wikipédia : Le théorème de complétude dit qu'il existe des théories axiomatiques complètes de la logique du premier ordre.

Alors Wikipedia dit des horreurs : le théorème de complétude établi un lien entre modèle et théorie, on peut démontrer qu'une théorie est complète sans parler de modèle.

Dixit un échange lu sur un autre forum :

Je ne vois pas ce que l'axiome du choix vient faire avec le théorème de complétude en logique classique du premier ordre, l'extrait que tu donnes parle peut-être de logiques infinitaires ?

Sinon, je suis d'accord avec la définition de "théorie complète" et de "théorie décidable".

Quant à la différentiation entre cohérente et consistante, elle n'a plus lieu d'être grace justement au théorème de complétude de Gödel.

[invite6754323456711]

Châtain quand à lui donne une version plus forte de l'incomplétude en affirmant qu'il existe des vérités mathématiques indémontrables.
Or ce que Chatain montre avec son nombre oméga, est qu'il existe de vérités non-démontrables qui sont des vérités-en-soi. Il faut entendre par là des vérités irréductibles, incompressibles, aléatoire..C'est comme cela et c'est tout. Ce sont des tautologies, des faits qui se résument strictement à eux-mêmes.

Qu'entends-tu par vérités mathématiques ?

Le V^e postulat d'Euclide (par un point pris hors d'une droite il passe une et une seule parallèle à cette droite) est "vrai" dans le plan de la géométrie euclidienne (modèle).

Ce même postulat est "faux" dans le demi-plan de Poincaré qui est un modèle de la géométrie hyperbolique (Lobatchevsky ). Pourquoi ce modèle devrait-il être moins privilégier ?

La formule est une loi logique ("vraie" dans tous les modèles).

Patrick

[invite9cd736bc]

Qu'entends-tu par vérités mathématiques ?

La conjecture de Golbach par exemple...

La conjecture de Goldbach stipule que tout nombre entier pair strictement supérieur à 2 peut être écrit comme la somme de deux nombres premiers (le même nombre premier pouvant être utilisé plusieurs fois). C'est l'un des plus vieux problèmes non résolus de la théorie des nombres et des mathématiques.

[invite7863222222222]

La conjecture de Golbach par exemple...

Une conjecture, par définition, on ne sait si elle est vérifiée ou non, ce n'est donc pas une vérité mathématique.

Peut être veux tu dire et pourquoi ne dirais-tu pas plus directement : Pour moi, une vérité mathématique est qu'il n'existe pas pour les théories contenant l'arithmétique de procédures automatiques permettant de savoir si toutes ses propositions sont vérifiées ?

[invite9cd736bc]

Une conjecture, par définition, on ne sait si elle est vérifiée ou non, ce n'est donc pas une vérité mathématique.

Non en tant que conjecture, elle a été vérifiée, mais pas démontrée...

[invite7863222222222]

Non en tant que conjecture, elle a été vérifiée, mais pas démontrée...

Heuu non pas suivant ce qu'il est expliqué ici : http://fr.wikipedia.org/wiki/Conjecture, par exemple.

[Médiat]

Non en tant que conjecture, elle a été vérifiée, mais pas démontrée...

Comment vérifie-t-on une propriété censée être vraie pour tous les entiers (une infinité donc) ?

[invite9cd736bc]

Comment vérifie-t-on une propriété censée être vraie pour tous les entiers (une infinité donc) ?

Très juste, il pourrait même s'agir d'une vérité indémontrable, juste vérifiable expérimentalement...
Serait-elle moins vraie pour autant ?

Par analogie avec le monde biologique, ces vérités sont comme des virus, ni vraiment vivantes, ni totalement inertes...

[Médiat]

Très juste, il pourrait même s'agir d'une vérité indémontrable, juste vérifiable expérimentalement...

Je répète ma question :
Comment vérifie-t-on une propriété censée être vraie pour tous les entiers (une infinité donc) ?

[Médiat]

Puisque le sujet de ce fil est l'ambiguité portée par l'usage d'un certain vocabulaire (que je combats), et que la conjecture de Goldbach est venue sur le tapis, j'en profite pour citer, avec ce même vocabulaire, ce que je considère être une horreur :

"Si la conjecture de Goldbach est indécidable, alors elle est vraie"

Phrase qui, évidemment, devrait être très suspecte, puisque par définition d'une proposition indécidable, on peut choisir de l'ajouter à sa théorie, ou y ajouter sa négation, être à la fois indécidable et vraie sonne donc comme un oxymore ; la bonne formulation (je veux dire celle sans ambiguité) serait plutôt :

"Si la conjecture de Goldbach est indécidable, alors elle est vraie dans le modèle standard".

Affirmation parfaitement exacte, en effet s'il existait un contre-exemple de la conjecture de Goldbach dans le modèle standard, ce contre-exemple se trouverait dans tous les modèles, et la conjecture de Goldbach ne serait donc pas indécidable.

Ce que je "démontre" dans le pragraphe précédent, bien qu'informel est correct (mais nécessiterait quelques précisions, et je ne pense pas que ce soit le bon lieu ici pour les donner) puisque le modèle standard est le modèle premier de l'arithmétique de Peano.

[invite6754323456711]

"Si la conjecture de Goldbach est indécidable, alors elle est vraie dans le modèle standard".

Peut on faire le lien avec cette formulation trouvé sur le Net ?

Le théorème de Gödel stipule que, étant donné un système cohérent quelconque d'axiomes arithmétiques, il y a des énoncés arithmétiques vrais qui ne peuvent pas être obtenus par déduction de l'ensemble des axiomes: "Il y a au moins une formule bien formée, dans n'importe quel système adéquat pour axiomatiser l'arithmétique, qui n'est pas décidable dans le système, même si on la sait juste (vraie) pour d'autres raisons".

Donc "Si la conjecture de Goldbach est indécidable, alors elle est vraie dans le modèle standard".


Maintenant s'il existait un contre-exemple de la conjecture de Goldbach dans le modèle standard, on en déduit que ce contre-exemple est donc satisfait dans le modèle standard (donc la conjecture est fausse dans le modèle standard ce qui induit qu'elle ne peut être indécidable) non ?

Ce contre-exemple se trouverait dans tous les modèles signifie qu'il est satisfait dans tous les modèles ?


Patrick

[Médiat]

Peut on faire le lien avec cette formulation trouvé sur le Net ?

Non, elle n'a aucun rapport avec la conjecture de Goldbach, cependant, la formulation que tu cites est, effectivement, un condensé de tout ce vocabulaire que je combats, permets d'écrire afin de communiquer quelque chose de faux (et encore je fais l'effort bienveillant de comprendre "même si on la sait juste (vraie)" comme voulant dire "même si on la sait juste (vraie dans le modèle standard)") ; de plus la formulation est intrinsèquement fausse (même pour un platonicien) : il n'y est pas question de l'hypothèse, pourtant essentielle, "récursivement axiomatisable".

Maintenant s'il existait un contre-exemple de la conjecture de Goldbach dans le modèle standard, on en déduit que ce contre-exemple est donc satisfait dans le modèle standard

(donc la conjecture est fausse dans le modèle standard ce qui induit qu'elle ne peut être indécidable) non ?

C'est exact (c'est ce que j'ai écrit, et je ne vais pas me dédire si vite) mais sans les explications que j'ai ajoutées, on pourrait croire que "si p est faux dans le modèle standard, alors p ne peut être indécidable" alors que c'est faux, il suffit de prendre pour exemple la négation de la conjecture de Goldbach.

Ce contre-exemple se trouverait dans tous les modèles signifie qu'il est satisfait dans tous les modèles ?

Cela ne le signifie pas, mais l'implique (mais comme je le disais dans mon message précédent : nécessiterait quelques précisions, et je ne pense pas que ce soit le bon lieu ici pour les donner) ; bien sur je répondrai à toutes les questions justifiées sur ce point.

[invite6754323456711]

Bonjour,

Est-ce le théorème de complétude qui permet d'avérer l'indécidabilité d'une conjecture à partir de l'ensemble des axiomes d'une théorie donnée (exemples le postulat de la parallèle d'Euclide, hypothèse du continu ...) ?

Corollaire :
Soit (L,S) une théorie du premier ordre. Si p est un énoncé de L non dérivable dans (L,S), il existe un modèle de (L,S) où (non p) est satisfait. Réciproquement, si l'énoncé (non p) est satisfait dans un modèle d'une théorie (L,S), p n'est pas dérivable dans (L,S).

Peut-on reformuler ainsi :

"Si la conjecture de Goldbach est indécidable, alors elle est un axiome dans le modèle standard"

Patrick

[Médiat]

Bonjour,

Est-ce le théorème de complétude qui permet d'avérer l'indécidabilité d'une conjecture à partir de l'ensemble des axiomes d'une théorie donnée (exemples le postulat de la parallèle d'Euclide, hypothèse du continu ...) ?

Non, pas vraiment, ce que l'on utilise c'est que s'il existe un modèle de T U {p} alors (non p) n'est pas démontrable dans T (et donc s'il existe un modèle de T U {p} et un de T U {(non p)} alors ni p ni (non p) ne sont démontrables dans T), ce qui est plus simple que le théorème de complétude.

"Si la conjecture de Goldbach est indécidable, alors elle est un axiome dans le modèle standard"

Dans la mesure ou la notion "d'axiome dans un modèle", n'a pas de sens, selon moi, la réponse est non !
Qu'y a-t-il de gênant à écrire "Si la conjecture de Goldbach est indécidable, alors elle est vraie dans le modèle standard" (on devrait même préciser "dans l'arithmétique de Peano") ?

[invite6754323456711]

Dans la mesure ou la notion "d'axiome dans un modèle", n'a pas de sens, selon moi, la réponse est non !

Oui la question est plutôt : dans la théorie classique de l'arithmétique de Peano tout comme l'axiome du choix peut être rajouté dans la théorie ZF des ensembles ?

Patrick

[Médiat]

Oui la question est plutôt : dans la théorie classique de l'arithmétique de Peano tout comme l'axiome du choix peut être rajouté dans la théorie ZF des ensembles ?

Par définition, si p est indécidable dans T on peut toujours ajouter p ou (non p) à T comme axiome, et on peut se poser la question de savoir lequel de p ou de (non p) est le plus "naturel" à ajouter. Pour l'hypothèse du continu, les travaux de Woodin font pencher la balance du côté de (non HC).

Pour l'arithmétique de Peano (PA), il n'y a pas de question, puisque le but est d'avoir une théorie dont le modèle standard est un modèle, par contre on pourrait (devrait) se poser la question de trouver une proposition p plus "naturelle", plus fondamentale que la conjecture de Goldbach (CG) et telle que PA U {p} démontre CG.

[invite6754323456711]

Par définition, si p est indécidable dans T on peut toujours ajouter p ou (non p) à T comme axiome

Le fait d'ajouter un axiome dans une théorie il devient donc un théorème pour cette théorie (p ==> p) donc satisfait dans tous ses modèles (et non pas seulement dans un seul modèle) ?

L'axiome n'est plus indécidable dans la théorie auquel il est ajouté.

Patrick

[Médiat]

Le fait d'ajouter un axiome dans une théorie il devient donc un théorème pour cette théorie (p ==> p) donc satisfait dans tous ses modèles (et non pas seulement dans un seul modèle) ?

Les axiomes ainsi que tous les théorèmes d'une théorie consistante sont vrais dans tous les modèles de cette théorie.

L'axiome n'est plus indécidable dans la théorie auquel il est ajouté.

C'est même pour cela qu'on l'ajoute.