Définition complétude.

[invite7849ae55]

Dans un de mes livres de logique je vois :
« Nous avons expliqué que les axiomes d'un système déductif sont "complets" si toute assertion vraie que l'on peut exprimer dans ce système est formellement déductible à partir des axiomes. »
Sur Wikipédia je vois :
« Un système de déduction pour une logique donnée (calcul propositionnel, ou calcul des prédicats en logique classique mais aussi en logique intuitionniste ...), est complet quand il démontre les formules valides dans tous les modèles de cette logique. »

Mais qui semble en contradiction avec le théorème de complétude de Gödel car d'après lui toute théorie serait complète, ce qui rend la complétude assez pauvre finalement.


Et dans un autre livre de logique, de ce que j'ai compris ils définissent ça comme "toute formule close est décidable dans la théorie".

Serait-ce que tout le monde ait raison mais que je n'aie pas compris grand chose ?

Merci à vous, bonne journée.
-----

[PlaneteF]

Mais qui semble en contradiction avec le théorème de complétude de Gödel car d'après lui toute théorie serait complète, ce qui rend la complétude assez pauvre finalement.

Bonjour,

J'ai très peu de temps et donc je vais faire une réponse courte et rapide, mais ce n'est pas ce que dit le théorème de complétude de Godel. Tu confonds 2 objets mathématiques différents à savoir une logique formelle (en l'occurrence la logique du 1er ordre) et une théorie exprimée dans cette logique. La complétude dans ce théorème porte sur le 1er objet et non pas le 2e.

Cordialement

[Médiat]

Mais qui semble en contradiction avec le théorème de complétude de Gödel car d'après lui toute théorie serait complète, ce qui rend la complétude assez pauvre finalement.

Le théorème de complétude de Gödel ne dit absolument pas cela, il dit que la logique classique du premier ordre est complète (au sens de la complétude d'une logique), pas que les théories dans cette logique sont complètes (au sens de la complétude d'une théorie).

[invite7849ae55]

Je précise au cas où :

Le théorème de complétude de Gödel ne dit absolument pas cela

Je ne dis pas qu'il dise cela, je dis "d'après ces définitions ci dessus, en appliquant le théorème de complétude on aurait".
Mais visiblement on ne parle pas du même "théorème de complétude" ; je me suis dis qu'ayant le même nom et portant sur des objets similaires ça devait être les même mais visiblement il y a ambiguïté :
Dans un de mes livres, j'ai un théorème nommé "théorème de complétude" qui dit explicitement :
T une théorie, F une formule close

Le premier symbole utilisé ayant pour sens défini dans le livre "il existe un sous ensemble T' fini de T tel que le séquent soit démontrable"
et le second ayant pour sens défini dans le livre "F est valide dans T" soit "pour tout modèle M qui satisfait T, F est vraie dans M".

Dans ce même livre, la complétude est définie très clairement comme suit :
On dit que T est complète ssi pour tout formule close F on a ou
(ce qui me semble équivaloir à dire : T est complète ssi toute formule close est décidable)

Sauf que je la compare à une autre définition de la complétude dans un autre livre :
« Nous avons expliqué que les axiomes d'un système déductif sont "complets" si toute assertion vraie que l'on peut exprimer dans ce système est formellement déductible à partir des axiomes. »
Et d'après le théorème de complétude de mon premier livre (pas celui de Gödel donc) on a "tout ce qui est vrai est formellement déductible des axiomes" (c'est le sens que je comprends de la phrase ) donc d'après ce sens de "complétude" on aurait "toute théorie est complète", ce qui me semble assez étrange.

Je questionne donc cette dernière définition car elle me semble en total désaccord avec la première et les théorèmes de mon premier livre,.
Bonne journée.

[A voir en vidéo sur Futura]

[Médiat]

Et d'après le théorème de complétude de mon premier livre (pas celui de Gödel donc) on a "tout ce qui est vrai est formellement déductible des axiomes" (c'est le sens que je comprends de la phrase Pièce jointe 254271) donc d'après ce sens de "complétude" on aurait "toute théorie est complète", ce qui me semble assez étrange.

C'est bien le théorème de complétude (au sens de la logique utilisée), mais il n'y a aucun moyen d'en déduire que toute théorie est complète (au sens des théories)

[invite7849ae55]

Si on utilise la définition (que je questionne) « les axiomes d'un système déductif sont "complets" si toute assertion vraie que l'on peut exprimer dans ce système est formellement déductible à partir des axiomes. »
comme d'après le théorème de complétude « toute assertion vraie que l'on peut exprimer dans un système est formellement déductible à partir des axiomes. »
on a « les axiomes d'un système déductif sont "complets" » pour tout système déductif donc toute théorie.
On en déduit que toute théorie est complète.
Donc cette définition a un bug. Non ?

[Médiat]

on a « les axiomes d'un système déductif sont "complets" » pour tout système déductif donc toute théorie

D'où vient ce "donc" ? Parce que le cadre déductif est complet dans un certain sens, tout ce qui s'exprime dans ce cadre serait complet dans un autre sens ? Ce n'est pas dans la définition qu'il y a un bug.

A tout hasard, je ne vois pas comment vous pouvez affirmer que la théorie sur le langage à un seul symbole de relation binaire sans aucun axiome pourrait être complet.

[Médiat]

Le théorème de complétude de la logique classique du premier ordre dit que tout ce qui est déductible (et non pas que tout est déductible) est vrai dans tous les modèles et vice-versa.

Une théorie est complète si toute formule y est soit démontrable soit réfutable.

Comment faites-vous le lien entre ces deux notions ?

[invite7849ae55]

Je précise : quand j'écris mon raisonnement, je ne l'affirme pas, j'écris juste exactement ce que je pense pour que vous puissiez me dire où je fais une erreur s'il y en a une ; il n'y a aucune prétention de ma part rassurez vous, je tente juste de comprendre.

D'où vient ce "donc" ? Parce que le cadre déductif est complet dans un certain sens, tout ce qui s'exprime dans ce cadre serait complet dans un autre sens ?

Peut-être mon problème vient-il de là : pour moi un système déductif est un sous ensemble d'une théorie (associé à la logique utilisée pour la théorie de départ.) permettant de faire une démonstration pour une proposition donnée.
Je pense donc qu'une théorie est un système déductif.

Le théorème de complétude de la logique classique du premier ordre dit que tout ce qui est déductible (et non pas que tout est déductible) est vrai dans tous les modèles et vice-versa.

Une théorie est complète si toute formule y est soit démontrable soit réfutable.

Comment faites-vous le lien entre ces deux notions ?

Je n'en fais pas.
Justement, tout est là, vous avez pris l'autre définition de complétude d'une théorie (celle qui ne me pose pas de problème et qui est issue de mon premier livre).

Mais celle qui me pose problème est celle qui dit qu'un système déductif est complet ssi tout ce qui est vrai est démontrable, à savoir :
« les axiomes d'un système déductif sont "complets" si toute assertion vraie que l'on peut exprimer dans ce système est formellement déductible à partir des axiomes. »

[Médiat]

Peut-être mon problème vient-il de là : pour moi un système déductif est un sous ensemble d'une théorie (associé à la logique utilisée pour la théorie de départ.) permettant de faire une démonstration pour une proposition donnée.
Je pense donc qu'une théorie est un système déductif.

Non, un système déductif est l'ensemble des règles d'une logique qui permet de faire des démonstrations, une théorie n'est pas un système déductif, le système déductif usuel, c'est la logique du premier ordre, qui est complète.

[invite7849ae55]

Je pensais cela parce qu'ils parlaient d' "axiomes d'un système déductif" et non de "règles", j'ai donc mécaniquement pensé à une théorie et non une logique.
Donc comment comprenez vous la phrase :
« les axiomes d'un système déductif sont "complets" si toute assertion vraie que l'on peut exprimer dans ce système est formellement déductible à partir des axiomes. » ?
Avec votre intervention j'aurais tendance à comprendre cette phrase comme ça :
"les règles d'un système déductif sont complètes ssi toute assertion vraie dans une théorie utilisant ce système déductif est formellement déductible à partir des règles de ce système".

[Médiat]

"les règles d'un système déductif sont complètes ssi toute assertion vraie dans une théorie utilisant ce système déductif est formellement déductible à partir des règles de ce système".

C'est correct ; le mot axiome n'a pas toujours le même sens, mais c'est usuel de parler des axiomes d'une logique

[PlaneteF]

Bonjour,

Dans un de mes livres, (...)

Ce ne serait pas "Introduction à la logique - Théorie de la démonstration" chez Dunod par hasard ? ... Parce que cela y ressemble étrangement !

Cdt

[invite7849ae55]

Complètement