Comment démontre-t-on l'indécidabilité d'une proposition mathématique ?

[andretou]

Bonjour tout le monde
Il a été prouvé par Gödel qu'il existe des propositions mathématiques indécidables, c'est-à-dire dont on ne peut démontrer ni qu'elles sont vraies, ni qu'elles sont fausses.
Ainsi, il a été prouvé que le 1er problème de Hilbert (l'hypothèse du continu) est indécidable https://fr.wikipedia.org/wiki/Probl%C3%A8mes_de_Hilbert
Mais comment est-il possible de démontrer l'indécidabilité, de démontrer qu'une proposition n'est ni vraie ni fausse ???
En effet, pour démontrer qu'une proposition est vraie ou fausse, on fait appel à des théorèmes et aux propriétés qui en découlent pour parvenir, au terme de déductions et de raisonnements, à la conclusion logique qui s'impose. Parfois, dans le cas le plus simple, il suffit de trouver un contre-exemple à ladite proposition pour trancher.
Ainsi, un raisonnement "normal" permet normalement de conclure :
- soit qu'une proposition est vraie,
- soit qu'elle est fausse,
- soit qu'on ne sait pas.
Comment un raisonnement peut-il conduire à l'affirmation qu'une proposition n'est ni vraie ni fausse ?...
Auriez-vous SVP la possibilité de m'aider à comprendre cela ?
Merci pour vos réponses.
-----

[Médiat]

Bonsoir,

Une méthode fructueuse, utilisée d'ailleurs aussi bien pour AC que pour HC est de construire un modèle vérifiant la formule et un modèle vérifiant son contraire ; le théorème de complétude de Gödel permet de conclure.

Construire un modèle peut être pris dans un sens littéral ( pour prouver que la commutativité est indécidable dans la théorie des groupes, il suffit de trouver un groupe commutatif et un groupe non commutatif), ou dans le sens d'une construction à partir d'un modèle de la théorie supposé exister (cas de AC et HC)

Remarques :
Le vocabulaire vrai/ faux est source de confusion
La notion d'indécidable est toujours liée à une théorie

[andretou]

Une méthode fructueuse, utilisée d'ailleurs aussi bien pour AC que pour HC est de construire un modèle vérifiant la formule et un modèle vérifiant son contraire ;

Bonsoir Médiat
Ce principe consiste-t-il à établir qu'une proposition est vraie, et que son contraire est vrai également ?

[PlaneteF]

Bonsoir,

Ce principe consiste-t-il à établir qu'une proposition est vraie, et que son contraire est vrai également ?

Vrai dans un certain modèle (ou plusieurs) de la théorie, et faux dans un autre modèle (ou plusieurs autres) de la théorie. C'est la définition même de l'indécidabilité dans une théorie donnée, ... qui au passage d'une manière générale n'est absolument pas "capturée" par le 1er théorème d'incomplétude de Gödel comme cela était en filigrane dans ton 1er message, mais on a ce concept d'indécidabilité par construction même de la logique classique du 1er ordre. La meilleure illustration de cela est la commutativité qui est un indécidable de la théorie des groupes comme le mentionnait Médiat, ... aucun rapport avec les théorèmes d'incomplétude de Gödel.

Cordialement

[A voir en vidéo sur Futura]

[andretou]

Vrai dans un certain modèle (ou plusieurs) de la théorie, et faux dans un autre modèle (ou plusieurs autres) de la théorie.

Bonsoir PlaneteF
Je ne comprends pas la différence entre une théorie et un modèle de théorie.
Aurais-tu éventuellement un exemple pour me permettre de comprendre ?

[PlaneteF]

Je ne comprends pas la différence entre une théorie et un modèle de théorie.
Aurais-tu éventuellement un exemple pour me permettre de comprendre ?

De manière ultra macrosopique et simplifiée (je mets en gras les concepts fondamentaux à approfondir avec de véritables cours sur le sujet) :

Une théorie est une objet syntaxique définie à partir d'axiomes (qui ne sont que de simples formules closes, c'est-à-dire des formules sans variable libre), définis eux même à partir de l'ensemble des symboles de la logique classique (comme par exemple les symboles de quantification ou les connecteurs logiques, etc ...) et des symboles du langage de la théorie (c'est-à-dire le ou les symboles supplémentaires dont on a besoin pour la syntaxe des formules de la théorie). Par exemple pour la théorie des groupes on a besoin au minimum d'un symbole de fonction que l'on note généralement , ce qui va permettre d'écrire le ou les axiomes de la théorie. Par exemple on va écrire l'associativité comme ceci :



Tu remarqueras qu'à ce stade l'on ne fait que manipuler des symboles d'où le caractère syntaxique que j'évoquais au début.

Après on peut avoir une approche sémantique qui consiste à définir une interprétation du langage de travail, c'est-à-dire se donner un ensemble de travail (par exemple l'ensemble des entiers relatifs ) et donner ce que représente les différents symboles du langage (ex. l'addition des entiers relatifs notée + pour interpréter le symbole de fonction * dans l'exemple précédent). Ce qui donne pour la formule précédente :




Un modèle d'une théorie est une interpretation du langage de la théorie qui satisfait tous les axiomes de la théorie. Dans la théorie des groupes, il s'agit des groupes eux-mêmes.


Voili, voilou, pour un très, très rapide aperçu de certaines notions fondamentales qui sont en jeu et il y a bien d'autres. Maintenant il y a un véritable formalisme précis et rigoureux de ce que je viens de raconter, il faut se plonger dans les cours qui expliquent la conctruction de la logique classique, les cours de théorie de la démonstration, de théorie des modèles, etc ...


Cordialement

[Médiat]

Bonjour,

Pour compléter un peu l'explication (très claire) de PlaneteF : dans un modèle, il n'y a pas d'indécidable, chaque formule close y est soit vérifiée, soit c'est son contraire qui l'est.

D'où la nécessité absolue de citer toutes les hypothèses des théorèmes d'incomplétudes de Gödel, car par exemple, il n'y a pas d'indécidable dans la théorie constituée de toutes les formules vérifiées par le modèle standard de l'arithmétique de Peano (IN, s, +, X, 0)

[Médiat]

Ce principe consiste-t-il à établir qu'une proposition est vraie, et que son contraire est vrai également ?

Vous touchez du doigt la raison de ma défiance vis à vis de ce vocabulaire.

Il se trouve que depuis hier je suis en train d'écrire un petit article de vulgarisation sur le forcing (méthode mise au point et employée par P. Cohen pour montrer l'indécidabilité de AC et HC), j'en ai encore pour plusieurs semaines pour en faire quelque chose de "publiable", mais je vais nettoyer un peu ce que j'ai déjà écrit et le poster ici dans la journée, puisque c'est bien le même sujet.

[Médiat]

Comme promis.

Il s'agit d'un premier brouillon, dont le but final est le forcing, mais il me semble que certains passages explicitent ce qui a été dit ou sous-entendu ici.

N'hésitez pas à critiquer ce document (en particulier si vous pensez qu'il manque des choses), je me ferai un plaisir de le modifier/compléter.

[Médiat]

J'en profite pour mettre le doigt sur un point du message de PlaneteF :

Dans l'écriture syntaxique (axiomes de la théorie) on a

Les variables quantifiées ne sont pas astreintes à appartenir à un ensemble particulier, c'est, bien sûr, correct, mais c'est aussi parfaitement normal, à ce stade, il n'y a pas d'ensemble !

Par contre, dans l'écriture sémantique (à propos d'un modèle particulier) on a

Les variables quantifiées sont astreintes à appartenir à un ensemble particulier, ici pour que l'on sache de quoi on parle.

On aurait aussi pu l'écrire , ce qui met en évidence le lien syntaxique/sémantique.



Malheureusement le latex du forum ne connait pas \models, le symbole

[andretou]

Merci Médiat et PlaneteF !
J'ai encore 2 questions :
- peut-on définir différents modèles de théorie au sein de l'arithmétique ?
- a-t-on identifié des propositions indécidables au sein de l'arithmétique ?

[andretou]

Comme promis.

Il s'agit d'un premier brouillon, dont le but final est le forcing, mais il me semble que certains passages explicitent ce qui a été dit ou sous-entendu ici.

N'hésitez pas à critiquer ce document (en particulier si vous pensez qu'il manque des choses), je me ferai un plaisir de le modifier/compléter.

Je vous remercie vivement de nous faire part de vos travaux.
Je souhaiterais apporter un commentaire sur le début du paragraphe III :

Si on est capable de construire un modèle d’une théorie, vérifiant une formule, on peut en
déduire que le contraire de cette formule n’est pas démontrable dans cette théorie (puisqu’une
formule démontrable dans une théorie est vérifiée dans tous les modèles de cette théorie). Autrement
dit, pour démontrer qu’une formule est indécidable dans une théorie,  il suffit  d’exhiber
un modèle la vérifiant et un modèle vérifiant son contraire.

Ce passage suggère qu'il suffit de trouver un modèle d'une théorie vérifiant une formule pour en déduire que le contraire de cette formule n'est pas démontrable dans cette théorie...
Pour quelle raison, simplement en construisant un modèle dans lequel une formule est vérifiée, on peut déduire que le contraire de cette formule n'est pas démontrable dans cette théorie ??? J'avais cru comprendre que, pour démontrer l'indécidabilité, il fallait vérifier que la formule ne donnait pas le même résultat dans deux modèles différents (ce que semble confirmer la dernière partie de ce paragraphe).

[Médiat]

Bonjour,

peut-on définir différents modèles de théorie au sein de l'arithmétique ?

Je ne comprends pas ce que vous voulez dire . Plusieurs modèles de l'arithmétique de Peano ?

a-t-on identifié des propositions indécidables au sein de l'arithmétique ?

Il y a les formules (sans intérêt arithmétique) mises au point dans la démonstration des théorèmes d'incomplétude de Gödel.

Mais il y a aussi le théorème de Goodstein (qui n'est pas un théorème de AP, mais de ZF), voir les travaux de Kirby et Paris.

[Médiat]

Ce passage suggère qu'il suffit de trouver un modèle d'une théorie vérifiant une formule pour en déduire que le contraire de cette formule n'est pas démontrable dans cette théorie...
Pour quelle raison, simplement en construisant un modèle dans lequel une formule est vérifiée, on peut déduire que le contraire de cette formule n'est pas démontrable dans cette théorie ???

C'est correct, car si une formule était démontrable, elle serait vérifiée par tous les modèles

J'avais cru comprendre que, pour démontrer l'indécidabilité, il fallait vérifier que la formule ne donnait pas le même résultat dans deux modèles différents (ce que semble confirmer la dernière partie de ce paragraphe).

Oui, c'est correct, et ce n'est pas contradictoire avec ce qui précède

[andretou]

Je ne comprends pas ce que vous voulez dire . Plusieurs modèles de l'arithmétique de Peano ?

Oui.
Est-ce que tout système axiomatique comporte différents modèles ?

[Médiat]

Oui.
Est-ce que tout système axiomatique comporte différents modèles ?

D'abord, la notion de "différents modèles" ne se conçoit qu'à isomorphisme près, c'est à dire que "deux" modèles isomorphes sont considérés comme "un seul" modèle

Non, par exemple la théorie dans le langage égalitaire réduit à un seul symbole de constante (C) et possédant un seul axiome : ne possède qu'un seul modèle (à isomorphisme près)

Par contre toutes les théories ayant un modèle infini possède un modèle dans toutes les cardinalités infinies (théorème de Löwenheim-Skolem) qui ne peuvent pas être isomorphes, c'est d'ailleurs aussi le cas de toute théorie ayant des modèles finis arbitrairement grands.

Sans compter les théories inconsistantes qui n'ont pas de modèle

[andretou]

Donc l'arithmétique de Peano comporte elle aussi différents modèles ?

[Médiat]

Elle en comporte "d'autant plus" que cette théorie est essentiellement incomplète (on ne peut pas la compléter récursivement, c'est le premier théorème d'incomplétude de Gödel), donc quelque soit les axiomes que l'on ajoute (récursivement) il existera toujours plusieurs modèles dénombrables non élémentairement équivalents donc, a fortiori, non isomorphes de la nouvelle théorie.

Mais même une théorie complète (aucun indécidable) peut posséder plusieurs modèles non isomorphes dans une cardinalité donnée ; par exemple la théorie des ordres totaux, denses, sans extremums possède des "tas" de modèles non isomorphes en cardinal , mais un seul en cardinalité

[Médiat]

Pour compléter ma réponse sur les modèles dénombrables de AP :

De simples questions de dénombrement sur l'ensemble de base sur lequel on doit définir une constante, une fonction unaire et deux fonctions binaires permettent d'affirmer qu'il y a au plus modèles dénombrables de AP.


On définit un nouveau symbole de Predicat ( divise ).

Ci-dessous représentera les nombres premiers de .

Soit , et soit l'ensemble de formules pour :
Soit la théorie , par compacité la théorie est consistante (si Peano l'est) et donc possède au moins un modèle. De plus, un modèle ne peut réaliser qu'un nombre dénombrable de théories .

Comme il y a sous ensembles de l'ensemble des nombres premiers, AP a donc au moins modèles dénombrables

Donc, finalement, AP a exactement modèles dénombrables.

[invite9dc7b526]

Construire un modèle peut être pris dans un sens littéral ( pour prouver que la commutativité est indécidable dans la théorie des groupes, il suffit de trouver un groupe commutatif et un groupe non commutatif), ou dans le sens d'une construction à partir d'un modèle de la théorie supposé exister (cas de AC et HC)

je ne comprends pas bien: est-ce qu'il ne pourrait pas se faire qu'il existe des groupes commutatifs et d'autres non commutatifs et une procédure permettant de décider qui l'est et qui ne l'est pas?

[Médiat]

Bonjour minushabens,

Je ne comprends pas ce que vous voulez dire, ni même ce qui vous chiffonne dans ce que j'ai écrit ...

[Médiat]

minushabens,

Je crois avoir compris : vous confondez indécidabilité d'une théorie et indécidabilité d'une formule (dommage que ce soit le même nom, malheureusement c'est ainsi)

Indécidabilité d'une théorie : il n'existe pas d'algorithme permettant de "décider" si une formule est un théorème ou non
Indécidabilité d'une formule dans une théorie : ni la formule ni son contraire ne sont démontrables dans la théorie

[andretou]

Elle en comporte "d'autant plus" que cette théorie est essentiellement incomplète (on ne peut pas la compléter récursivement, c'est le premier théorème d'incomplétude de Gödel), donc quelque soit les axiomes que l'on ajoute (récursivement) il existera toujours plusieurs modèles dénombrables non élémentairement équivalents donc, a fortiori, non isomorphes de la nouvelle théorie.

Mais même une théorie complète (aucun indécidable) peut posséder plusieurs modèles non isomorphes dans une cardinalité donnée ; par exemple la théorie des ordres totaux, denses, sans extremums possède des "tas" de modèles non isomorphes en cardinal , mais un seul en cardinalité

J'ai une dernière question sur l'arithmétique de Peano.
A-t-on découvert une proposition indécidable au sein de cette théorie ?

[Médiat]

Je vous ai déjà répondu au message #13

je peux ajouter le théorème de Ramsey fini dont Paris (le même) et Harrington ont montré l'indécidabilité dans AP

[andretou]

Je vous ai déjà répondu au message #13

je peux ajouter le théorème de Ramsey fini dont Paris (le même) et Harrington ont montré l'indécidabilité dans AP

Je vous remercie.
Mais est-ce que ces exemples d'indécidabilité au sein de l'arithmétique ont éventuellement une traduction concrète, accessible au profane (du genre "tout nombre pair est égal à la somme de 2 nombres premiers"...) ?

[PlaneteF]

Bonjour,

Mais est-ce que ces exemples d'indécidabilité au sein de l'arithmétique ont éventuellement une traduction concrète, accessible au profane (du genre "tout nombre pair est égal à la somme de 2 nombres premiers"...) ?

https://fr.wikipedia.org/wiki/Th%C3%...e_de_Goodstein

https://fr.wikipedia.org/wiki/Th%C3%...A8me_de_Ramsey

Cordialement

[PlaneteF]

Un article de Patrick Dehornoy sur les suites de Goodstein :

http://www.math.unicaen.fr/~dehornoy/Surveys/Dgm.pdf

[andretou]

Merci pour ces exemples.
Si j'ai bien compris, les postulats de Goodstein et de Ramsay sont donc indécidables si l'on s'en tient à l'arithmétique, mais peuvent être démontrés en faisant appel à des théories mathématiques plus "fortes" que l'arithmétique (et sont de ce fait des théorèmes).
Est-ce à dire que pour résoudre tout problème indécidable, il "suffit" d'employer une théorie plus forte ?
Ou, au contraire, certains problèmes sont-ils absolument indécidables quelle que la soit la théorie avec laquelle on les manipule ?
L'indécidabilité de l'hypothèse du continu est-elle ainsi "absolue", ou peut-on espérer la réduire ?

[Médiat]

Bonjour,

Ce ne sont pas des postulats, mais des formules, qui sont indécidables dans AP et des théorèmes dans ZFC.

Une formule f indécidable dans une théorie T est toujours un théorème dans d'autres théories, ne serait-ce que dans T U {f}.

[andretou]

Une formule f indécidable dans une théorie T est toujours un théorème dans d'autres théories, ne serait-ce que dans T U {f}.

Donc l'hypothèse du continu n'est pas absolument indécidable ?