Les leçons du professeur Hopper

Le théorème de Gödel
Partie I: notions fondamentales

Introduction

Le calcul propositionnel

Le calcul propositionnel est la partie la plus simple de la logique mathématique. Il s'agit donc d'un outil particulièrement utile comme introduction à ses propriétés.
Il a aussi une grande importance pratique, puisqu'il recouvre par exemple la construction de circuits électroniques logiques, mais aussi la résolution de problèmes de satisfactions de contraintes qui peuvent être très compliqués, dans le cadre de ce qu'on appelle les solveurs SAT).

Parlons d'abord des formules qui composent notre langage. En logique propositionnelle, nous travaillons avec des objets appelés atomes et notés a, b, c etc et avec deux opérateurs: ¬ et →

Ces objets peuvent être combinés en utilisant les règles suivantes pour créer des formules bien formées (en anglais well-formed formula, ou wff, une expression que l'on rencontre régulièrement):

• Un atome est une formule
• Si F est une formule ¬F est une formule
• Si F et G sont des formules F→G est une formule

Par exemple: a est une formule bien formée; a→b également ainsi que; ¬a→¬b ou ¬a→(a→b), etc...

A partir d'ici j'emploierai l'expression formule comme synonyme de formule bien formée. C'est techniquement incorrect. Une formule quelconque peut par exemple être →→pq, mais comme seules les formules bien formées nous intéressent, nous ferons un léger raccourci.

La démonstration

Nous en arrivons directement à la notion de démonstration: on appelle les formules démontrables des théorèmes et on va tout de suite voir comment les reconnaître. Cela se fait à partir de deux éléments:

• Tout d'abord les axiomes, qui sont ce qui est admis comme base de la théorie. Les axiomes du calcul propositionnel sont:
  1. P→(Q→P)
  2. (P→(Q→R))→((P→Q)→(P→R))
  3. (¬P→¬Q)→(Q→P)
  Ici P, Q et R représentent n'importe quelle formule telles que définies au dessus. Donc a→(b→a) est un théorème d'après (1), mais (a→b) → (c→(a→b)) est aussi un théorème en substituant dans (1) P par a→b et Q par c. Les axiomes permettent donc déjà de générer une infinité de théorèmes par simple substitution. Il faut donc noter que les axiomes du calcul propositionnel ne sont pas en eux-mêmes des théorèmes, car ce ne sont pas des formules, puisque P, Q, et R ne sont pas des atomes mais des objets auxquels on peut substituer n'importe quelle formule.
• Il existe enfin une règle, dite règle d'inférence, qui dit la chose suivante (ici aussi P et Q sont des formules quelconques):
  • Si P→Q est un théorème et si P est un théorème, alors Q est un théorème
  Donc par exemple ici, d'après l'axiome 2, (p→(q→p))→((p→q)→(p→p)) est un théorème en substituant p à P, q à Q et p à R. D'autre part, d'après l'axiome 1, p→(q→p) est un théorème. Donc à partir de ces deux théorèmes et de la règle d'inférence, on en déduit que (p→q)→(p→p) est un théorème.

Nous allons maintenant traiter un exemple et vérifier que p→p est un théorème, et nous allons également constater que la démonstration de quelque chose d'aussi simple n'est pas trivial:

1. Tout d'abord, remplaçons dans l'axiome 1 P par p et Q par p→p. Nous obtenons comme théorème 1: p→((p→p)→p)
2. Maintenant remplaçons dans l'axiome 2 P par p, Q par p→p et R par p. Nous obtenons comme théorème 2: (p→((p→p)→p))→((p→(p→p))→(p→p))
3. Appliquons la règle d'inférence sur les théorèmes 1 et 2 que nous venons de démontrer. Nous en déduisons le théorème 3: (p→(p→p))→(p→p)
4. En remplaçant dans l'axiome 1 P par p et Q par p, nous obtenons le théorème 4: p→(p→p)
5. En appliquant la règle d'inférence entre les théorèmes 4 et 3, nous obtenons le théorème 5: p→p

Nous avons fini la route de la démonstration. Une formule est démontrable si c'est un théorème et les théorèmes se construisent mécaniquement à partir des axiomes et règles ci-dessus. Simple, n'est-ce pas? Notons que jusqu'ici n'interviennent que des notions mécaniques de substitution et de simplification, que nous n'avons jamais parlé de vérité ou de fausseté et que les symboles ¬ et → peuvent bien être n'importe quoi, nous ne leur avons donné aucun sens. La démonstration est une opération purement mécanique qui permet de construire un sous-ensemble (les théorèmes) à l'intérieur du grand ensemble des formules bien formées (qui est lui-même un sous-ensemble du très grand ensemble de toutes les formules possibles).

Définitions fondamentales

Maintenant que nous maîtrisons les notions de théorème et de démonstration, nous pouvons introduire certaines définitions fondamentales. Pour un système logique donné, on dit qu'une formule est :

• Indépendante: une formule F est dite indépendante si F n'est pas un théorème et ¬F n'est pas non plus un théorème. Une formule indépendante peut être rajouté aux axiomes d'une théorie sans en modifier les propriétés.
• Décidable: une formule F est dite décidable si il existe un algorithme permettant de décider en un temps fini si F est un théorème.

Informellement un algorithme est la description d'une procédure "mécanique" permettant de réaliser un processus en suivant un ensemble de règles strictement déterministes.

Pour le système logique dans son ensemble on dit qu'il est:

• Cohérent (ou Consistant): il est impossible de trouver une formule F telle que (F est un théorème) et que (¬F est un théorème)
• Décidable: il existe un algorithme permettant de décider en un temps fini si une formule est un théorème (autrement dit, toutes les formules sont décidables)
• Complet ou syntaxiquement complet ou complet relativement à la négation: pour toute formule F, F est un théorème ou ¬F est un théorème (il n'y a pas de formule indépendante)

En ce qui concerne notre exemple (le calcul propositionnel) il possède les propriétés de consistance et de décidabilité (nous verrons bientôt que ces propriétés sont relativement simples à établir pour le calcul propositionnel), mais pas celle de complétude syntaxique. Il suffit pour se persuader de ce dernier point de considérer p. p est une formule bien formée, mais ce n'est pas un théorème, et ¬p n'est pas non plus un théorème.

La complétude est une propriété incroyablement forte, et il ne faut guère s'étonner de l'incomplétude d'un système. En effet, les règles de construction des théorèmes semblent bien plus restrictives que les règles de construction des formules, et il serait plutôt surprenant que toute formule F soit un théorème ou que ¬F soit un théorème. Intuitivement, il semble bien qu'il y ait "beaucoup plus" de formules que de théorèmes.

Mais même la consistance est une propriété très forte si on y réfléchit. Rien a ne semble garantir qu'on ne puisse pas avoir une formule F telle que F et ¬F soient des théorèmes. Après tout rien dans notre système de construction ne semble a priori fait pour l'éviter.

Quant à la décidabilité, il s'agit aussi d'un propriété très forte. Nous avons déjà vu que démontrer des théorèmes simples n'est justement pas simple. Il est donc presque miraculeux qu'il puisse exister un algorithme permettant de décider de façon totalement déterministe si une formule est un théorème. Notons que l'algorithme ne dit pas nécessairement comment (c'est à dire par quel enchaînement de règles) la formule a été construite mais seulement si elle a été construite suivant ces règles.

Pour en revenir informellement à Gödel

Nous sommes maintenant suffisamment "armés" pour revenir au second problème de Hilbert, et aux deux théorèmes d'incomplétude de Gödel, et pour en parler un peu plus correctement.

Le second problème de Hilbert consistait à démontrer de façon finitiste que l'arithmétique classique était consistante, c'est à dire que l'on ne pouvait pas avoir une formule F de l'arithmétique telle que F soit un théorème et que ¬F soit également un théorème. En effet, l'arithmétique "classique" est un système logique qui possède une axiomatique (au demeurant pas beaucoup plus compliqué que celle du calcul propositionnel si on s'en tient au nombre d'axiomes), et on peut donc en étudier les propriétés exactement comme pour le calcul propositionnel.
La notion de démonstration finitiste est intuitivement compréhensible: il s'agit de démonstrations dans lesquelles on peut parler d'ensembles infinis, mais pas de propriétés qui s'appliqueraient à tous les éléments de ces ensembles. La définition généralement rencontrée est que l'on s'interdit de penser l'infini comme un objet mathématique réel. Notons tout de suite le caractère très restrictif de cette contrainte...

En cherchant à résoudre ce problème, Gödel a montré trois choses:

• l'arithmétique n'est pas syntaxiquement complète, c'est à dire qu'il existe des formules arithmétiques F telles F n'est pas un théorème et ¬F non plus. C'est à proprement parler un théorème d'incomplétude. Notons que cela n'a intuitivement rien d'exceptionnel. Il y a "beaucoup" de formules bien formées, et même intuitivement il semble qu'il y en ait beaucoup plus que de théorèmes, qui sont eux générés par des règles strictes. Donc rien ne dit intuitivement qu'une formule ou sa négation doit nécessairement être un théorème.
• l'arithmétique est indécidable: il n'y a pas d'algorithme permettant de déterminer de façon mécanique qu'une formule arithmétique est ou n'est pas un théorème. Là encore, ce n'est pas intuitivement choquant, bien au contraire. Ce serait certes formidable d'avoir un algorithme capable de démontrer automatiquement n'importe quel théorème arithmétique, mais admettons que ce serait presque trop beau pour être vrai.
• on peut exprimer la propriété que l'arithmétique est consistante en utilisant le langage de l'arithmétique elle-même; c'est une propriété très forte, et qui montre que l'arithmétique "classique" est un langage déjà très expressif malgré le petit nombre de principes fondamentaux qui la définissent. C'est véritablement le résultat le plus spectaculaire dans la démonstration de Gödel, et c'est la pierre angulaire de cette démonstration. Malheureusement, c'est aussi le résultat dont on parle le moins...
• on ne peut pas montrer directement en utilisant des méthodes finitistes dans le langage de l'arithmétique que l'arithmétique est consistante. C'est ce que l'on appelle souvent le "deuxième théorème d'incomplétude". Le terme d'incomplétude est ici, à mon sens, très mal choisi. Cela n'a rien à voir avec l'incomplétude au sens logique du terme, il s'agit simplement de dire que l'on ne peut pas démontrer la consistance dans les conditions posées par Hilbert. En fait, si l'on y réfléchit bien, ce résultat n'est pas en soi si étonnant que cela. Les contraintes sont extrêmement fortes, et il suffit d'ailleurs d'en lever une pour pouvoir démontrer la consistance. Par exemple, la consistance de l'arithmétique est démontrable si on admet la consistance de la théorie des ensemble. De la même façon, elle est démontrable en admettant un petite entorse à la notion de finitiste (c'est la démonstration de Gentzen qui fait appel à l'induction transfinie jusqu'à ε₀).

Ces théorèmes ne font aucune référence à la notion de "Vérité"; ce sont des résultats strictement syntaxiques, et ils ne montrent donc pas directement (contrairement à ce qu'on lit trop souvent) qu'il existe des propositions "vraies" qui ne sont pas démontrables, d'autant que la notion de "vérité" en logique nécessite une définition rigoureuse que nous verrons dans une leçon ultérieure, et qui n'est pas très proche du sens commun...

Méfions-nous également de l'idée trop répandue que le théorème de Gödel s'applique "partout". Considérons la proposition suivante: parmi 7 nombres réels différents, on peut trouver x et y tels que (x-y) divisé par (1+xy) est plus grand que 0 et plus petit que la racine carrée de 3. Il s'agit d'un problème complexe faisant appel à des notions mathématiques non élémentaires, et pourtant elle s'exprime dans un système (les corps réels clos) pour lequel le théorème de Gödel ne s'applique pas. Ainsi cette proposition est parfaitement décidable (il existe un algorithme permettant de savoir si cette proposition est un théorème), et, de plus, le système des corps réels clos est consistant et syntaxiquement complet.
Plus fort encore, Alfred Tarski a construit une axiomatisation de la géométrie euclidienne élémentaire qui la rend equivalente à la théorie des corps complets clos, ce qui fait que la géométrie euclidienne élémentaire est elle aussi consistante, décidable et syntaxiquement complète.

La différence entre un système "mathématico-logique" où le théorème de Gödel s'applique et un où il ne s'applique pas est un problème technique complexe qui ne repose en rien sur l'intuition. Autant dire qu'il ne faut jamais appliquer le théorème de Gödel hors de son cadre mathématique strict et en particulier surtout pas dans des élucubrations philosophico-fumeuses.

Caveat

J'ai employé dans ce petit texte certains termes sans les définir tout à fait précisément, comme algorithme, ou arithmétique classique. De la même façon, j'ai fait quelques confusions entre axiomes et schémas d'axiomes. Ce sera le sujet de leçons ultérieures...

Retour à ma page principale

Le téléchargement ou la reproduction des documents et photographies présents sur ce site sont autorisés à condition que leur origine soit explicitement mentionnée et que leur utilisation se limite à des fins non commerciales, notamment de recherche, d'éducation et d'enseignement.
Tous droits réservés.

Dernière modification: 17:44, 21/02/2024