Ok

En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies. Ces derniers assurent le bon fonctionnement de nos services. En savoir plus.

18/08/2017

La Complétude

Bon, tout se mélange. Aussi il nous faut parler de la complétude, aussi affirmée par Gödel. Le brigand semble se contredire, mais il ne parlait pas de la même chose. 

D'abord c'est la THESE de Gödel de 1929(il commençait bien).  

Mais d'abord, on définit la "cohérence" comme la "consistance" (ce sont une et une seule chose) comme la capacité d'un système de ne pas produire de contradictions. Encore faut il être capable de produire quelque chose, c'est à dire être un système... On dit aussi qu'il est "non contradictoire", ce qui est logique finalement.

Un point intéressant: une théorie est cohérente si elle a des énoncés non démontrables... Par exemple, la contradiction, doit pouvoir être exprimée dans la théorie, mais il vaut mieux qu'elle ne soit pas démontrable. Il doit y avoir du faux dans une théorie, sinon elle est "triviale" et donc n'a aucun intérêt. 

On en vient alors à la différence syntaxe/sémantique c'est à dire à la notion de "modèle". Un modèle est une structure descriptible -par ailleurs- qui vérifie les axiomes de la théorie. Une interprétation, quoi. Le mot "sémantique", sensé donner du sens, caractérise ainsi ce qui est "commun" à des objets différents et qui va au delà du simple respect potentiel de certaines règles: en plus c'est possible, car CA existe... Du moins dans une acception "réaliste" du mot "sens".

On dit qu'il y a cohérence "au sens sémantique" si il y a un modèle pour la théorie. 

La logique "du premier ordre", décrite par Frege, est la logique des prédicats avec les quantificateurs. Elle permet de décrire l'arithmétique, par exemple. 

Le théorème de complétude, le truc de Gödel, dit que SI un théorème est vrai dans TOUS les modèles, alors, on peut le démontrer en appliquant les règles du système. Vrai implique démontrable. Il le prouve pour la logique du premier ordre.

Arithmétiques

A ce stade, on doit réaliser ce qu'est la logique du premier ordre. On a du ou, du et, du non, A, E et des variables en nombre indéfini.

On y peut définir l'arithmétique en choisissant des symboles primitifs et des règles de succession. L'arithmétique, c'est celle de Peano, définit l'addition mais aussi la multiplication. Elle est du "premier" ordre, car elle exclut les quantifications sur les ensembles de nombres.

Il y a aussi l'arithmétique de Robinson (Raphael, pas Julie), moins puissante que Peano, car "finiment" axiomatisable, mais suffisante pour être incomplète gödéliennement. Elle a la multiplication, définie pourtant en fonction de l'addition, de manière évidente, quoique récursivement:  x*0 = 0 et  x * s(y) = x*y + y.

Ainsi donc, c'est ce schéma récursif là qui "porte" la capacité à faire le monstre (le monstre de Gödel).

Au passage, l'arithmétique sans multiplication, celle de Presburger (quel nom, il a pour prénom Mojżesz ) est super simple, "complète" et "décidable". Il faudrait en reparler. 

Pour en revenir à Péano, il a -en plus- une infinité d'axiomes qui sont toutes les formes possibles du raisonnement par récurrence, énumérées bestialement car il est impossible (si on veut rester au premier ordre) d'abstraire sur toutes les formules... Péano est ainsi "infiniment" axiomatisé. 

Par contre, toutes ces arithmétiques sont compatibles avec la complétude Gödelienne: il y a bien une démonstration pour tout énoncé vrai dans tous les modèles, PARCEQUE elles sont du premier ordre.

La complétude est donc celle du système de déduction appliqué au système, ou plus exactement celle du système axiomatisé à qui l'on applique la déduction "naturelle", c'est à dire LE raisonnement tout court. Il faut bien comprendre ce qu'est ce fameux "raisonnement": il n'a pas lui, d'"axiomes" à proprement parler, sinon la seule déduction possible à partir de rien, que l'on appelle "axiome", d'ailleurs

__________ ax

    X,A |- A

Les autres règles, reformulations du raisonnement dit "axiomatique", ne sont que des ré-expressions commodes de ce qu'on appelle la déduction dite "naturelle". Tout ça fut réglé par GG (Gentzen), voir mon exposé sur Girard 

http://francoiscarmignola.hautetfort.com/archive/2015/09/12/girard-jean-yves-5684115.html

 Cette histoire DU "raisonnement" est ce qui obsède Girard... 

Une "logique" (il y en a plusieurs) est une forme de ce fameux raisonnement. Allez on crache le morceau, chacune de ces logiques est donnée par des conventions (les symboles variés) et surtout des règles de raisonnement (exprimables avec des séquents et la fichue barre horizontale). On a L K (la logique klassike), L J (la logique intuitionniste) et L L (la logique linéaire). 

Toutes se définissent avec leurs règles spécifiques, exprimées par des déductions (la fameuse barre horizontale) reliant des séquents d'entrée à des séquents de sorties. Une démonstration dans la logique en question est une suite d'application de ces règles, de fait un arbre dont la racine, loin en bas est ce qu'on est arrivé à démontrer... 

Les séquents

Un point au sujet des séquents, qui restent LA manière d'exprimer des raisonnements généraux, bien que les graphes de Girard (il faudra en reparler) soient bien tentants.

Ils ont eux mêmes une partie droite et une partie gauche, séparées par "|-" le "donc" du raisonnement élementaire, en fait la classique implication, qui se contente de séparer une suite de "et" et une suite de "ou". 

De fait l'assertion élémentaire, le séquent est capable d'exprimer n'importe quoi... Depuis le faux : ( A |- ), et le vrai: (|- A) en passant par tout le reste.

Les séquents sont utilisés pour exprimer une règle particulière, la règle de coupure (cut). Gentzer a démontré lui même, ce fut sa "hauptsatz" qu'elle est redondante, et qu'on peut exprimer tout raisonnement sans elle. Les coupures peuvent toujours être éliminées. Voyons voir le séquent des coupures: 

X |- A, Y       X,A |- Z

__________________ cut

         X |- Z 

A est "coupé" (éliminé). La seule règle qui élimine une hypothèse, c'est celle là. Elle est donc, en principe, une menace: si on arrive à prouver le séquent vide |-, on serait foutu. Or, il se trouve que la contradiction mène au séquent vide. 

La règle de négation (à droite) bien connue, donne: 

|-  nA

_______

nnA |-

Et on combinant, avec la règle de coupure, on a donc au total:

|- nnA         |- nA

               ________

                 nnA|- 

_______________

       |-

C'est à dire, précisément que (nnA et nA), expression de toutes les contradictions, mène au séquent vide.  Par contraposée, s'il n'y a pas de séquent vide, il n'y aura pas de contradiction. COMME il n'est pas possible de générer de séquent vide, la logique n'est pas contradictoire.

Rassurant,non ? Et bien il a fallut un nazi pour nous le prouver. 

 

Les modèles

Naturellement, l'expression "vraie dans TOUS les modèles" a un caractère intrigant: qu'est ce que cette vérité là? De fait, il s'agit de la vérité "combinatoire", celle qui, pour le calcul des propositions, s'exprime avec les tables de vérité. On a donc les distinctions entre toujours faux, parfois faux, (et donc parfois vrai), et toujours vrai (valide).

Le mot valide est un peu faible, le "toujours vrai" ou "absolument vrai" est qualifié de "universellement valide". Alors que l'invalide lui est plus simplement "absolument faux".

En gros une proposition porte sur des variables, et un modèle, forcément dénombrable, est une liste de variables, la validité d'une proposition étant vérifiée par la constatation qu'elle est déclarée vraie dans TOUS les modèles... Pour qu'une telle absurdité soit possible, il faut donc que la proposition soit non atomique ou bien un "axiome", évidemment démontrable. P(x) vrai toujours, avec P un symbole, par exemple. 

Une proposition "validable" est donc composite, et utilise les structures du premier ordre pour se formuler.

La "conséquence logique", au sens des modèles, notée "|=", est donc une relation entre deux assertions de validité, qui se "calcule" de manière basique. 

C'est Paul Bernays, qui démontra en 1926 que pour les proposititions, la démontrabilité découle de la validité.  

 Notons que, on aurait pu commencer par là, que la réciproque est vraie: une démonstration (au sens de Gentzen), (notée "|- ") implique que tout modèle de l'hypothèse est aussi modèle de la conclusion. La chose parait assez naturelle, la déduction dit "naturelle" étant bien compatible avec l'attribution de la vérité dans les opérateurs logiques élémentaires.  C'est le théorème de "correction", de "korrektheit", de "soundness", qui s'applique à une logique, ou à un "système logique". Par exemple, la logique intuitionniste est "correcte".

Incomplétudes

Il faut maintenant évoquer LES théorèmes d'incomplétude... Car en plus, il y en a DEUX...Le truc est multiple. 

Mais surtout le sens (du mot "complet") est DIFFERENT.

D'abord, le premier d'entre eux, qui est le plus fameux dit que toute théorie consistante incluant l'arithmétique, cela inclut le calcul des prédicats, est "incomplète": il y existe des énoncés indécidables. Non pas faux, ça on le savait (voir plus haut), mais non susceptibles d'être démontré avec les axiomes de la théorie, c'est à dire qu'il n'en existe pas de démonstration avec cette théorie là. 

Notons que le théorème de complétude s'applique et n'a en fait rien à voir avec cette choucroute, le mot est juste traitre. Car l'énoncé "indécidable" dont on parle (non démontrable, donc) n'est pas "vrai" dans un modèle particulier (ce qui contredirait la complétude gödélienne). Par contre, ce modèle violateur, qui donc existe forcément, est "non standard" car le code de Gödel (attention, on s'accroche aux branches) de l'assertion "la théorie n'est pas consistante". Les modèles non-standards de l'arithmétique sont  ainsi en fait inévitables...  

L'incomplétude gödélienne est donc distincte de la complétude du même (auteur), en ce qu'elle ne s'applique pas à la même notion à compléter.

C'était ce que je voulais dire.

Allons directement au "monstre" de Gödel, qui utilise l'expressivité de l'arithmétique pour encoder l'assertion qu'il n'est pas prouvable. Cette assertion ne trouve indécidable par définition: si elle est prouvable, c'est qu'elle est vraie et donc elle se contredit; elle est donc non prouvable et se trouve réfutée, c'est à dire par définition prouvée, compte tenu de ce qu'elle affirme. Le monstre est donc bien indécidable et Gödel a raison de dire ce qu'il dit.

Le deuxième théorème de Gödel se déduit (presque) immédiatement du premier: les théories plus puissantes ou égales que l'arithmétique sont trop expressives: elle ne peuvent prouver leur propre cohérence car l'expression de leur cohérence s'y trouve indémontrable. En fait, si cette démonstration était possible, ALORS, la théorie serait contradictoire... Là le monstre se trouve fixé: il est précisément l'affirmation de la cohérence de la théorie, s'encode dans des considérations compliquées mais se trouve (donc,ainsi) indémontrable. Encore un sens nouveau pour le mot "incomplet". On y va: l'encodage de la preuve de l'assertion "la théorie n'est pas consistante" si elle est possible, 

Diophante et l'ordinateur

En parlant de complétude, l'équivalence faite par Matiassevitch entre les équations diophantiennes (sur les polynômes à coefficients entiers) et les ensembles récursivement énumérables montre que ces équations là ne peuvent être décidées solvables en général, et donc que le dixième problème de Hilbert est résolu, négativement. 

On fera remarquer que Matiassevitch, né en 1947 comme Girard, trouva cela en 1970, et que c'est à Paris que Hilbert (David) formula son programme. Que toute l'informatique, c'est à dire le calcul chosifié qui occupe tellement les esprits soit équivalent aux équations diophantiennes restera toujours fascinant (au moins pour moi).

Le XXème siècle fut un siècle complet (elle est bien bonne celle là).

 

P.S. J'ai passé beaucoup de temps à bien séparer les deux sens du mot "complétude". Ce n'est que dans la version anglaise de l'article wikipedia qu'on parle d'appliquer le théorème de complétude à l'assertion indécidable issue du deuxième théorème d'incomplétude... De plus, la "omega" inconsistence dont Rosser peut se passer pour démontrer le théorème d'incomplétude d'une autre manière n'a rien à voir avec la choucroute, contrairement à ce que semble laisser sous entendre Girard... Il y a donc toujours un doute, mon sentiment est mitigé, incomplet en quelque sorte...

 

La syntaxe et la sémantique

Object des fantasmes de Girard, l'abolition de la distinction sémantique/syntaxe est bien mystérieuse et constitue un horizon sur lequel je me fracasse. 

Disons que c'est le coeur du propos de ce papier: le modèle est la sémantique, et le raisonnement la syntaxe (à moins que ce ne soit l'inverse). L'un est le réel de l'autre et c'est ce que veut dire Girard, qui veut abolir le réel, c'est à dire l'essence des choses. 

Dans sa fabuleuse "nécrologie" Nécrologie http://iml.univ-mrs.fr/~girard/titres.pdf il met en avant la chose, et prétend l'avoir résolue (ou pas).

Philosophie des mathématiques

Plus que jamais, la question de la nature du monde est posée et il semble bien que ces apories du raisonnement lui même en question agissent en faveur de deux points de vues à la fois opposés et adversaires des relativistes et autres conventionnalistes et donc des scientistes (et oui) qui veulent "écraser" la notation et faire du monde une simple mécanique.

Ces deux points de vue sont bien le platonisme mathématique, et oui, c'était ce que pensait Gödel lui même, et ce que pensent les mathématiciens en général: un monde de réalité abstraite contraint la raison et se trouve à explorer, le faillibilisme, contrairement à ce que pense Girard étant le critère. Le monde mathématique EST naturel, et se trouve peuplé de monstres à découvrir. C'était ce que pensait Bach pour la musique, du moins j'en suis sur. 

L'autre point de vue est similaire, mais aussi radicalement opposé: un intuitionnisme forcené, qui ramène tout à la seule chose qui compte, l'ensemble des entiers naturels, seule chose crée par Dieu, totalement donné, totalement naturel (comme son nom l'indique) et qui contient tout... 

Écrire un commentaire