Complétude ou incomplétude ?

Bonjour à tous,

quelqu'un pourrait-il m'expliquer brièvement chacun des théorèmes car j'arrive à une contradiction.

De ce que j'ai compris, en très gros :

théorème de complétude (dans une théorie du premier ordre) : cohérence équivaut à avoir un modèle ensembliste, de plus conséquence sémantique équivaut à conséquence syntaxique.

théorème d'incomplétude : une théorie cohérente qui exprime l'arithmétique de Péano est incomplète (notamment sa cohérence n'est pas démontrable)

La démonstration du th d'incomplétude repose sur un énoncé G qui est vrai dans N mais pas démontrable, mais pourtant l'arithmétique de Péano est du 1er ordre donc G étant vrai dans le modèle "standard" N, le fait qu'il n'est pas démontrable contredit le théorème de complétude ? (évidemment, il y a quelque chose qui m'échappe, mais je n'arrive pas à comprendre quoi.)

Merci pour vos éclaircissements.

Réponses

  • Foys
    Modifié (20 Mar)
    En fait dans le premier théorème de Gödel l'expression "énoncé vrai" est rhétorique.

    1°) Un terme (de l'arithmétique) est une suite de cractères obtenue par application répétée des règles suivantes:
    (i) les variables sont des termes.
    (ii) $0$ est un terme.
    (iii) pour tous termes $a,b$, $a+b$, $ab$ et $S(a)$ sont des termes.

    2°) Un terme est dit clos s'il ne contient aucune variable (seuls (ii) et (iii) sont utilisés ci-dessous dans sa formation).

    3°) Il y a un programme informatique qui à une formule $F$ fait correspondre un terme clos du langage $ \#F$ (c'est le "numéro de Gödel de $F$" dénotant un entier:par exemple si mettons $F$ est une suite de bits -in fine les formules et autres objets syntaxiques, chaînes de caractères en sont après encodage- $F$ est le nombre $\geq 1$ dont les chiffres après $1$ sont cette suite de bits).
    Disons qu'un "ensemble définissable de nombres" est un couple $(x,A)$ (qu'on notera plutôt $\{x \mid A\}$) où $x$ est une lettre et $A$ une formule. Etant donné un terme clos $t$ et un ensemble $\{y \mid B\}$, "$t \in \{y \mid B\}$" est une abréviation de l'énoncé $\exists y, y = t \wedge B$ (bref "$t$ appartient à $\{y \mid B\}$ si la propriété définie par la formule $B$ est vérifiée quand on remplace $y$ par $t$").
    Exemple: $3$ "est un nombre premier/ appartient à l'ensemble des nombres premiers" est l'énoncé $\exists p, p = 3  \wedge p > 1 \wedge \forall x \forall y, p = x y \Rightarrow x=1 \vee y = 1$.

    4°) le complémentaire d'un ensemble définissable est évidemment définissable: le complémentaire de$\{z \mid C\}$ n'est rien d'autre que $\{z \mid \neg C \}$

    5°) Il existe un programme informatique qui pour tout ensembles définissable de nombres $E$ (cf 3°)), renvoie un autre ensemble définissable de nombres $E^*$ qui est tel que pour tout autre ensemble de nombres $F$, l'énoncé suivant est un théorème:

    $(\#F) \in E^* \Leftrightarrow \left (\#(\# F \in F)\right ) \in E$.

    la construction de ce programme est assez délicate (il faut parser des expressions etc, mais on peut écrire des formules arithmétiques qui décrivent son fonctionnement; ça prend des pages et des pages dans les ouvrages spécialisés mais je pense que le laïus ci-dessus en livre l'idée intuitive).

    6°) Théorème de point fixe
    Pour tout ensemble définissable de nombres $X$, il existe une formule $F$ telle que $(\#F \in X)$ si et seulement si $F$.
    Preuve: $F$ n'est rien d'autre que $(\#X^*) \in X^*$ (cf 3° et 5° ci-dessus).

    7°) Théorème de point fixe "négatif".
    Pour tout ensemble définissable de nombres $Y$, il existe une formule $G$ telle que $(\#G \notin Y) \Leftrightarrow  G$.
    Preuve: appliquer le théorème du point fixe au complémentaire (4°)) de $Y$

    8°) Remarque: les considérations ci-dessus permettent d'établir, bien avant les théorèmes de Gödel, que la vérité n'est pas définissable en arithmétique au sens suivant: il n'existe pas (sauf si la théorie ambiante est contradictoire) d'ensemble définissable de nombres $V$ tels que pour toute formule $F$, $F \Leftrightarrow (\#F) \in V$ (appliquer le théorème de point fixe négatif à $V$). C'est-à-dire de manière imagée que l'ensemble des numéros de Gödel des formules "vraies" de l'arithmétique n'est pas définissable (c'est la première fois dans mon laïus que le mot "vrai" est employé).

    9°) Le (premier) théorème de Gödel est un peu différent: on peut définir en arithmétique un "ensemble $D$ des numéros de Gôdel des énoncés démontrables" (un preuve est une suite de bits spécifiques).
    Gödel introduit alors une formule $H$ (via à nouveau 7° ci-dessus) telle que $(\#H \notin D) \Leftrightarrow H$ ce qui dit intuitivement "$H$ équivaut à ce que son numéro n'est pas celui d'une formule prouvable".
    Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$.
  • Le modèle standard est surtout une vue de l'esprit (il est parfois introduit dans des théories plus fortes que Peano, pour faire de la théorie des modèles avec cette dernière).
    Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$.
  • Neknek
    Modifié (19 Mar)
    J'ai l'impression que tu résumes la démonstration du théorème d'incomplétude (désolé si j'ai mal compris, je ne suis pas logicien du tout) du coup je n'ai pas réussi à capturer la réponse à ma question.

    Je suis novice, une version simplifiée me serait peut-être plus accessible :#
  • @Neknek a écrit:
    mais pourtant l'arithmétique de Péano est du 1er ordre donc G étant vrai dans le modèle "standard" N, le fait qu'il n'est pas démontrable contredit le théorème de complétude ? (évidemment, il y a quelque chose qui m'échappe, mais je n'arrive pas à comprendre quoi.)


    Ce n'est pas parce que cet énoncé est vrai dans le "modèle standard" (whatever that means) qu'il est vrai dans les autres et dans le cadre du théorème de complétude, démontrable équivaut à vrai dans tous les modèles.

     
    Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$.
  • Neknek
    Modifié (20 Mar)
    Le modèle "standard" n'est-il pas inclus dans tous les modèles "non-standards" ? Donc G n'est pas vrai dans tous les modèles ? 
    Ok je pensais que la démonstration ne dépendait pas du modèle (seulement de l'existence de celui-ci).
    Le théorème de complétude n'a-t-il pas pour conséquence que toute théorie du premier ordre est complète ? 
    L'arithmétique de Péano est cohérente puisqu'elle admet un modèle ensembliste, pourquoi une théorie qui formalise l'arithmétique ne peut plus démontrer sa propre cohérence ?
    Désolé pour toutes ces questions.
  • Neknek a dit :
    Le théorème de complétude n'a-t-il pas pour conséquence que toute théorie du premier ordre est complète ?
    Non pas du tout. Prend les axiomes de la théorie des groupes, qui s'expriment au premier ordre sur le langage $(*, \cdot^{-1})$. Cette théorie est consistante puisqu'il en existe des modèles (n'importe quel groupe) mais elle n'est pas complète puisque, par exemple, la formule $\forall x, \forall y, x*y=y*x$ et sa négation ne pas démontrables à partir des axiomes de la théorie des groupes, puisqu'il en existe des modèles qui satisfont l'une ou l'autre (les groupes abéliens, et les groupes non abéliens respectivement).
    Neknek a dit :

    L'arithmétique de Péano est cohérente puisqu'elle admet un modèle ensembliste, pourquoi une théorie qui formalise l'arithmétique ne peut plus démontrer sa propre cohérence ?
    Ben... parce que Gödel l'a démontré ! Une telle théorie est suffisamment expressive pour pouvoir exprimer la démontrabilité en son sein et se retrouver dans une situation du style "paradoxe du menteur" (c'est l'idée de la démonstration de Gödel). Et l'arithmétique de Peano ne démontre justement pas sa consistance, on a besoin de plus pour montrer ça. Je ne suis pas expert, mais il existe un théorème de Gentzen qui montre quel est le "minimum syndical" pour démontrer la cohérence de Peano.

  • Ok effectivement je me suis rendu compte qu'une théorie qui formalise l'arithmétique peut contenir plus de choses que l'arithmétique ce qui peut la rendre possiblement incohérente.

    Pour la première question, je pensais que "conséquence sémantique" signifiait tout simplement "vrai dans un modèle" et pas dans "tout modèle".
  • Neknek
    Modifié (20 Mar)
    Dernière question, comment exhiber un modèle où la formule G du premier th d'incomplétude est faux ?

    Car G n'étant pas démontrable alors dans le modèle (qui contient forcément les entiers) il n'y a pas de nombre qui corresponde à une démonstration de G, cette dernière affirmation est donc vraie dans le modèle, G étant elle-même cette affirmation, G est vraie.

    Mais d'un autre côté, si G est vraie dans tout modèle alors le théorème de complétude nous dit qu'elle est démontrable ce qui n'est pas le cas.
    Deuxième argument qui va dans ce sens, si G n'est pas démontrable et si la théorie est cohérente alors en rajoutant G ou non G la théorie reste cohérente. Or si G est vraie dans tout modèle le fait de rajouter nonG rend la théorie incohérente, donc c'est pas possible non plus.

    Où est la faille ?

    (oups j'ai fait deux posts de suite, désolé)
  • @Neknek "Car G n'étant pas démontrable (...) G est vraie". Je n'ai pas compris ta démonstration de "G est vraie dans tout modèle". G est une proposition vraie dans N et non démontrable pour une certaine théorie T donc, par le théorème de complétude, il existe des modèles de T (différents de N) pour lesquels G est faux; je ne saisis pas ce qui te pose problème.
  • Neknek
    Modifié (23 Mar)
    "Proposition 20 — Si tous les axiomes de T sont vrais dans le modèle standard, alors la formule G est vraie et non démontrable dans T : N ⊧ G et T ~⊢ G."
    Démonstration. Si tous les axiomes de T sont vrais dans le modèle standard, alors tous les théorèmes (clos) de T sont également vrais dans le modèle standard (même raisonnement qu’à la Prop. 2) et la théorie T est cohérente (même raisonnement qu’à la Prop. 3). D’après la Prop. 19, la formule G n’est donc pas démontrable dans la théorie T. Par conséquent, aucun entier naturel n n’est le code d’une démonstration de la formule G dans la théorie T. 
    On a donc
    ● (n, G#) ∉ DemT pour tout n ∈ N
    ● T ⊢ ¬DemT (n, G#) pour tout n ∈ N (déf. de la formule DemT (x1, x2))
    ● N ⊧ ¬DemT (n, G#) pour tout n ∈ N (car N ⊧ T )
    ● N ⊧ ∀z ¬DemT (z, G#)
    ● N ⊧ ¬∃z DemT (z, G#)
    ● N ⊧ ¬Th(G#) (car Th(x) ≡ ∃z DemT (z, x)),
    d’où il ressort que N ⊧ G (car N ⊧ T ⊢ G ⇔ ¬Th(G#)). 
    Sachant que tout modèle des entiers, donc y compris les non-standards (à moins d'avoir mal compris), vérifie les axiomes de Péano.
    Chacun de ces modèles donc y compris les non-standards contient les entiers classiques "0, 1, 2, 3, ...".
    J'ai sans doute mal compris mais il me semble que la démonstration ci-dessus n'utilise que le codage des formules, ces codes sont des entiers classiques, pourquoi cette démonstration ne serait-elle pas valable dans un modèle non-standard ?
  • AlainLyon
    Modifié (24 Mar)
    @Neknek tu parles sans doute du deuxième théorème de Gödel : si Z est consistant alors sa preuve est indécidable dans une logique du premier ordre. Autrement dit : si Z est consisttant alors on ne peut pas le prouver avec les axiomes de Z (il faut rajouter des axiomes).
    Pour ce qui est de la construction de $\mathbb{N}$ le premier théorème de Gödel énonce qui si l'arithmétique de Peano est consistante alors il existe des énoncés indécidables dans une logique du premier ordre : par exemple certains logiciens pensent que la conjecture de Goldbach est indécidable, d'autre pensent que la preuve que le cycle 4,2, 1 est attracteur et seul attracteur de la suite de Syracuse est indécidable
    Les mathématiques ne sont pas vraies, elles sont commodes.
    Henri Poincaré
  • @AlainLyon je parle bien du premier théorème d'incomplétude, la formule G n'est pas démontrable dans la théorie T mais elle est vraie dans N (donc sa négation est fausse et donc non-démontrable dans la théorie T ce qui conclut le premier théorème).

    Seul problème pour moi, c'est que cette démonstration me semble valable dans tout modèle qui contient les entiers classiques "0, 1, 2, 3, ..." (ou 0, s(0), s(s(0)), ....) et donc aussi dans tous les modèles non-standards mais cela n'est pas possible (car ça contredirait le théorème de complétude), et j'aimerais comprendre où est la faille.
  • Alesha
    Modifié (24 Mar)
    @Neknek Tu écris "aucun entier naturel n n’est le code d’une démonstration de la formule G dans la théorie T". Comment en déduis-tu que "aucun entier non-standard n n’est le code d’une démonstration de la formule G dans la théorie T" ?
  • Neknek
    Modifié (24 Mar)
    Il me semble que le codage des formules n'est pas très compliqué et n'utilise que les entiers classiques, les éventuels entiers non-standards n'interviennent pas dans le codage, comment pourraient-ils être le code d'une démonstration de G ?
  • Alesha
    Modifié (24 Mar)
    @Neknek G est une formule non prouvable de la forme $\neg (\exists z) P(z)$. On prouve que, pour tout entier naturel $n$, on n'a pas $P(n)$. Il n'y a pas moyen d'en déduire qu'on n'a pas $P(n)$ pour un entier non-standard $n$, car la preuve de ce que la satisfaction de $P(n)$ entraîne une absurdité (à savoir que $G$ serait alors prouvable) utilise le fait que $n$ est un entier naturel. Quand on vulgarise, ça donne : si on a $P(n)$, alors $n$ est le "code d'une preuve" d'une formule non prouvable mais, en fait, quand $n$ est non-standard on ne peut pas en déduire qu'il lui correspond une preuve de $G$.
  • Effectivement je suis d'accord avec toi, le seul hic qui me reste c'est que je n'arrive pas à comprendre comment il est possible qu'un entier non standard puisse être le code d'une preuve.

    Je ne sais pas quelle est la fonction exacte utilisée pour le codage (j'essaie de la trouver) mais de ce que j'ai lu elle repose sur la décomposition en nombres premiers ou des choses similaires, donc ce que je n'arrive pas à comprendre c'est comment avec cette fonction on peut atteindre des entiers non-standards?
  • Foys
    Modifié (24 Mar)
    Quand on exécute pendant un "nombre non standard" d'étapes un programme qui génère des nombres de plus en plus grands, il est normal qu'au bout du compte il produise des nombres "non standard".
    Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$.
  • Neknek
    Modifié (25 Mar)
    Ok vu comme ça je pense comprendre.
    Par construction de la fonction : sur une démonstration en un nombre standard d'étapes la fonction renvoi un nombre standard comme code, mais avec un nombre non-standard d'étapes elle peut renvoyer un nombre non-standard comme code. Donc en gros la formule G : "il n'existe pas de nombre qui soit le code d'une démonstration de G" n'a pas de code qui soit un entier standard (c'est à dire en gros qu'il n'y a pas de démonstration en un nombre fini d'étapes) mais peut en avoir un qui soit un entier non-standard (donc une démonstration avec un nombre infini d'étapes), donc elle vraie dans un modèle standard de N quand bien-même il existerait un entier non-standard qui soit le code d'une démonstration !

    Merci pour votre aide !
Connectez-vous ou Inscrivez-vous pour répondre.