Archive année 2020-2021 Complétude et indécidabilité - Sem 2 2020/ ...

L’objectif de ce cours est d’exposer la démonstration du premier théorème d’incomplétude de Gödel en distinguant plusieurs versions. Selon ce célèbre théorème, dont une première version paraît en 1931, toute théorie formelle de l’arithmétique est incomplète, pourvu qu’elle soit axiomatisable et cohérente, et qu’elle ne soit pas trop faible. Cela signifie qu’il existe des énoncés du langage de l’arithmétique qui ne sont ni démontrables ni réfutables dans une théorie de l’arithmétique dès lors que celle-ci satisfait les conditions qui en sont généralement attendues. L’intérêt de ce théorème ne réside pas seulement dans ses conséquences, mais également dans les méthodes utilisées pour sa démonstration. Le second théorème de Gödel, dont l’intérêt philosophique n’est pas moindre, sera également discuté. L’un et l’autre font partie d’une série de célèbres résultats négatifs obtenus en logique dans les années trente du XX^e siècle. Une instance concrète de ces théorèmes est l’indépendance de l’hypothèse du continu de la théorie des ensembles ZFC, ce qui va lier, sans en faire préalable, ce cours au cours de la théorie des ensembles en S1.

Bibliographie

Boolos (G.) et Jeffrey (R.), Computability and Logic, Cambridge University Press, 3e éd., 1989.

Mirna Džamonja, Fast Track to Forcing, Cambridge University Press, 2020.

 Franzén (Torkel), Gödel's theorems. An incomplete guide to its use and abuse, Weslesley, A K Peters, 2005.

 Gödel, K., 1931, “Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I,” Monatshefte für Mathematik Physik, 38: 173–198. English translation in van Heijenoort, éd., From Frege to Gödel, Cambridge, MA: Harvard University Press., 596-616, and in Gödel, Collected Works I, S. Feferman et al. (eds.), Oxford, Oxford University Press., p. 144-195.

 Gödel, K., 1931, “Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I,” Monatshefte für Mathematik Physik, 38: 173–198. English translation in van Heijenoort, éd., From Frege to Gödel, Cambridge, MA: Harvard University Press., 596-616, and in Gödel, Collected Works I, S. Feferman et al. (eds.), Oxford, Oxford University Press., p. 144-195.

 Raatikainen (Panu), "Gödel's Incompleteness Theorems", The Stanford Encyclopedia of Philosophy (Spring 2015 Edition), Edward N. Zalta (ed.), URL = <https://plato.stanford.edu/archives/spr2015/entries/goedel-incompleteness/>.

Smith (Peter), An Introduction to Gödel’s Theorems, Cambridge U. P., 2007, 2e éd. 2013.

Smullyan (Raymond), Gödel’s Incompleteness Theorems, Oxford University Press, 1992.

Informations sur l'espace de cours

Rattachements à l'offre de formation