Petit quiz sur l'indécidabilité

[andretou]

Bonjour à tous
Sauf erreur de ma part, une proposition indécidable est une proposition pour laquelle on a démontré qu'on ne peut démontrer ni qu'elle est vraie, ni qu'elle est fausse (en quelque sorte, on a démontré qu'on ne peut rien démontrer !).

Mais a-t-on le droit de dire :
1/ une proposition indécidable est soit vraie, soit fausse, mais c'est impossible de le savoir
2/ une proposition indécidable n'est ni vraie, ni fausse
3/ une proposition indécidable peut être vraie sans qu'il soit possible de le démontrer
4/ une proposition indécidable peut être ni vraie, ni fausse

Merci d'avance pour vos réponses
-----

[Tryss2]

Il faut bien comprendre qu'une proposition est indécidable dans une théorie.

Or le théorème de complétude de Gödel nous dit qu'une proposition indécidable est une proposition qui est vraie dans certains modèles de la théorie, et fausse dans d'autres.

Prends comme théorie la géométrie d'Euclide (sans le 5ème postulat) et considère la proposition suivante : "soit un point et une droite. Alors il existe une seule droite qui passe par ce point et est parallèle à cette droite". Cette proposition est indécidable : Il existe des modèles ou elle est vraie (par exemple le plan euclidien R² ) et d'autres ou elle est fausse (par exemple la géométrie sphérique).

[Médiat]

Bonjour,

D'abord, comme le dit Tryss2, "proposition indécidable" ne veut rien dire, une proposition est démontrable, réfutable ou indécidable, dans une théorie, de plus le vocabulaire vrai/faux (typiquement platonicien) est source de nombreuses incompréhensions (j'ai même entendu Cédric Villani tomber dans ce travers) quand on l'utilise dans le cadre syntaxique (la théorie).

Vos 4 phrases sont la preuve évidente de cette incompréhension.

Soit une théorie et soit une proposition dans le langage de , alors (théorème de complétude de Gödel, bien plus important que les théorèmes d'incomplétude)

1. Soit est démontrable dans et dans ce cas elle est "vraie" dans tous les modèles de (j'ai l'air de me contredire en utilisant ce vocabulaire, mais je ne l'utilise que dans le cadre sémantique (les modèles) et non syntaxique (la théorie)
2. Soit est réfutable dans et dans ce cas elle est "fausse" dans tous les modèles de
3. Soit est indécidable dans et dans ce cas elle est "vraie" dans certains les modèles de et "fausse" dans d'autres
   1. est une théorie iso-consistante avec et est un théorème de cette théorie
   2. est une théorie iso-consistante avec et ​ est un théorème de cette théorie

Plutôt que de prendre la géométrie comme exemple (et c'est un très bon exemple), je préfère l'exemple beaucoup plus simple de la commutativité qui est indécidable dans la théorie des groupes

[feanorel]

Peut-être peut on ajouter pour l'ignorant que je suis qu'un modèle M d'une théorie T est une théorie qui contient T.

En d'autres termes dans une théorie donnée une proposition est indécidable si la supposer vraie ou la supposer fausse (en temps que nouvel axiome)
ne rends pas la théorie inconsistante. En termes grossier : on peut déclarer que P est vraie ou que P est fausse et ça ne change rien (à la théorie courante).

Et l'exemple le plus parlant de ceci pour moi est la question de savoir (dans ZFC) s'il existe un infini entre les dénombrables et les réels. C'est, si je ne
m'abuse, indécidable, donc on peut déclarer qu'il existe ou qu'il n'existe rien et ça ne changeras rien aux maths actuelles.

[A voir en vidéo sur Futura]

[Médiat]

Peut-être peut on ajouter pour l'ignorant que je suis qu'un modèle M d'une théorie T est une théorie qui contient T.

Vous voulez dire que la théorie d'un modèle de est une théorie qui contient

En d'autres termes dans une théorie donnée une proposition est indécidable si la supposer vraie ou la supposer fausse (en temps que nouvel axiome

ne rends pas la théorie inconsistante. En termes grossier : on peut déclarer que P est vraie ou que P est fausse et ça ne change rien (à la théorie courante).)

Comme je l'ai dit ci-dessus, ce vocabulaire génère des confusions

Et l'exemple le plus parlant de ceci pour moi est la question de savoir (dans ZFC) s'il existe un infini entre les dénombrables et les réels. C'est, si je ne
m'abuse, indécidable, donc on peut déclarer qu'il existe ou qu'il n'existe rien et ça ne changeras rien aux maths actuelles.

C'est l'hypothèse du continu, c'est effectivement indécidable dans ZFC (merci Gödel et Cohen), mais je ne pense vraiment pas que ce soit l'exemple le plus simple à proposer à des non-logiciens (il y a aussi AC dans ZF (merci Gödel et Cohen, encore).
Par contre l'ajouter ou ajouter sa négation change des théorèmes, mais comme le dit Krivine (pour critiquer la présentation des travaux de Woodin) dont j'ai eu l'extrême chance d'être un étudiant :

Chercher à savoir si HC est vraie ou fausse relève de la discussion sur le sexe des anges

[shaams]

Peut-être peut on ajouter pour l'ignorant que je suis qu'un modèle M d'une théorie T est une théorie qui contient T.

En d'autres termes dans une théorie donnée une proposition est indécidable si la supposer vraie ou la supposer fausse (en temps que nouvel axiome)
ne rends pas la théorie inconsistante. En termes grossier : on peut déclarer que P est vraie ou que P est fausse et ça ne change rien (à la théorie courante).

Et l'exemple le plus parlant de ceci pour moi est la question de savoir (dans ZFC) s'il existe un infini entre les dénombrables et les réels. C'est, si je ne
m'abuse, indécidable, donc on peut déclarer qu'il existe ou qu'il n'existe rien et ça ne changeras rien aux maths actuelles.

Cantor n'a t-il pas démontrer (avec l'argument diagonale) que cet infini existe ?

[Médiat]

Cantor n'a t-il pas démontrer (avec l'argument diagonale) que cet infini existe ?

Non, Cantor a démontré (je donne la version généralisée) que si est un ensemble de cardinal , alors est un ensemble de cardinal et , mais cela ne dit rien sur d'éventuels cardinaux entre et

[shaams]

Ah je vois !

[Tryss2]

D'ailleurs construire un modèle ou il existe un cardinal intermédiaire n'est pas chose aisée. Cohen a d'ailleurs obtenu la médaille Fields "pour ça".

https://fr.wikipedia.org/wiki/Forcing

Bon, cette technique n'est pas juste limitée à cette question

[andretou]

Mais s'il advenait que, demain, il soit prouvé que la conjecture de Goldbach est indécidable...
Dans ce cas, pourra-t-on dire de la proposition "tout nombre pair est égal à la somme de deux nombres premiers" que :
1/ c'est une proposition soit vraie, soit fausse, mais on ne peut pas le savoir
2/ c'est une proposition ni vraie, ni fausse
3/ c'est une proposition vraie mais impossible à démontrer
4/ c'est une proposition qui peut être ni vraie, ni fausse, on ne peut pas le savoir

[Médiat]

Encore une fois, le vocabulaire vrai/faux utilisé hors d'un cadre sémantique précis (ce que vous faites), ne peut vous conduire que vers une mauvaise compréhension, voire dans l'erreur absolue !

Si on démontrait que la conjecture de Goldbach est indécidable dans la théorie AP, alors la proposition "tout nombre pair est égal à la somme de deux nombres premiers" serait "vrai" dans le modèle standard de AP, mais fausse dans d'autres modèles

[Superbenji]

Si on démontrait que la conjecture de Goldbach est indécidable dans la théorie AP, alors la proposition "tout nombre pair est égal à la somme de deux nombres premiers" serait "vrai" dans le modèle standard de AP, mais fausse dans d'autres modèles

Bonjour,
en repensant à cette discussion pendant que je m'endormais tranquillement au fond de mon lit, je me suis rendu compte qu'un truc m'échappe complètement.
Vous avez dit précédemment que si une proposition P est démontrable dans une théorie T, alors elle est valide (pour éviter "vraie", vilain mot) dans tout les modèles de T.
Si la proposition "la conjecture de Goldbach est indécidable dans la théorie AP" est démontrable dans AP, alors la conjecture de Goldbach est indécidable et donc valide dans tout modèles de AP, puisque que chaque modèle pense de son propre point de vue être le modèle standard.

Bien évidemment je viens de dire beaucoup de bêtises. Est ce qu'une démonstration d'indécidabilité dans une théorie T ne se fait jamais dans T ? Ou bien où se trouve la solution à mon embrouillage ?

[Médiat]

Bonjour

Vous avez dit précédemment que si une proposition P est démontrable dans une théorie T, alors elle est valide (pour éviter "vraie", vilain mot) dans tout les modèles de T.

Oui, je le confirme, c'est le théorème de complétude de Gödel

Si la proposition "la conjecture de Goldbach est indécidable dans la théorie AP" est démontrable dans AP, alors la conjecture de Goldbach est indécidable et donc valide dans tout modèles de AP, puisque que chaque modèle pense de son propre point de vue être le modèle standard.

Non, "Le modèle standard de AP a une particularité : c'est le modèle premier de AP, il est donc "inclus" dans tous les modèles, s'il existait un nombre pair qui ne soit pas la somme de deux nombres premiers (forcément plus petits), tous les modèles le contiendrait et donc Goldbach serait "fausse" et non indécidable.

Est ce qu'une démonstration d'indécidabilité dans une théorie T ne se fait jamais dans T ?

La méthode la plus usuelle pour démontrer l'indécidabilité d'une formule dans une théorie est de trouver un modèle de la théorie vérifiant la formule et un autre ne la vérifiant pas (le forcing de Cohen est justement une méthode qui permet de "construire" (*) un modèle vérifiant une formule particulière)

(*) Le forcing est un peu plus subtile que cela, mais c'est bien l'idée de fond

[andretou]

Si on démontrait que la conjecture de Goldbach est indécidable dans la théorie AP, alors la proposition "tout nombre pair est égal à la somme de deux nombres premiers" serait "vrai" dans le modèle standard de AP, mais fausse dans d'autres modèles

Vous voulez dire que l'arithmétique telle que formalisée par Peano contient un modèle standard ainsi que d'autres modèles ?
Si tel est le cas, pourriez-vous SVP expliquer la différence entre le modèle standard et les autres, et donner un exemple de modèle non-standard ?
Merci d'avance

[Médiat]

Vous voulez dire que l'arithmétique telle que formalisée par Peano contient un modèle standard ainsi que d'autres modèles ?

Non pas "contient" mais "possède" ; toutes les théories du premier ordre qui ont un modèle infini possède une infinité de modèles, AP n'a rien de particulier ici.

Si tel est le cas, pourriez-vous SVP expliquer la différence entre le modèle standard et les autres, et donner un exemple de modèle non-standard ?

Le modèle standard est le modèle premier (IN), tous les autres sont non-standard, malheureusement je ne peux pas vous donner un exemple à cause du théorème de Tennenbaum :

Il n'existe pas de modèle non-standard de l'arithmétique qui soit récursif.

C'est à dire où l'addition et la multiplication soient récursives ("définissables par un être humain").

Mais on sait démontrer (c'est même assez facile) qu'il y a exactement modèles dénombrables non isomorphes de AP (supposée consistante)