indécidabilité et conjecture de Goldbach

[invited37a86e7]

Depuis Gödel on sait que les théories mathématiques cohérentes et contenant l'arithmétique sont nécessairement incomplètes.
Une assertion peut donc être exclusivement
(1) un théorème (vraie et démontrable),
(2) fausse,
(3) indécidable (ni vraie ni fausse)
(4) vraie mais non démontrable

Concernant la conjecture de Goldbach, j'aurais tendance à penser qu'elle est soit vraie soit fausse, puisqu'elle repose sur l'existence ou non d'au moins un entier pair qui ne peut s'écrire comme la somme de deux nombres premiers.
Mais la conjecture pourrait-elle être indécidable ? ça serait finalement au moins aussi surprenant que l'indécidabilité de l'hypothèse du continu non ?
Quant à la quatrième possibilité, cela serait équivalent à l'indécidabilité à l'exception qu'une théorie plus puissante du point de vue des axiomes est capable d'établir une démonstration de la véracité de l'assertion. Ce serait tout aussi déconcertant non ?
-----

[Bloud]

Je me pose une question : quel est la différence entre "vraie mais non démontrable" et indécidable ? Par exemple l'hypothèse du continu est classée dans quelle catégorie ?
La conjecture de Syracuse également ? J'ai lu (je ne sais plus où) que l'on avait démontré que ce problème est indécidable. Pourtant, quelle que soit la valeur considérée, la conjecture est vérifiée : alors vraie mais non démontrable ou indécidable ?

Merci d'avance.

Dimitri.

[Bloud]

Je retire ce que j'ai dit pour la conjecture de Syracuse. Son indécidabilité n'a pas du tout été prouvé. On a juste montré que des problèmes "similaires" étaient algorithmiquement indécidables.
Mille excuses.

Cependant, ma question reste posée...

[martini_bird]

Salut,

un problème également issu de l'arithmétique est le théorème de Goodstein : vrai mais indémontrable dans l'axiomatique de Peano.

Ce qu'il faut bien comprendre, c'est que le concept d'infini échappe à l'intuition : tous les paradoxes concernent ce concept.

Cordialement.

[A voir en vidéo sur Futura]

[martini_bird]

Je me pose une question : quel est la différence entre "vraie mais non démontrable" et indécidable ? Par exemple l'hypothèse du continu est classée dans quelle catégorie ?
La conjecture de Syracuse également ? J'ai lu (je ne sais plus où) que l'on avait démontré que ce problème est indécidable. Pourtant, quelle que soit la valeur considérée, la conjecture est vérifiée : alors vraie mais non démontrable ou indécidable ?

Merci d'avance.

Dimitri.

HC : indémontrable dans l'axiomatique de Zemerlo-Fraenkel.

Conjecture de Syracuse : mystère !

Vrai mais non démontrable : voir le théorème de Goodstein sus-mentionné.

Cordialement.

[Bloud]

J'ai lu le lien que tu as donné martini_bird. Cependant je me demande comment on fait pour démontrer qu'une assertion est vraie mais non démontrable ? Paradoxal non ? .
Soit on démontre qu'elle est vraie, soit on démontre qu'on ne peut pas la démontrer... Je crois ne pas encore avoir le niveau suffisant pour comprendre tout cela

[invite6de5f0ac]

Depuis Gödel on sait que les théories mathématiques cohérentes et contenant l'arithmétique sont nécessairement incomplètes.
Une assertion peut donc être exclusivement
(1) un théorème (vraie et démontrable),
(2) fausse,
(3) indécidable (ni vraie ni fausse)
(4) vraie mais non démontrable

Bionsoir,

Je ne te suis pas vraiment...

D'après le peu que je connais en Logique, il n'y a que des énoncés "démontrables" (D) ou "non démontrables" (ND). Et, depuis Gödel, des qui ne sont ni l'un ni l'autre (ID). Mais en aucun cas des "vrais, indémontrables", ou pire, (ce que tu n'envisages même pas), des "faux, dont on ne peut prouver qu'ils sont faux".

Je suis d'accord pour discuter de tout ça, mais là, on tombe en plein dans le forum "Epîstémologie", ce qui n'est d'ailleurs pas un défaut, loin de là.

En fait la question centrale est "Est-ce que la métamathématique est encore une branche des mathématiques" ? Pourquoi pas?

Quand on voit ce qu'on arrive à faire avec la Théorie des Catégories, qui ne repose même pas sur la totalité des axiomes de Zermelo-Fränkel, on peut se demander. Le sujet est effectivement passionnant... mais peut-être indécidable???

-- françois

P.S. - à , j'aurais peut-être dû ajouter "jaune"...

[invited37a86e7]

Le meilleur exemple d'assertion vraie mais non démontrable est l'assertion que produit la diagonale de Gödel et dont la traduction est "Je ne suis pas démontrable". Si elle est vraie elle n'est pas démontrable, sinon c'est une fausseté démontrable donc la théorie est incohérente.

Et Goldbach alors ? est-ce possible que ce soit indécidable (dans Peano ou ZF ?)

[martini_bird]

J'ai lu le lien que tu as donné martini_bird. Cependant je me demande comment on fait pour démontrer qu'une assertion est vraie mais non démontrable ? Paradoxal non ? .
Soit on démontre qu'elle est vraie, soit on démontre qu'on ne peut pas la démontrer... Je crois ne pas encore avoir le niveau suffisant pour comprendre tout cela

Le théorème de Goodstein se démontre en ajoutant des choses à l'axiomatique de Peano, à savoir la manipulation d'ordinaux transfinis.

Cordialement.

PS : l'axiomatique de Peano donne un sens à l'ensemble des nombres entiers naturels ; les nombres ordinaux sont le premier, le second, le troisième, etc. Les ordinaux transfinis permettent grosso modo de donner un sens à l'infinième +4, par exemple.

En particulier, une suite décroissante d'ordinaux transfinis est stationnaire à partir d'un certain rang (à comparer avec la descente infinie de Fermat).

[invite6de5f0ac]

Le meilleur exemple d'assertion vraie mais non démontrable est l'assertion que produit la diagonale de Gödel et dont la traduction est "Je ne suis pas démontrable". Si elle est vraie elle n'est pas démontrable, sinon c'est une fausseté démontrable donc la théorie est incohérente.

Et Goldbach alors ? est-ce possible que ce soit indécidable (dans Peano ou ZF ?)

Ah. Je vois.

C'est (IMHO) un abus de langage de dire que cette proporition est "vraie, mais non démontrable". Ce qui est sûr, c'est qu'elle est ND. De là à dire qu'elle est vraie... si ça veut dire qu'on ne peut pas produire de contre-exemple, c'est équivalent: si ND(P), alors ND(~P), ou plus précisément ~|=(P) => ~|=(~P), ce qui ne nous avance pas beaucoup.

Mais le symbole |=(P) n'a de sens que sous la forme T|=(P), où T est une théorie, au sens du volume 1 du tome 1 du chapitre 1 (etc.) de Bourbaki, c'est-à-dire, au sens où on n'accepte que ce qu'on a déjà décidé qui était acceptable...

Je suis un peu de mauvaise foi, d'accord, mais je suis comme Saint Thomas: je ne considérerai comme vrai que ce que l'on peut me démontrer, ou dont on peut me démontrer que le contraire est faux.

Et évidemment, les paradoxes échappent habituellement à ces critères...

-- françois

P.S. - Pour la culture générale, le lemme d'Emile Coué: pour toute proposition P, il existe une héorie T, et en entier naturel n(T,P), tel que T|=(Pⁿ).
En d'autres termes, toute proposition répétée suffisamment longtemps finit par être démontrable. Donc vraie?

[martini_bird]

C'est (IMHO) un abus de langage de dire que cette proporition est "vraie, mais non démontrable".

Tout à fait (IMHO too) : on devrait dire "vrai dans un système axiomatique, mais indécidable dans un système plus faible".

[invite6de5f0ac]

Tout à fait (IMHO too) : on devrait dire "vrai dans un système axiomatique, mais indécidable dans un système plus faible".

On peut faire pire, sans casser Zermelo-Fränkel. Regarde l'analyse non-standard: on postule l'existence d'ordinaux transfinis (avec la propriété de stationnarité que tu cites). Rien n'est remis en cause. Mais ça permet d'assimiler une intégrale (au sens de Riemann) à une somme finie, d'un nombre illimité de termes...

Et l'ANS n'introduit aucun paradoxe!

-- françois

[martini_bird]

je n'ai jamais travaillé avec l'ANS, mais il me semble qu'il y a bien ajout d'axiomes (existence d'éléments non-standard). Du reste, c'est effectivement compatible avec ZF, mais pas équivalent, si? Me trompé-je?

[invite6de5f0ac]

je n'ai jamais travaillé avec l'ANS, mais il me semble qu'il y a bien ajout d'axiomes (existence d'éléments non-standard). Du reste, c'est effectivement compatible avec ZF, mais pas équivalent, si? Me trompé-je?

Le seul axiome ajouté est que "Tout ensemble comporte des éléments non-standard". Le prédicat st(x) ("x est standard") est indépendant de tous les autres, ZF ou pas. On peut le lire indépendamment de toute interprétation; si j'osais (j'ose) je dirais que le fait d'être ou non standard est un degré de liberté supplémentaire, comme le spin en physique. Je vais me faire tuer...

-- françois

[martini_bird]

Ok, donc on a bien une axiomatique plus large que ZF.

Si un physicien ne passe pas dans le coin tu devrais t'en tirer à bon compte.

[invite6de5f0ac]

Ok, donc on a bien une axiomatique plus large que ZF.

Si un physicien ne passe pas dans le coin tu devrais t'en tirer à bon compte.

Tu rigoles? Les physiciens sont les premiers à admettre que ça marche:

intégrale de 0 à 1 de x dx = somme de 0 à omega de x fois epsilon = x(x+1)/2 fois un epsilon quelconque, qui est infinitésimal, donc l'intégrale égale (à un infinitésimal près) à x²/2.

Désolé, je n'ai pas encore les réflexes TeX câblés, mais ça va venir...

-- françois

[invited37a86e7]

C'est (IMHO) un abus de langage de dire que cette proporition est "vraie, mais non démontrable". Ce qui est sûr, c'est qu'elle est ND. De là à dire qu'elle est vraie... si ça veut dire qu'on ne peut pas produire de contre-exemple, c'est équivalent: si ND(P), alors ND(~P), ou plus précisément ~|=(P) => ~|=(~P), ce qui ne nous avance pas beaucoup.

Désolé, je dois être long à la détente mais en fait un énoncé plus correct serait "je ne suis pas démontrable dans T". Il s'agit d'une expression bien formée dans T et à l'instant ou elle est produite il n'est pas encore question d'une autre théorie plus forte. P dit ~|=(P).

~P => |=(P)
non ?

[martini_bird]

Tu rigoles? Les physiciens sont les premiers à admettre que ça marche:

intégrale de 0 à 1 de x dx = somme de 0 à omega de x fois epsilon = x(x+1)/2 fois un epsilon quelconque, qui est infinitésimal, donc l'intégrale égale (à un infinitésimal près) à x²/2.

Désolé, je n'ai pas encore les réflexes TeX câblés, mais ça va venir...

-- françois

Oki je croyais que ta remarque concernait ton illustration avec le spin.

Enfin bref, l'ANS semble (car je n'ai jamais trop pratiquer) bien fonctionner et ne s'oppose pas à l'analyse standard. En fait, on revient un peu au point de vue de Leibniz et Newton.

Cordialement.

[invite6de5f0ac]

Oki je croyais que ta remarque concernait ton illustration avec le spin.

Enfin bref, l'ANS semble (car je n'ai jamais trop pratiquer) bien fonctionner et ne s'oppose pas à l'analyse standard. En fait, on revient un peu au point de vue de Leibniz et Newton.

Cordialement.

Principalement, à celui de Newton. Et l'ANS, si tu regardes bien, ne fait que "officialiser" la complétude de R... et par là même, éjecte toutes les topologies p-adiques: Comme si les suites de Cauchy étaient définies comme le seul ctitère de convergence! C'est bien confortable, mais aussi très paresseux, non?

-- françois

[matthias]

Pour la conjecture de Goldbach, si elle est fausse alors il est possible de trouver un contre-exemple donc ce n'est pas un indécidable. Par contraposée, si c'est un indécidable alors elle est vraie.
Donc si on pouvait démontrer que c'est un indécidable on démontrerait en même temps qu'elle est vraie, et elle ne serait pas indécidable.
Conclusion : si la conjecture de Goldbach est indécidable, alors la proposition (la conjecture de Goldbach est indécidable) est elle-même indécidable.
Bizarre.
Y aurai-t'il une faille dans ce raisonnement ?

[Bloud]

Tout à fait (IMHO too) : on devrait dire "vrai dans un système axiomatique, mais indécidable dans un système plus faible".

D'accord, c'est beaucoup plus clair comme cela. J'avais du mal à imaginer la chose en restant dans un système axiomatique unique! .
J'ai une autre question : une assertion vraie est une proposition dont on a démontré qu'elle est vraie. Mais dans le cas des indécidables ou indémontrables, on ne peut les qualifier ni de vrais ni de faux. Mais peut-on considérer qu'une proposition a une "valeur intrinsèque" (valeur = vrai ou faux) ? Autrement dit, il me semble que ça a quand même du sens de parler, dans un système axiomatique donné, de vrai (faux) non démontrable (non réfutable).
En effet, mathématiquement, pour qualifier de vrai ou de faux, il faut établir une démonstration ou un contre-exemple. Mais le fait qu'on ne puisse pas les établir empêche-t-il à une proposition, quand elle est indémontrable, indécidable, d'être en elle-même vraie ou fausse ? On ne pourra jamais le savoir, certes, mais elle a quand même un caractère cette proposition, non ?

Deuxième question : on parle de "vrai dans un système axiomatique, mais indécidable dans un système plus faible". Mais dans le cas du faux ? Que dit-on ? Existe-t-il des énoncés faux dans un sytème axiomatique mais indécidables dans un sytème plus faible ? Si oui, comment les qualifie-t-on ? "Faux non réfutables" ?

Merci d'avance pour tous vos éclaircissements.

[invited37a86e7]

D'accord, c'est beaucoup plus clair comme cela. J'avais du mal à imaginer la chose en restant dans un système axiomatique unique! .
J'ai une autre question : une assertion vraie est une proposition dont on a démontré qu'elle est vraie.

C'est là ou je coince
pour moi il n'y a pas déquivalence entre "vrai" et "démontrable". il y a juste:
pour tout P, P est demontrable => P est vrai

Donc si je suis capable de trouver (sans sortir de ma théorie T) une proposition p telle que:
p est démontrable => p est faux
alors je me retrouve devant non pas un paradoxe, mais une incohérence dans T.
C'est justement ce que réalise l'assertion provenant de la diagonale de Gödel p="je ne suis pas démontrable dans T". Encore une fois, dans cette construction, on ne sort pas de T, on n'a pas ajouté d'axiomes.

[Bloud]

C'est là ou je coince
pour moi il n'y a pas déquivalence entre "vrai" et "démontrable". il y a juste:
pour tout P, P est demontrable => P est vrai

Je comprends ce que tu veux dire. Si tu préfères, je voulais dire : on peut dire qu'une assertion est vraie à partir du moment où on l'a démontré. Sans cette condition, tout avis serait vaine supputation. Cependant, tu remarqueras que cela est tout à fait en accord avec ce que tu as écrit : la démontrabilité de P est une condition nécessaire pour que l'on puisse écrire P est vraie. Toutefois cela est assez frustrant : cela peut vouloir dire qu'il existerait des énoncés vrais non démontrables d'où ma question dans mon post précédents : peut-on parler d'énoncé vrai "intrinsèquement" ? (quelque soit le système axiomatique considéré).

[invited37a86e7]

Pour la conjecture de Goldbach, si elle est fausse alors il est possible de trouver un contre-exemple donc ce n'est pas un indécidable. Par contraposée, si c'est un indécidable alors elle est vraie.

il me semble que tu peux reprendre ton raisonnement avec comme hypothèse que la conjecture est vraie: si vraie donc décidable. par contraposée: si indécidable alors faux !! ce qui est aussi faux

En fait ça revient à établir que si Goldbach est indécidable alors elle est à la fois vraie et fausse, ce qui n'est pas très surprenant.

Par contre si il est prouvé que Goldbach est indécidable dans Peano ou ZF, là c'est plus dur à avaler
Mais est-ce seulement envisageable?

[Bloud]

Donc si je suis capable de trouver (sans sortir de ma théorie T) une proposition p telle que:
p est démontrable => p est faux
alors je me retrouve devant non pas un paradoxe, mais une incohérence dans T.
C'est justement ce que réalise l'assertion provenant de la diagonale de Gödel p="je ne suis pas démontrable dans T". Encore une fois, dans cette construction, on ne sort pas de T, on n'a pas ajouté d'axiomes.

Je n'ai pas encore lu Gödel donc je vais peut-être dire des bêtises. J'ai l'impression que l'exemple que tu donnes est l'implication inverse de celle que tu as présentées. En effet si p est vraie alors p est non démontrable dans T. Mais si p est faux alors p est démontrable dans T. On a donc :
(1) p vrai => p non démontrable
(2) p faux => p démontrable

Le cas (1) correspond effectivement à l'implication que tu as présentée (il suffit de raisonner par contraposée). Seulement un détail me chiffonne : par contraposée on supppose que p est démontrable. Un raisonnement tel est complètement absurde dans la mesure où j'ai p="je ne suis pas démontrable dans T". En effet, dans la contraposée, p devient l'hypothèse. En règle générale, une hypothèse n'a qu'une seule valeur. Dans le cas présent, p est l'hypothèse donc la supposition est "p est non démontrable dans T". Voilà pourquoi le raisonnement par contraposée dans le cas (1) me semble louche. Par conséquent, seule l'implication (2) me semble "valide" et c'est bien l'implication inverse de celle que tu présentes .


Cependant je nuance mes propos : je me répète je n'ai rien lu de Gödel (et je ne me suis pas encore penché vraiment sur la logique) donc il se peut que je dise n'importe quoi.

[invited37a86e7]

Toutefois cela est assez frustrant : cela peut vouloir dire qu'il existerait des énoncés vrais non démontrables d'où ma question dans mon post précédents : peut-on parler d'énoncé vrai "intrinsèquement" ? (quelque soit le système axiomatique considéré).

Je pense qu'il y a des choses vraies non démontrables, mais c'est forcement par rapport à un système donné.

[matthias]

il me semble que tu peux reprendre ton raisonnement avec comme hypothèse que la conjecture est vraie: si vraie donc décidable. par contraposée: si indécidable alors faux !! ce qui est aussi faux

Non je ne suis pas d'accord, ou alors il y a vraiment quelque chose qui m'échappe. Pourquoi vraie entrainerait décidable ?
De plus en logique classique on a le principe du tiers exclu (contrairement à la logique intuitionniste). Une proposition quelconque, même indécidable, est ou vraie ou fausse, mais pas les deux ou aucun des deux. C'est un peu artificiel de dire qu'un indécidable est vrai ou faux, mais comme ça n'entraine pas de contradiction ...

En fait ça revient à établir que si Goldbach est indécidable alors elle est à la fois vraie et fausse, ce qui n'est pas très surprenant.

Ca irait juste à l'encontre du principe du tiers exclu justement. Un peu génant quand-même.

[Bloud]

Une proposition quelconque, même indécidable, est ou vraie ou fausse, mais pas les deux ou aucun des deux.

Super! C'est exactement ce sur quoi je m'interrogeais.
Merci!!!

[invited37a86e7]

Pas d'accord.
Un proposition p indécidable dans T n'est ni prouvable ni réfutable dans T.
Je peux construire une théorie T1 en posant comme axiome que p est vraie. Je peux en construire une deuxième T2 ou p est faux. Les deux seront parfaitement cohérentes. On peut alors parler de la fausseté/véracité exclusive, mais on se retrouve dans une théorie (T1 ou T2) plus fortement axiomatisé que T.
Cette démarche ne change pas le fait que dans T initiale, ma proposition p n'est ni vraie ni fausse ou, ce qui équivalent, vraie et fausse à la fois.
Ce que nous apprend Gödel c'est que même dans T1 et T2, je suis capable de trouver au moins une proposition qui soit indécidable, et pire: au moins une qui soit vraie mais non démontrable (la diagonale de Gödel dans T). Je dis "pire" pacequ'en plus on est capable de la construire (bien que son expression dans le formalisme utilisé soit monstrueuse)

[invited37a86e7]

On a donc :
(1) p vrai => p non démontrable
(2) p faux => p démontrable

Les deux implications sont vraies pour p. Mais en considérant que le membre de gauche de (2) est vrai ("p faux" est vrai) alors on en déduit que le membre de droite l'est aussi ("p démontrable" est vrai) ce qui est une incohérence dans la théorie considérée puisque:
Pour tout P, P faux => P non démontrable (contraposée de P démontrable => P vraie).
Donc il en résulte que l'implication (2) reste vraie pour p mais que "p faux" est nécessairement faux donc p est nécessairement vraie.