Les leçons du professeur Hopper

Can't display Hopper

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

Introduction

Après avoir appris à assembler des trains, nous allons ici poser plus formellement les bases du calcul propositionnel. Cela nous permettra de comprendre quelle est exactement la portée du fameux théorème.

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):

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:

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 :

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:

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:

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.

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: 01:37, 09/02/2021