Théorèmes d'incomplétude: un préliminaire
Table des matières
Un instant …
Le 19ème siècle et le début du 20ème ont connu des bouleversements
profonds dans l'activité mathématique. Et parmi ces changements, on note la
métamorphose de la logique, devenant alors la clé de voûte dans la
construction de l'édifice mathématique.
L'une des dynamiques qui commandaient à cette évolution est le souci de la
bonne définition des objets, leurs bonnes fondations et la cohérence de
l'ensemble de l'édifice mathématique complet.
Mais l'évolution que Hilbert va entamer avec son programme changera le
paysage, le statut et le rôle de la logique. Gödel était le tournant
décisif dans cette dynamique !
… Une problématique
De manière toute « naturelle », on note deux grands principes qui
président à l'acte fondateur de Connaissance:
- Exigence de totalité et processus de synthèse: « l'unite que constitue
nécessairement l'objet net peut être autre chose que l'unité formelle de
la conscience dans la synthèse du divers de représentations » (Kant,
Critique de la raison pure).
Ce processus est celui cherche à produire de l'Ordre, à imprimer une
structure dans le Savoir.
- Coupures épistémologiques: la nouveauté est une transgression, une
brisure de symétrie dans la litanie routinière.
Ces deux principes sont complémentaires et nécessaires l'un à l'autre:
c'est en brisant l'ordre établi pour en renouveler le sens et les horizons que
le progrès dans la Connaissance s'opère.
Un enjeu: les fondements !
Les théorèmes de Gödel étaient une réponse à la problématique de la
bonne fondation des mathématiques.
Qu'entend – on par « fondements des mathématiques? »
On note trois caractérisations :
- Fondement axiomatique: produire un ensemble d'axiomes à partir desquels
on peut déduire toutes les mathématiques. L'approche de la théorie des
ensembles s'inscrit dans cette dynamique.
- Fondement conceptuel: mettre en perspective et décrire les concepts
fondamentaux des mathématiques et leurs articulations, constituant ainsi
une sorte de langage universel à partir duquel on peut penser l'ensemble
des mathématiques.
- Fondement logique:montrer que les mathématiques ne sont pas
contradictoires.
Remarque:
- Les trois types de fondements sont dynamiquement interdépendants.
- Les théorèmes de Gödel ont été une réponse au dénommé «
programme formaliste » de Hilbert. Cette caractérisation de la question
des fondements des mathématiques visait un fondement
logico-axiomatique.
- Russel et Whitehead alliaient à ceci, de manière assez explicite, une
différenciation conceptuelle via le typage et la classification des ordres
de considération. Il n'empêche que la philosophie commandant à leur
démarche est opérationnaliste et imprégné de positivisme, comme en
témoigne la postérité.
- La postérité a privilégié une dynamique triadique, où la logique a
joué pendant longtemps un rôle privilégié; aujourd'hui une démarche
diversifiée participe de cette question (cf. Jean-Yves Girard).
Et la logique dans tout ça …?
La logique, une théorie mathématique
- Elle utilise la logique comme les autres théories mathématiques.
- Elle étudie des sortes particulières d'objets mathématiques:
propositions, théorèmes, raisonnement, démonstrations, etc.
Ces deux aspects disent la métamorphose historique qui s'est opérée pour
donner la logique contemporaine: elle s'est mathématisée dans ses méthodes
et dans son objet.
les buts de la logique
- Comprendre la nature intime du raisonnement mathématique.
- Faire du « raisonnement » une théorie mathématique comme les
autres.
- donner un sens précis à ce que peut être le ''vrai'' dès qu'il s'agit
de raisonnement et d'argumentation.
- S'assurer (se convaincre ?) que les mathématiques sont exemptes de
contradictoires, de paradoxes.
- Mécaniser les processus de démonstration.
- exhiber les liens entre démonstrations et calculs.
- Formaliser les objets informatiques (c'est une orientation récente):
- Sûreté (par exemple: ligne 14 du métro) [ la question qu'on se
pose est: est – ce que le logiciel est correctement développé
vis-à-vis d'un cahier de charges ?]
- Sécurité [la question qui se pose ici: est-ce que des états
d'erreur sont accessibles ?]
Construction de la logique [1]
La logique est composée de deux parties:
- La syntaxe: cette partie porte sur la manipulation formelle des objets
manipulés
- La sémantique: cette partie s'intéresse aux valeurs de vérité des
propositions, théorèmes, ...
L'aspect formel de la logique se fonde sur des axiomes (sortes de
''vérités premières'') et des règles de déduction. Ces deux éléments
permettent de former des expressions particulières, que sont les théorèmes
et ce via la construction d'objets mathématiques particuliers, à savoir les
démonstrations (ou preuves).
Et les théorèmes alors … ? [2]
Énoncés:
- Si l'arithmétique élémentaire est w-consistante, elles comportes des
formules fermées qui ne sont démontrables ni réfutables à partir des
axiomes.
- Si l'arithmétique élémentaire est consistante, sa consistance, qui
s'exprime par une formule dans le système, ne peut être prouvée à
partir des axiomes du système.
Grandes lignes de la démonstration:
idée: projection et diagonalisation (analogue dans son principe à la
démarche cantorienne)
- 1ère étape:
Écrire formules et démonstrations arithmétiques sous forme de nombres
devenant ainsi leurs codes. On fait de même avec les nombres, comme suites
de signes, dans l'arithmétique formelle. Les propriétés
métamathématiques se transposent vers les codes numériques [3]
- 2ème étape:
On montre qu'elles sont exprimables par des formules arithmétiques et
qui sont des fonctions récursives primitives (fonctions calculables à
plusieurs variables obtenues par substitution et par récurrence à partir
des fonctions constante, identité et successeur).
- 3ème étape:
On construit une formule indécidable … on obtient ensuite le 1er
théorème.
- 4ème étape:
On exprime la consistance du système et par un procédé analogue, on
tire l'indécidabilité du 2ème théorème.
Conséquences:
Pourquoi ces théorèmes ?
Ils sont une réponse aux orientations du programme formaliste de
Hilbert:
- Possibilité d'une démonstration finitiste de la consistance de
l'arithmétique ? (i.e. Existence d'un algorithme, soit un nombre fini
d'étapes mécanisables, permettant de répondre par oui ou par non à la
question posée: l'arithmétique est – elle contradictoire ?)
Gödel démontre cette impossibilité via une démarche justement
formaliste, i.e. Il montre la non-viabilité du fondement même de la
démarche formaliste.
La conséquence a posteriori est la suivante: différenciation de
l'approche épistémologique de l'approche logique.
- Forme logique pour le principe d'indécidabilité des problèmes
mathématiques ?
Hilbert: tout problème est susceptible de recevoir une solution
définitive
→ complétude syntaxique des systèmes formels représentant les
théories mathématiques.
Gödel: le premier théorème dit l'incomplétude syntaxique des
théories classiques,de l'arithmétique, de la théorie des ensembles. Mais
le principe de solubilité des problèmes mathématiques reste valable; et
ce dans le cadre de théories plus puissantes relativement aux systèmes en
question par axiomatisation indéfinie relativement aux incomplétudes.
- Établissement finitiste de la consistance en ayant la non-absurdité:
En ajoutant la négation d'une formule indécidable au système, on
obtient la consistance, mais au même l'absurdité.
Solution: rendre sens aux signes → problématique
d'impédicativité.
- Comment définir vérité et démontrabilité ?
Vérité relève du métalangage. La définir est une question
extra-logique.
Conséquences
- Reconnaissance de l'infini en mathématique et justification
épistémologique (a posteriori)
- nécessité d'allier une réflexion philosophique sur le sujet et la
réalité des objets mathématiques.
- Limites des machines fabriquées par l'homme et indécidabilité des
systèmes formels.
Notes
- cf. le cours de logique de M. Richard Mijoule [c'est un
excellent cours, fond et forme]; tout en soulignant un aspect important
lié à la logique: c'est une démarche assez déconcertante de part
l'objet et l'approche. C'est une démarche qui a des points communs avec la
raisonnement mathématique classique, sans s'y réduire.
- Les énoncés présentés ici sont des énoncés équivalents,
tiré de l'excellent ouvrage Le théorème de Gödel (J.-Y. Girard).
- On exprime des objets portant sur le système à l'aide des
objets du système; c'est en cela qu'il y a projection.
Orientations bibliographiques:
la liste ne peut être en aucun cas exhaustive; les thèmes d'indécidabilité,
d'incomplétude et des systèmes formels sont toujours des thèmes de recherche
très active.
- [1] R. Blanché: La logique et son histoire d’Aristote à Russell.
Editions Amand Colin, collection U, Paris, 1970
- [2] R. Blanché: L’Axiomatique. Editions P.U.F., Collection
Quadrige,1999 (2ème éd.)
- [3] P. Cassou-Noguès: Gödel. Editions Les Belles Lettres, Collection
Figures du savoir, 2004
- [4] P. Cassou-Noguès, Hilbert. Editions Les Belles Lettres, Collection
Figures du savoir, 2005
- [5] A. Delessert, Gödel, une révolution en mathématiques - Essai sur
les conséquences scientifiques et philosophiques des théorèmes
gödeliens. Editions Presses Polytechniques et Universitaires Romandes,
2000
- [6] C. Raffali, K. Nour, R. David: Introduction à la logique - théorie
de la démonstration. Editions Dunod, Collection Sciences Sup, 2003
- [7] R. Cori & D. Lascar: Logique mathématique. Editions Dunod,
Collection Sciences Sup, 2003
- [8] D. Vernant: Introduction à la logique standard. Editions Flammarion,
Collection Champs-Université n° 3027, 2001
- [9] J. Lassègue: Turing. Editions Les Belles Lettres, Collection Figures
du savoir, 2003
- [10] E.Charpentier, L. Habsieger & N. Nikolski: Leçons de
mathématiques d’aujourd’hui. Editions Cassini, Collection Le Sel et Le
Fer, 2003
- [11] J. Gray, Le défi de Hilbert – un siècle de mathématiques.
Editions Dunod, Collection UniverSciences, 2003
- [12] E. Nagel, K. Gödel & J.-Y. Girard: Le théorème de Gödel.
Editions Seuil, Collection Points, 1997
Auteur : Hamza HAJJI
