Démontrabilité d'une proposition réfutable par un contre-ex

[Wiggins]

Bonjour à tous,

Je me pose une question plutôt métamathématique après avoir écouté encore une autre vidéo sur le théorème de Gödel... Voici la teneur du problème, pour lequel je vais détailler le raisonnement que j'ai fait, qui est peut-être (sûrement ?) erroné.

Imaginons une proposition réfutable par un contre-exemple (dans le cas où elle serait fausse), par exemple cette proposition issue d'un problème enfantin :

Tous les zéros non triviaux de la fonction Zêta de Riemann ont une partie réelle égale à 1/2.

Il suffit de trouver une racine dont la partie réelle n'est pas 1/2 pour la réfuter. Jusqu'ici je ne pense pas me tromper. Et bien j'ai l'impression que grâce à cette propriété, alors la proposition est forcément démontrable ou réfutable, et ne fait donc pas partie de l'ensemble des problèmes indécidables.

En effet, raisonnons par l'absurde. Je suppose que cette proposition est indécidable. Alors je ne peux pas la réfuter, donc je ne peux pas trouver un contre-exemple qui l'invaliderait, et donc j'ai démontré que cette proposition était vraie, ce qui est absurde car je l'ai supposée indécidable et donc en particulier non démontrable.

Ai-je démontré que toutes les propositions réfutables par un contre-exemple sont nécessairement démontrables ou réfutables? Est-ce indépendant du système d'axiomes? Je ne comprends pas où je me trompe.

En espérant susciter votre désir de me répondre, je vous remercie de m'avoir lu.

[GaBuZoMeu]

Si dans une théorie on démontre , alors n'est sûrement pas indécidable dans cette théorie . C'est bien évident, tu ne te trompes pas là-dessus, et je ne vois pas quel est le problème.

[lyceen95]

Tu n'as rien démontré.

Tu dis : Je cherche un contre-exemple, et je n'en trouve pas. Donc il n'y a pas de contre-exemple, donc la propriété est vraie.

La fin du raisonnement est correcte : s'il n'y a strictement aucun contre-exemple, alors la propriété est vraie.
Mais le début du raisonnement est faux. Si tu cherches un contre-exemple, et que tu n'en trouves pas, ça ne veut pas dire qu'il n'y a pas de contre-exemple. Ca veut juste dire que tu n'as pas trouvé de contre-exemple.
Peut-être que tu n'as pas assez cherché ce fameux contre-exemple, peut-être qu'il n'y a aucun contre-exemple, tu ne sais pas.

[GaBuZoMeu]

Rappelons une définition : un énoncé est indécidable dans une théorie si ni cet énoncé, ni sa négation n'est démontrable dans .
Le fait qu'on ne puisse pas démontrer dans n'entraîne pas que soit un théorème de .

[QuadriviuumTremens]

Je crois que le mot réfutable est utilisé en physique, pour caractériser si un modèle est testable par l'expérience. Je n'ai pas vu l'usage de ce mot en mathématique.

Une proposition mathématique est soit vraie si on l'a démontrée avec les axiomes de la théorie, soit fausse si elle entraîne une contradiction, soit indécidable si on a démontré que son acceptation, ou l'acceptation de son contraire n'entraine pas de contradiction. Si on ne connait pas le statut d'une proposition, on utilise pas d'adjectif particulier, mais on peut nommer cette proposition "conjecture" ou "hypothèse".

[GaBuZoMeu]

Autre chose :
Une théorie est dite inconsistante quand elle démontre le faux, autrement dit quand elle démontre tout.
Dans une théorie consistante, un énoncé est
- soit un théorème,
- soit la négation d'un théorème,
- soit ni l'un ni l'autre, auquel cas on dit qu'il est indécidable dans la théorie.

[Wiggins]

Si dans une théorie on démontre , alors n'est sûrement pas indécidable dans cette théorie . C'est bien évident, tu ne te trompes pas là-dessus, et je ne vois pas quel est le problème.

Justement je n'ai pas supposé qu'on avait démontré . Je dis simplement que si j'ai une propriété de cette forme : , alors effectivement il suffit de montrer pour démontrer qu'elle est fausse (ça je suis d'accord c'est trivial), mais surtout je montre que la propriété ne peut pas être indécidable. Car si elle était indécidable (raisonnons par l'absurde), alors ça veut dire qu'il est impossible de démontrer qu'elle est fausse, et donc dans ce cas, qu'il est impossible d'exhiber un contre-exemple. S'il est impossible d'exhiber un contre exemple, alors c'est qu'il n'y en a pas, donc la propriété est vraie. J'ai donc démontré qu'elle était vraie. C'est absurde puisque je l'ai supposée indécidable. Et donc j'en conclus que toutes les propriétés de la forme sont décidables.

Tu n'as rien démontré.

Tu dis : Je cherche un contre-exemple, et je n'en trouve pas. Donc il n'y a pas de contre-exemple, donc la propriété est vraie.

La fin du raisonnement est correcte : s'il n'y a strictement aucun contre-exemple, alors la propriété est vraie.
Mais le début du raisonnement est faux. Si tu cherches un contre-exemple, et que tu n'en trouves pas, ça ne veut pas dire qu'il n'y a pas de contre-exemple. Ca veut juste dire que tu n'as pas trouvé de contre-exemple.
Peut-être que tu n'as pas assez cherché ce fameux contre-exemple, peut-être qu'il n'y a aucun contre-exemple, tu ne sais pas.

Je n'ai pas simplement dit que je ne trouvais pas de contre-exemple, j'ai montré qu'il était impossible d'en trouver un, ce qui change tout et rend pour moi la démonstration correcte du début à la fin.

Ce qui m'étonne dans ce résultat c'est que justement l'hypothèse de Riemann est présentée comme potentiellement indécidable et qu'elle est de cette forme, donc il y a quelque chose de pas clair que j'aimerais comprendre .

[GaBuZoMeu]

Ton "raisonnement" tourne à vide.

Si est indécidable dans la théorie , il est impossible de démontrer dans . Mais cela ne constitue pas une démonstration de dans !!!

Sémantiquement : si est indécidable dans la théorie , il existe un modèle de et tel que , et il existe aussi un modèle de tel que, pour tout , est vrai.

Tu prends l'exemple de l'hypothèse de Riemann. OK. Mais la question est : quelle est la théorie dans laquelle tu te poses le problème de son indécidabilité ???

La notion d'indécidabilité est toujours liée à une théorie.

[Wiggins]

Si est indécidable dans la théorie , il est impossible de démontrer dans . Mais cela ne constitue pas une démonstration de dans !!!

Il me semblait aussi que le problème était là mais je ne trouve pas ça évident. J'ai considéré que l'impossibilité de démontrer était équivalente à l'impossibilité de trouver tq , ce qui pour moi équivalait à une démonstration de . Et le fait que ça ne dépende pas de la théorie choisie m'avait aussi perturbé, mais je n'en avais pas besoin dans cette pseudo-démonstration.

En fait dans le cas général je comprends bien que le fait de ne pas pouvoir démontrer une proposition n'implique pas que cette proposition est fausse, mais avec ce cas particulier j'avais l'impression qu'il y avait une équivalence entre les deux.

En tout cas merci pour vos réponses même si tout n'est pas encore parfaitement clair, ça m'a déjà bien aidé.

[GaBuZoMeu]

J'ai considéré que l'impossibilité de démontrer était équivalente à l'impossibilité de trouver tq , ce qui pour moi équivalait à une démonstration de .

Si tu veux t'éclaircir les idées, ne te contente pas de regarder des vidéos sur le théorème d'incomplétude de Gödel, mais lis un bon manuel de logique mathématique (un classique en français : Cori & Lascar).

Le théorème de complétude de Gödel (pas incomplétude, hein) te dit que si n'est pas un théorème de , alors il existe un modèle de tel que, pour tout , est vrai. Mais ça ne dit pas que pour tout modèle de et pour tout , est vrai.