Les théorèmes limitatifs en logique et leurs implications philosophiques
Dans ce cours nous étudions les théorèmes limitatifs prouvés par Gödel, Tarski, Church, Turing, Löwenheim and Skolem dans la première moitié du 20ème siècle. Il s'agit des cinq fameux résultats suivants:
1) Chaque système formel d'une certaine expressivité est nécessairement incomplet. (Gödel)
2) Chaque système formel d'une certaine expressivité est incapable de prouver sa propre cohérence. (Gödel)
3) Chaque système formel d'une certaine expressivité ne peut pas contenir son propre prédicat de vérité. (Tarski)
4) Il n'y a aucun algorithme général qui peut calculer si une procédure donnée va arrêter pour une entrée donnée, et il n'y a aucun algorithme qui peut calculer la validité d'une formule de la logique prédicative. (Church et Turing)
5) Toute théorie formulée dans la logique prédicative qui a un modèle infini, a un modèle de cardinalité arbitraire. (Löwenheim et Skolem)
Tous ces résultats ont eu un effet d'humilité sur les fondements des théories mathématiques et scientifiques. Ils ont détruit l'espoir que nous serions en mesure de réduire les théories complexes à leurs axiomatisations logiques qui décident, une fois et pour toujours, la vérité de chaque phrase. L'influence de ces théorèmes sur l'épistémologie, les mathématiques, l'informatique et ses philosophies est énorme. Malheureusement, tous ces résultats ont également été abusés en mal interprétant les théorèmes formels.
Nous étudions quelques préliminaires essentielles pour être capable de comprendre les cinq théorèmes (logique prédicative, fonctions récursives, machines de Turing, l'arithmétique de Peano et Robinson). Nous analysons la signification précise des cinq théorèmes. Pour les quatre premiers théorèmes, nous donnons un résumé clair de leurs preuves ingénieuses. Enfin, nous discutons les implications philosophiques des théorèmes sur la base des textes sélectionnes de [1] et [4] de la bibliographie.
Bibliographie
1. Torkel Franzén, Gödel's Theorem: An Incomplete Guide to its Use and Abuse, A K Peters 2005.
2. Kurt Gödel: Collected Works, Volume I: Publications 1929-1936, Oxford University Press, New York, Oxford 1986; Volume III, Oxford University Press, 1995.
3. Douglas R. Hofstadter, Gödel, Escher, Bach, an Eternal Golden Braid, Basic Books, NY 1979.
4. Jean Ladrière. Les limitations internes des formalismes. Étude sur la signification du théorème de Gödel et des théorèmes apparentés dans la théorie des fondements des mathématiques, ed.Nauwelaerts-Gauthier-Villars, Leuven-Paris, 1957; réed. éd. J. Gabay, coll "les grands classiques", Paris 1992.
5. Peter Smith, An Introduction to Gödel's Theorems, Cambridge University Press 2007.
6. Raymond M. Smullyan, Gödel's Incompleteness Theorems, Oxford University Press, New York, Oxford 1992.
- Enseignant: Verdée Peter