Les leçons du professeur Hopper

Le "théorème de Gödel"
Prologue: les trains

Introduction

Il n'est pas simple de comprendre véritablement ce qu'est le "théorème de Gödel", et les âneries que je lis sur ce sujet sous la plume de certains "philosophes" ou "penseurs" hérissent régulièrement mon poil de Golden Retriever, et me donnent de fortes envies de leur mordre les fesses.
On lit ainsi qu'il dit que toutes les théories sont "incomplètes". Ou qu'il démontre qu'il existe des choses "vraies" mais pas "démontrables". Mais qu'est-ce que cela veut dire, incomplet? Et de quelle "vérité" parle-t-on ?
Je vous propose un premier petit tour dans la logique mathématique, pour découvrir que derrière le théorème de Gödel se cache en fait deux théorèmes très différents, traitant de notions logiques très différentes, qui ne portent pas forcément très bien leur nom (théorèmes d'incomplétude) et qui s'appuient sur des définition très précises de ce que sont la démonstration et la "vérité", des notions qui n'ont pas forcément grand chose à voir avec le sens commun.
Et la première chose que nous allons voir, c'est que les fameux théorèmes de Gödel ne font en fait aucune référence à la notion de "vérité". En fait, le théorème de Gödel, c'est presque une histoire d'assemblage de trains...

Comment bien assembler un train

Notre aventure commence avec le chef de gare du pays de Formula. Il doit assembler des trains. Un train peu être composé de wagons (qui porte des lettres minuscule pour les reconnaître comme q par exemple) et des locomotives (qui n'ont pas de nom). Il existe aussi des wagons plateformes (sans nom) sur lesquels on peut charger des trains entiers. Les trains de leur côté sont identifiés par des lettres majuscules (comme Q) pour qu'on ne les confonde pas avec des wagons, car un wagon est un train, mais un train n'est pas toujours un wagon.

Les symboles ferroviaires

Enfin, il y a des règles très spécifiques pour former correctement les trains:

• Un wagon est un train.
• L'assemblage de deux trains au moyen d'un attelage est un train.
• Un wagon plateforme contenant un train est un train.
• Si on met une locomotive derrière un train, le résultat est aussi un train.

Il faut bien noter que le mot "train" (ainsi que le symbole associé dans les schémas) ne sont jamais que des "raccourcis" pour désigner un assemblage correct de wagons, d'attelages et de locomotives.

Les 4 façons de former correctement des trains.
De haut en bas et de gauche à droite: (a) un wagon, (b) deux trains attelés, (c) un train sur un wagon plateforme et (d) une locomotive derrière un train.

Il faut aussi noter que les wagons plateformes ne sont que des "utilitaires de stockage" et un train T sur un wagon plateforme est équivalent au même train sans wagon plateforme. Les wagons plateformes ne sont utilisés que pour lever des ambiguïtés d'assemblage.

Un train T sur un wagon plateforme est équivalent au même train T s'il est seul
Les wagons plateformes ne sont que des facilités d'assemblage.

Pour se simplifier la vie (mais cela a peu d'importance pour l'instant), notre chef de gare invente une notation pour représenter ses trains: un wagon est représenté par sa lettre, une locomotive par le symbole ¬, un attelage par le symbole →, et un wagon plateforme par les symboles ( et ) à l'intérieur desquels on place le train qu'il transporte.

Voici quelques exemples de trains bien formés, avec leur notation:

Le train ¬p→q

Le train ¬(p→q)

Le poste de douane

Les assemblages

Pour passer dans le pays voisin, l'état de Théoréma, les trains doivent respecter des règles supplémentaires au niveau de leur assemblage. Notre chef de gare sait que les douaniers ne laisseront passer son train que s'il est d'une des formes suivantes:

Assemblage 1: P→(Q→P)

Assemblage 2: (P→(Q→R))→((P→Q)→(P→R))

Assemblage 3: (¬P→¬Q)→(Q→P)

Premiers exemples

On peut donc construire des trains complexes et les envoyer de Formula à Théoréma, puisque les trains P, Q et R des règles ci-dessus peuvent être remplacés par n'importe quel train bien formé de Formula. On appellera d'ailleurs ces trains des trains Théoréma. Par exemple, les trains suivants sont des trains Théoréma et pourront franchir la frontière:

Train Théoréma 1: ¬p→(p→¬p)
A partir de l'Assemblage 1 en remplaçant P par ¬p et Q par p

Train Théoréma 2: p→((p→p)→p)
A partir de l'Assemblage 1 en remplaçant P par p et Q par p→p

Train Théoréma 3: (p→((p→p)→p))→((p→(p→p))→(p→p))
A partir de l'Assemblage 2 en remplaçant P par p, Q par p→p et R par p

La Règle d'Indulgence

Ceci dit, la mécanique des assemblages est relativement restrictive, et peu de trains pourraient passer. Pour améliorer un peu les choses, les douaniers de Théoréma ont décidés d'être indulgents, et ils ont donc édictés la règle suivante, aussi connue sous le nom de RI (Règle d'Indulgence):

La Règle d'Indulgence (RI)
Si P est un train Théoréma et P→Q est aussi un train Théoréma alors Q est un train Théoréma

Cette règle dit globalement que si le train de gauche d'un attelage est un train Théoréma et que le train complet est un train Théoréma, alors le train de droite de l'attelage est aussi un train Théoréma.

Un exemple pratique

Tout cela est bien clair sur le plan des règles à respecter, mais l'application pratique n'est pas élémentaire. Notre chef de gare se demande par exemple si le train suivant, au demeurant très simple, pourra franchir la frontière:

Le train p→p est il un train Théoréma ?

Répondre à la question n'est pas simple. Mais notre chef de gare se souvient des exemples précédents qui nous indiquent que les trains suivants sont des trains Théoréma:

Train Théoréma 2: p→((p→p)→p)
A partir de l'Assemblage 1 en remplaçant P par p et Q par p→p

Train Théoréma 3: (p→((p→p)→p))→((p→(p→p))→(p→p))
A partir de l'Assemblage 2 en remplaçant P par p, Q par p→p et R par p

Et d'un coup d'oeil on voit que la partie de gauche du train Théoréma 3 est exactement le train Théoréma 2 (rappelons-nous que les wagons plateformes ne sont que des facilités d'assemblage). En appliquant la règle d'indulgence, nous savons donc que la partie de droite du train Théoréma 3 est aussi un train Théoréma:

Train Théoréma 4: (p→(p→p))→(p→p)
Par application de RI sur les trains Théoréma 2 et 3

Remarquons maintenant que le train suivant est aussi un train Théoréma:

Train Théoréma 5: p→(p→p)
A partir de la règle d'Assemblage 1, en substituant p à P et p à Q

Or le train Théoréma 5 est aussi exactement le train à gauche de l'attelage du train Théoréma 4. Donc en appliquant à nouveau la RI sur ces deux trains, on en déduit que le train à droite de l'attelage est aussi un train Théoréma et donc le train suivant est bien un train Théoréma:

Le train p→p est bien un train Théoréma par application de la RI sur les trains Théoréma 5 et 4

On reconnaîtra qu'il n'est pas trivial de répondre à la question d'origine, ce qui suscite chez notre chef de gare de multiples interrogations.

Les interrogations du chef de gare

• Décidabilité: Serait-il possible, par une procédure algorithmique (donc en suivant des règles totalement déterministes à chaque étape), de savoir si un train T quelconque va pouvoir franchir la frontière?
• Complétude: pour un train T quelconque, peut-on être sûr que T franchira la frontière ou que sinon il suffit de rajouter une locomotive à T pour qu'il puisse passer la frontière? Globalement la question est de savoir si pour T quelconque, on a toujours que T est un train Théoréma ou (¬T) est un train Théoréma.
• Consistance: en complément de la question précédente, peut-on être sûr qu'il n'y a pas de train T tels que T et (¬T) soient tous les deux des trains Théoréma?

Arrivé à ce stade, notre chef de gare a compris, sans le savoir, quelques unes des questions fondamentales de la logique mathématique, et il maitrise tous les rudiments du calcul propositionnel...

En ce qui concerne nos trois question, et dans le cas présent, la réponse est oui pour la décidabilité, ce qui est rassurant pour notre chef de gare: il est possible de vérifier simplement si un train passera la douane avant de l'envoyer aux douaniers. C'est en revanche non pour la complétude, ce qui est plus ennuyeux en ce qui le concerne: il ne suffira pas de rajouter une locomotive a un train non conforme pour lui faire passer la douane...

Le but de ce prologue est de faire comprendre une chose simple: la partie syntaxique de la logique mathématique, celle sur laquelle porte les théorèmes de Gödel à proprement parler, se ramène à de la manipulation de symboles, sans aucune signification a priori. Un train n'est pas "vrai" s'il peut passer la frontière, et "faux" sinon. Il est juste conforme ou non-conforme à des règles de construction, et rien d'autre.

Vous pouvez maintenant passer à la partie I de cette leçon.

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