Non-contradiction versus consistance

Bonjour,

J'ai du mal à saisir la nuance (s'il y en a une) entre consistant et non-contradictoire. Est-ce la même chose pour le premier ordre ?
Après quelques recherches dans les archives, j'ai presque trouvé une réponse, mais j'hésite encore...\\

Principe de non-contradiction : \\
Un ensemble d'énoncés $\Sigma$ est non-contradictoire $\Longleftrightarrow\forall \phi\in\Sigma$, on ne peut pas avoir simultanément $\Sigma\models\phi$ et $\Sigma\models\neg\phi$.\\

Théorème de complétude de Gödel :\\
Un ensemble d'énoncés $\Sigma$ est \textbf{consistant} $\Longleftrightarrow\Sigma$ possède un modèle.\\
Autre version :\\
Il existe un ensemble d'énoncés $\Sigma$ telle que $\forall \phi\in\Sigma,\quad\phi\models\phi'\Longrightarrow\phi\vdash\phi'$.\\
Ou encore :\\
Il existe une théorie $T$ dans laquelle tout énoncé universellement vrai est démontrable.\\

Avec les définitions :\\
Un énoncé $\phi$ est \textbf{universellement vrai} (ou une loi logique) si $\mathcal M\models\phi$ pour tout modèle $\mathcal M$.\\
$\Sigma \vdash
\phi\Longleftrightarrow$ pour tout $\mathcal M$ modèle de $\Sigma$, \quad $\mathcal M\models\phi$.\\
Un énoncé $\phi$ est \textbf{démontrable} s'il existe un ensemble d'énoncés $\Sigma$ tel que $\Sigma\vdash\phi$.\\

J'ai faux ou j'ai pas raison ?

Autre question, similaire, cette fois pour la complétude d'une théorie : est-elle équivalente au principe du tiers exclu, ou ce dernier n'en est-il qu'une propriété ?

Merci pour votre aide

Réponses

  • Tigerfou a écrit:
    J'ai du mal à saisir la nuance (s'il y en a une) entre consistant et non-contradictoire. Est-ce la même chose pour le premier ordre ?

    Bah tout dépend de tes définitions de ces deux termes. L'homme de la rue donne souvent la même pour l'un et l'autre, mais j'imagine que les experts doivent tenir à leurs conventions en la matière (très certainement complètement différentes d'un expert à l'autre).


    Bref, tu as compris qu'une théorie $\Sigma$ avait deux façons d'entraîner la nécessité d'une formule $\phi$ :
    $(1) \Sigma\vdash\phi$ : on peut démontrer $\phi$ en rajoutant les formules de $\Sigma$ aux axiomes logiques
    $(2) \Sigma\models\phi$ : tout modèle de $\Sigma$ valide $\phi$ (la réalisation de $\phi$ dans un modèle de $\Sigma$ est vraie).


    Une première remarque est que $(1) \Rightarrow (2)$ : c'est le théorème de consistance, qui est vrai dans le formalisme du premier ordre, mais qui a de toutes façon intérêt à être vrai dans n'importe quel formalisme où l'on propose une notion de modèle, sans quoi notre notion est à jeter.


    Tu as vu aussi que $(2) \Rightarrow (1)$ : ce type de théorème s'appelle théorème de complétude, et au premier ordre on en a un de toute beauté (merci Gödel). Note : c'est cool d'avoir un théorème de complétude, mais il existe des formalismes pour lesquels on a une notion de modèle qui malheureusement ne vérifie pas de théorème de complétude (on essaie d'éviter, quand même).


    Finalement, tu as vu qu'au premier ordre $(1) \Leftrightarrow (2)$, donc l'existence d'une formule $\phi$ telle que $\Sigma\vdash\phi$ et $\Sigma\vdash\neg\phi$, ou l'existence d'une formule $\phi$ telle que $\Sigma\models\phi$ et $\Sigma\models\neg\phi$, c'est du kif. Après, appeler une théorie vérifiant une des deux propriétés "contradictoire", et une théorie vérifiant l'autre "non consistante", vu que finalement ça veut dire la même chose, ça n'est pas très important.


    Remarque (petit exercice facile) : on a équivalence entre
    $\cdot$ il existe une formule $\phi$ telle que $\Sigma\vdash\phi$ et $\Sigma\vdash\neg\phi$
    $\cdot$ pour toute formule $\phi$, $\Sigma\vdash\phi$ et $\Sigma\vdash\neg\phi$

    Ce qui nous fait encore une troisième définition possible.


    Autre question, similaire, cette fois pour la complétude d'une théorie : est-elle équivalente au principe du tiers exclu, ou ce dernier n'en est-il qu'une propriété ?

    Je ne suis pas sûr qu'on emploie le terme "complétude" pour signifier qu'une théorie est complète.


    En tout cas, ça n'a absolument rien à voir avec le tiers-exclus. Le tiers exclus est un axiome logique. Dans le formalisme classique des langages du premier ordre, il fait partie des axiomes logiques. En particulier, pour tout langage du premier ordre, pour toute théorie $\Sigma$ dans ce langage, pour toute formule $\phi$, on a $\Sigma\vdash\phi \vee \neg\phi$. Mais il sera rare qu'on ait $\Sigma \vdash\phi$ ou $\Sigma\vdash\neg\phi$.


    Par exemple, dans le langage de l'appartenance, la théorie $\Sigma=ZF$ des ensembles n'est pas complète. Explicitement, pour $\phi=$l'hypothèse du continu, on n'a ni $\Sigma\vdash\phi$ ni $\Sigma\vdash\neg\phi$.
    Mais on a bien $\Sigma\vdash\phi \vee \neg\phi$.


    C'est d'ailleurs un peu énervant, et c'est une motivation possible pour utiliser d'autres formalismes dans lesquels le tiers-exclus ne fait pas partie des axiomes logique (c'est-à-dire pour lesquels la logique sous-jacente est intuitionniste).
  • Merci le barbu rasé pour ces précisions !

    Concernant le tiers exclu, je voulais dire que (sauf en logique intuitionniste), on a $\neg\neg p=p$ d'où $\neg(p\wedge\neg p)\Longleftrightarrow\neg p\vee p$...

    En fait ma confusion vient du fait que je mélangeais les deux : $\Sigma\vdash\phi \vee \neg\phi$ est différent de $\Sigma\vdash\phi \vee \Sigma\vdash\neg\phi$, me trompe-je ?\\

    Donc si je résume :\\

    Dans toute théorie $\Sigma$, pour toute formule $\phi$, on a $\Sigma\vdash\phi \vee \neg\phi$ (Tiers exclu).\\
    Ce qui signifie que de $\phi$ et $\neg\phi$, une des deux est universellement vraie, mais aucune n'est forcément démontrable (on peut avoir du vrai non-démontrable).\\

    Dans une théorie complète, on a $\Sigma \vdash\phi$ ou bien $\Sigma\vdash\neg\phi$.\\
    Ce qui signifie que de $\phi$ et $\neg\phi$, une des deux est nécessairement démontrable, et comme on sous-entend théorie non-contradictoire, c'est au plus une, donc finalement, exactement une des deux est démontrable, c'est le cas idéal.\\

    @deufeufeu : merci pour le lien, j'avais déjà vu ton message qui m'avait quasiment convaincu :)
  • TigerFou a écrit:
    En fait ma confusion vient du fait que je mélangeais les deux : $ \Sigma\vdash\phi \vee \neg\phi$ est différent de $ \Sigma\vdash\phi \vee \Sigma\vdash\neg\phi$, me trompe-je ?

    Tu ne te trompes pas. Ça n'a rien à voir.

    TigerFou a écrit:
    Dans toute théorie $ \Sigma$, pour toute formule $ \phi$, on a $ \Sigma\vdash\phi \vee \neg\phi$ (Tiers exclu).
    Ce qui signifie que de $ \phi$ et $ \neg\phi$, une des deux est universellement vraie, mais aucune n'est forcément démontrable (on peut avoir du vrai non-démontrable).

    Pas du tout. Ça signifie que $\phi \vee \neg\phi$ est démontrable, ce qui est trivial puisque c'est un axiome.

    Via le théorème de complétude, cela équivaut à dire que tout modèle valide $\phi \vee \neg\phi$, ce qui signifie effectivement que tout modèle valide l'une des deux (si $phi$ est close).

    Dire que l'une des deux est universellement vraie, c'est dire que tout modèle valide la même. Il n'y a aucune raison que ce soit le cas. On sait simplement que si $\phi$ est close, il existe des modèles qui valident $\phi$, et d'autres (les autres) qui valident $\neg\phi$.


    Quant à l'expression "vrai non-démontrable", elle ne me plaît guère. Tu peux avoir en tête un modèle bien précis de ta théorie et appeler "vraie" une formule validée par ce modèle, mais ça reste subjectif. Somme toute, mieux vaut ne pas employer le mot "vrai"...
  • Bonsoir,

    je n'irai pas jusqu'à jeter le terme "vrai" à la poubelle, il faut juste que je n'oublie plus qu'il n'a de sens que par rapport à un modèle (ou à un ensemble d'axiomes).
    C'est un peu comme de parler de pourcentage sans référer à quoi en somme...

    Merci pour ton aide !

    Cordialement
  • je n'irai pas jusqu'à jeter le terme "vrai" à la poubelle, il faut juste que je n'oublie plus qu'il n'a de sens que par rapport à un modèle (ou à un ensemble d'axiomes).

    A bin, il te reste encore une marche à franchir... (comme dans le feuilleton kung fu)

    C'est quand tu l'auras jeté que tu accèderas à la "vraie" sagesse

    qu'il n'a de sens que par rapport à un modèle

    même pas...

    Un prémodèle est simplement une application de 'lensemble des phrase dans {vrai;faux} et un modèle est un prémodèle ayant certaines propriétés supplémentaires (algébriques) mais {vrai;faux} pourrait aussi bien être {prune; pomme} ou {0;4}
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • à ceci près que ça n'aiderait pas beaucoup l'étudiant qui voudrait comprendre la motivation qui pousse à appeler modèle d'une théorie une interprétation du langage qui rende "prune" tous les énoncés de la théorie .. La vie est déjà assez compliquée quand on prend soin des mots qu'on utilise pour s'exprimer ..
  • Certes...
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • Bonjour,
    qu'il n'a de sens que par rapport à un modèle

    même pas...

    Je vais faire le mauvais élève, mais je n'ai pas compris ta réponse...

    Que le mot "vrai" puisse être remplacé par "prune" ou n'importe quel autre ne me dérange pas, du moment que leur fonction est la même... c'est le sens intuitif que l'on associe au terme "vrai" qui pose problème içi, puisque la théorie des modèle propose soit de le redéfinir, soit d'utiliser à sa place les termes de "satisfaction", "démonstration" (équivalents au premier ordre, si je suis bien) et "démontrabilité" qui eux sont définis de manière formelle, ie non-ambigüe.
    (pourtant au cours de mes lectures, j'ai bien vu que beaucoup de termes différents existent pour désigner la même chose !)


    Reprenons, d'une façon différente. Qualités possibles d'une proposition p exprimée dans une théorie T axiomatisée par A :

    - p satisfaite dans tout modèle de A, cad p démontrable à partir de A (en particulier p est satisfaisable). On peut dire que p est vraie dans la théorie T.

    - il existe un modèle1 de A dans lequel p n'est pas satisfaite et un modèle2 de A dans lequel elle est satisfaite. p est satisfaisable et falsifiable dans T donc est indépendante de l'axiomatique A. Comme p et non p ne sont ainsi pas démontrables dans T, p est indécidable logique. p est vraie pour le modèle2 et fausse pour le modèle1 tout en étant indémontrable dans la théorie (je n'ai fait qu'attribuer au terme "vrai" le sens de "satisfait").


    De ce point de vue, la théorie des modèles permettrait bien de corriger la notion grecque de vérité en la dissociant de la démontrabilité et en la faisant correspondre à la satisfaction (dans un ou modèle précis d'une certaine axiomatique), non ? Y a-t-il quelque chose de plus que je ne vois pas ?

    Est-ce que je me rapproche de cette marche vers la "vraie" sagesse, ou bien je divague et sombre dans l'incompréhension totale, maitre Kwai Chang ?

    Merci pour vos lumières
  • Salut TigerFou,

    Je crois que tu te focalises sur une boutade de Christophe.
    c'est le sens intuitif que l'on associe au terme "vrai" qui pose problème içi, puisque la théorie des modèle propose soit de le redéfinir, soit d'utiliser à sa place les termes de "satisfaction", "démonstration" (équivalents au premier ordre, si je suis bien) et "démontrabilité" qui eux sont définis de manière formelle, ie non-ambigüe.

    Grâce aux théorèmes de complétude et de consistance, la démonstrabilité d'une formule dans une théorie équivaut à sa validation universelle par cette théorie. Je pense que terme de satisfiabilité est plutôt utilisé pour dénoter l'existence d'un modèle qui valide la formule.


    Je récapitule (je ne sais pas si mes notations sont standard) :
    $\cdot$ $\Sigma \models_\mathcal{M} \phi$ : dans le modèle $\mathcal{M}$ de $\Sigma$, l'interprétation de $\phi$ est valide.
    $\cdot$ $\phi$ est satisfiable dans $\Sigma$ : il existe un modèle $\mathcal{M}$ de $\Sigma$ tel que $\Sigma \models_\mathcal{M} \phi$
    $\cdot$ $\phi$ est universellement valide dans $\Sigma$ : pour tout modèle $\mathcal{M}$ de $\Sigma$, $\Sigma \models_\mathcal{M} \phi$
    $\cdot$ $\phi$ est démontrable dans $\Sigma$ : on peut démontrer $ \phi$ en rajoutant les formules de $ \Sigma$ aux axiomes logiques
    En général, seuls les deux derniers points sont équivalents au premier ordre.


    Encore une fois, ça n'est pas sur le sens des termes que je veux insister (libre à nous d'utiliser les mots dans le sens qu'on veut, et je peux te garantir que les gens ne se privent pas) mais sur les différentes notions mises en jeu.


    p satisfaite dans tout modèle de A, cad p démontrable à partir de A (en particulier p est satisfaisable). On peut dire que p est vraie dans la théorie T.

    Si tu veux, mais je te signale que tu as précédemment utilisé le mot "vrai" dans un autre sens, très proche de "satisfiable" («je pense à un modèle en particulier, et ce modèle valide $\phi$»).

    il existe un modèle1 de A dans lequel p n'est pas satisfaite et un modèle2 de A dans lequel elle est satisfaite. p est satisfaisable et falsifiable dans T donc est indépendante de l'axiomatique A.

    Oui, mais note bien que ce donc dépend du théorème de consistance.

    p est vraie pour le modèle2 et fausse pour le modèle1 tout en étant indémontrable dans la théorie (je n'ai fait qu'attribuer au terme "vrai" le sens de "satisfait").

    Ce qui fait encore un troisième sens.

    De ce point de vue, la théorie des modèles permettrait bien de corriger la notion grecque de vérité en la dissociant de la démontrabilité et en la faisant correspondre à la satisfaction (dans un ou modèle précis d'une certaine axiomatique), non ? Y a-t-il quelque chose de plus que je ne vois pas ?

    Non. Tu as parfaitement compris : on dissocie ces deux notions (pour les relier ensuite par consistance et complétude).

    Ensuite, en tirer des conclusions philosophiques sur une "correction de la notion grecque de vérité" est certainement louable, mais ne ressort plus des mathématiques. :D

    Est-ce que je me rapproche de cette marche vers la "vraie" sagesse, ou bien je divague et sombre dans l'incompréhension totale, maitre Kwai Chang ?

    Je laisse le soin à Christophe de te répondre, mais je doute que la sagesse puisse s'acquérir sous l'enseignement d'un maître (c'est plutôt quelque chose à trouver par soi-même). ;)

    Pour répondre à la question que tu ne formules pas : il me semble que tu as bien saisi les différentes notions mises en jeu, et que tu seras d'autant plus à l'aise avec si tu es amené à les manipuler.
  • C'est assez long et assez technique, mais il semble que tu comprends... (sans maitre lol)

    Version light

    On se donne un ensemble V de 2 symboles différents, l'un qu'on appelle le vrai et l'autre le faux. Pour aller plus vite, je pose -vrai=faux et -faux=vrai

    (je simplifie avec un seul signe parce que ça semble ne pas te poser de problème cette partie là)

    On appelle "phraso" un ensemble (ses éléments seront appelés "phrases") muni (au moins) d'une opération binaire notée "et" et d'une orération unaire notée "non"

    Dans la suite, on se donne un phraso L

    On appelle prémodèle une application de L dans V

    On dit que le prémodèle M satisfait P si M(P)=vrai.

    On appelle conviction(M) l'ensemble des phrases P telles que M(P)=vrai

    Un prémodèle est dit modèle quand M(non(P)) = -M(P) et quand M(P et Q)=vrai ssi M(P) et M(Q) sont tous les 2 égaux à vrai, pour toute phrase dans L (tu remarqueras le petit cercle vicieux qui permet au français de revendiquer sa part de pertinence...)

    Soit T inclus dans L. T est appelée une théorie.

    Il exsite des notions de démonstrations que je ne précise pas ici, toutes cernant robustement la même chose technique qui sont des ensembles D de couples (T;P) à comprendre comme (T;P) est dans D signifie que on peut prouver P à l'aide d'axiomes dans T


    Un (pré)modèle M satisfait T quand T est inclu dans conviction de(M)

    Fixons un D (parmi les plus courants), en fait ils sont tous égaux car:


    Pour certains phraso (en fait tous ceux qui concernent les maths)** le théorème de complétude dit, à propos de ces D:

    Si tous les modèles M qui satisfont T sont tels que M(P)=vrai alors (T,P) est dans D

    En maths, D et L sont généralement toujours les mêmes ensembles, mais à priori, tout ceci est très général

    Ce sont des phraso qui ont la propriété suivantes:

    je ne peux pas faire les signe inférieur à cause du html, donc j'utilise: R

    Soit L un phraso

    Soit R_L la plus petit relation binaire transitive contenant les couples (P;non(P)) et (P; P et Q) et (Q; P et Q) et

    L est appelé "phraso" mathématique quand R_L est bien fondée.

    Le théorème de complétude s'y applique.

    Tu remarqueras à quel point le mot "vrai" a joué un rôle... Non seulement, il fait toujours partie des données, mais en plus il n'en toujours partie qu'en tant que mot
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • Merci Le barbu rasé pour ces confirmations !\\

    christophe j'ai un peu de mal à te suivre... ce que tu dit me semble très intéressant, mais si je comprends à peu près tes définitions et ton théorème de complétude, je ne comprends pas leurs liens avec la version de la théorie des modèles que je connais...
    Je vais essayer de reformuler cela avec le langage de la théorie des modèles et en ajoutant ton application .\\

    Ce que tu appelles un phraso (j'aime bien le terme :)) serait un ensemble $L$ (de phrases)\\
    [EDIT : formant une $\mathcal L_{\in}$-structure avec pour langage l'appartenance et les constantes vrai et faux.\\
    $V=\{$vrai,faux$\}$ sous-ensemble de L et on les définit opposés, cela suffit.]\\

    Soit donc $M : L\longrightarrow V$ ce que tu appelles un prémodèle. C'est cette définition que j'ai un peu de mal à saisir car $M$ n'est pas une structure...\\
    J'ai envie d'utiliser la $\mathcal L_{\in}$-structure $\mathcal M=<L,M,\in, vrai,faux>$\\
    $\mathcal M$ satisfait $p\in L \Longleftrightarrow M(p)=vrai$. Notons $\mathcal M\models p$\\

    $\mathcal M$ est un modèle ssi $M(\neg p)=-M(p)$ et $M(p\wedge q)=vrai\Longleftrightarrow M(p)=M(q)=vrai$\\
    Autrement dit $M(p)\neq M(\neg p)$ cad on a une clause de non-contradiction et $\wedge$ remplit son rôle logique.\\

    Soit $T\subset L$ une théorie.\\
    $\mathcal M$ satisfait $T\Longleftrightarrow T\subset M^{-1}(\{vrai\})\Longleftrightarrow \mathcal \forall p\in T, \, \mathcal M\models p$. Là en gros on dit justement que $\mathcal M\vdash p$ ? Je comprends pas l'histoire des couples D...\\

    Théorème de complétude : Pour tout modèle $\mathcal M$ qui satisfait $T$, on a $M(p)=vrai \Longrightarrow T\vdash p$\\
    traduction, tout énoncé vrai dans $T$ pour $\mathcal M$ est démontrable.\\

    Voilà a peu près ce que j'ai cru comprendre, j'espère n'avoir pas dit trop de bêtises. Je vais réfléchir encore à tes ensembles D.
    En tout cas merci pour cet exercice de reformulation intéressant !
  • Pardon de te répondre si tard

    Je lis...
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • Tu sembles avoir tout compris SAUF un point vraiment important

    Tu dis:

    Théorème de complétude : Pour tout modèle $\mathcal M$ qui satisfait $T$, on a $M(p)=vrai \Longrightarrow T\vdash p$\\
    traduction, tout énoncé vrai dans $T$ pour $\mathcal M$ est démontrable.\\


    Or je n'ai pas du tout écrit ça:

    En traduisant, j'ai écrit:

    Théorème de complétude : SI [pour tout modèle $\mathcal M$ qui satisfait $T$, on a $M(p)=vrai]$ ALORS $[T\vdash p]$\\
    traduction, tout énoncé déclaré vrai par tous les modèles de $T$ est démontrable à partir de T
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • Sans symbole cabalistique, ce que je voulais te dire est très général:

    Le théorème de complétude n'est pas un truc particulier à la logique, mais plutôt un phénomène général

    Si tu veux comprendre ne regarde que le théorème de complétude de la logique propositionnelle, et mon invitation est de ne pas trop te prendre la tête avec le premier ordre qui ne rajoute rien de pertinent en ce qui concerne cet aspect-là des choses.

    Par ailleurs cette "découverte" est aussi celle qu'il n'y a pas 36000 façons de définir les notions de démontrations, mais essnetiellement une seule.


    La plus naive, mais la plus édifiante est la suivante:

    Tu pars des axiomes logiques

    [(A-->P) et ((nonA)-->P)] implique P (***)

    et de quelques autres et tu as un théorème de complétude pour la notion D de démonstration où la seule règle est le modus ponens (ie de A--P et A déduire P) et la conjonction (ie après avoir prouvé A et prouvé B, on peut prétendre avoir prouvé "A et B")

    Preuve:

    soit T un ensemble de phrases, contenant les axiomes logiques

    on regarde le jeu suivant:

    il y a une phrase courante qui change au cours du jeu:

    P étant la phrase courante, le prouveur a le droit de proposer au sceptique de choisir entre A--->P et A comme nouvelle phrase courante

    la règle est que le prouveur gagne si au bout d'un temps fini, la phrase courante est dans T

    S'il n'y a pas de modèle (prémodèle vérifiant quelques propriétés algébriques déjà précisées) contenant non(P) voici une manière très simple de gagner:

    tu ranges toutes les phrases A_n dans une suite et à chaque étape n tu proposes *** au sceptique avec A:=A_n et P:= phrase courante

    si tu n'es pas en position facile à gagner pour toi à au moins un moment de la partie alors à la fin de la partie l'ensemble des "hypothèses"* d'au moins une phrase courante de la partie est un BON modèle de nonP,

    les hypothèse de A-->B sont A ainsi que les hypothèses de B (def par induction)

    Si en tant que prouveur tu as une stratégie gagnante alors il y a une preuve de P avec des axiomes dans T

    Pour conclure, il te reste juste à prouver que ce jeu est "déterminé" (ie que le sceptique a une stratégie infaillible ou que le prouveur en a une)

    Le premier ordre n'est qu'un avatar de logique propositionnelle où on donne à R(a,b,c) le statut de phrases et où on doit gérer des liaisons de variables, ce qui ne change pas gd chose.

    Mais ce que je te dis là est plus une invitation qu'un cours par contre, vois tes motivations et si tu n'es pas encore trop familier de logique, restes-en un temps à la cabalistique classique

    Je te donne un slogan qui permet de se rappeler tout ceci: le théorème de complétude n'est que l'annonce du fait qu'une théorie consistante a des modèles: les théories complètes qui la contiennent

    Et par ailleurs "être une théorie complète" est une notion "compacte" et même algébrique (et Zorn fait le reste)
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • CC a écrit:
    Par ailleurs cette "découverte" est aussi celle qu'il n'y a pas 36000 façons de définir les notions de démontrations, mais essentiellement une seule.

    Attention, écrite telle quelle, cette croyance n'engage que son auteur.
  • J'avoue que c'est "du café du commerce", par contre pour tiger, le slogan ci-dessus est important, je pense:

    "une théorie complète est un modèle"

    Ca permet de comprendre le théorème de complétude rapidement sur le fond

    Par exemple, Tiger peut s'essayer à l'exercice suivant:

    Prendre un ensemble E de phrases muni de quelques opérations:

    Les prémodèles sont les éléments de 2^E

    On munit E de la topologie produit de la discrête sur 2

    Définir une "bonne notion" de modèle (***), l'ensemble des modèles sera alors un FERMé dans 2^E

    Les théories finies sont des parties de E

    Si T est une partie finie de E

    L'ensemble des prémodèles de T est à la fois ouvert et fermé

    Si T n'est plus forcément finie, l'ensemble des modèles de T est quand-même un fermé

    Si T n'a pas de modèle il existe un ensemble fini T2 inclus dans T qui n'a pas de modèle

    Et la découverte du siècle (donnée par les définitions elles-mêmes!!!), c'est que la liste des "T2 n'a pas de modèle" (quand T2 est fini) est ressemble à une notion de démonstration du genre "la conjonction des phrases dans T2 impliquent tout" qu'il reste à étudier (mais ça c'est plus que la partie "logique booléenne" en quelque sorte
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • Bonjour,

    Merci pour la correction et les précisions.
    Si tu veux comprendre ne regarde que le théorème de complétude de la logique propositionnelle, et mon invitation est de ne pas trop te prendre la tête avec le premier ordre qui ne rajoute rien de pertinent en ce qui concerne cet aspect-là des choses.

    Le premier ordre m'intéresse en rapport à l'axiomatisation...

    Je récapitule le sens des deux théorèmes, et après je m'arrête parce que je crains de m'embrouilller...

    Théorème de complétude de la logique propositionnelle : universellement vrai => démontrable
    Donc il entraine que l'on a équivalence entre le point de vue sémantique et le point de vue syntaxique puisque l'autre sens est donné par le théorème de fiabilité (ou comme dit le barbu rasé "de consistance").
    Il entraine aussi que toute théorie complète est un modèle.

    Théorème de complétude de Gödel : au premier ordre, consistant <=> possède un modèle
    Autrement dit la théorie du calcul des prédicats du premier ordre est complète.
    Ou encore toute théorie exprimée dans cette théorie (le calcul des prédicats du premier ordre) est complète (par compacité).
    Encore une autre façon de le dire, toute théorie exprimée dans cette théorie (le calcul des prédicats du premier ordre) est axiomatisable.

    Au ordres supérieurs, une théorie consistante n'a pas forcément de modèle, donc n'est pas forcément axiomatisable.
    Dernière question (après je m'arrêterai là, promis) En revanche, une théorie consistante et complète est-elle toujours axiomatisable ?
    (Je sais que si elle contient l'arithmétique elle ne peut pas être à la fois consistante et complète, mais cela n'aide pas)

    Cordialement
  • je n'ai pas bcp de tps, mais la réponse est "non", mais qu'entends-tu par "axiomatisable" (pour bcp de logiciens, ils entendent par là "ensemble récursivement énumérable d'axiomes)?. Sinon, si tu penses à juste "ensemble d'axiomes", bin ya qu'à prendre les énoncés de la théorie...

    Certaines théories sont complètes, consistantes et l'ensemble des énoncés qu'elles contiennent sont récursifs

    par exemple: les corps algébriquement clos de caractéristique 0. 2 tels corps ont le même ensemble vérité. Ca tient au fait qu'un énoncé qui commence par R(a,b,c..)="il existe x" suivi d'un polynome P(x,a,b,c...peut être démontré équivalent à un énoncé sans quantificateurs S(a,b,c..) (uniformément, ie pour tout a,b,c.. (il existe x R(x,a..)) équivaut à S(a,..))
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • Bonjour,

    Pardon pour mon temps de réaction, j'ai été obligé d'abandonner un peu ce thème de réflexion ces dernières semaines...

    Merci christophe pour ta réponse.
    En fait, par axiomatisable je voulais simplement dire possédant un ensemble d'axiomes énumérable (pas nécessairement récursivement).

    Mais puisque le théorème de complétude du calcul propositionnel revient à dire que l'ensemble des propositions logiques est énumérable, toute axiomatique est énumérable donc... c'est nul comme critère puisqu'on peut prendre toutes les propositions de la théorie, comme tu le signales. C'est ok pour ça.

    Je crois que ce qui m'a un peu perturbé c'est cette affirmation lue dans un article sur la théorie des modèles :
    <<Mais A4 (le principe de récurrence) n’est pas un énoncé du premier ordre.
    Dans le premier ordre, en effet, on ne quantifie que sur des variables d’individu, non
    sur des propriétés. La quantification sur les propriétés (des individus) est du second
    ordre ; or la logique du second ordre n’est pas axiomatisable. Ce qui signifie que ($\Sigma\vdash p <=> p$ est une conséquence de $\Sigma$) n’est pas vrai pour des formules du second ordre.>>

    Est-ce que je n'ai toujours pas compris quelque chose ou est-ce que cette citation est formulée de manière ambigue ? (edit : parceque je ne comprends pas ce qui est en gras)

    Merci encore
Connectez-vous ou Inscrivez-vous pour répondre.