Complétude et indécidabilité

1- Complétude et indécidabilité (3 ECTS) K4041215 

Le but de ce cours est de démontrer plusieurs théorèmes célèbres d'incomplétude et d'indécidabilité et d'en discuter l'interprétation et les conséquences philosophiques.

Le cœur du cours consiste en la démonstration de deux théorèmes importants : le premier théorème d'incomplétude de Gödel (qui affirme en substance que toute théorie axiomatique de l'arithmétique qui est cohérente et « suffisamment forte » est incomplète, au sens où il existe des énoncés de son langage qu'elle ne permet ni de démontrer ni de réfuter), et un théorème d'indécidabilité apparenté (d'après lequel toute théorie vérifiant les hypothèses précédentes est indécidable, au sens où il n'existe pas de procédure algorithmique permettant, étant donné un énoncé de son langage, de déterminer en un temps fini si celui-ci y est ou n'y est pas démontrable). La démonstration de ces théorèmes est très instructive et introduit des idées et outils essentiels en logique mathématique, qui, entre autres, font le lien entre étude des systèmes formels et théorie de la calculabilité. 

Nous aborderons également le second théorème d'incomplétude de Gödel et le théorème d'indéfinissabilité de la vérité de Tarski, et discuterons la signification et la portée des résultats démontrés.

Quoique ce ne soit pas absolument indispensable (quelques rappels seront fournis), une familiarité préalable avec la théorie de la calculabilité, qui fait l'objet d'un cours au premier semestre, est recommandée. Des notes de cours seront fournies.

Indications bibliographiques

Smith, Peter. An Introduction to Gödel's Theorems. 2e édition, Cambridge : CUP, 2013.

Cori, René et Lascar, Daniel. Logique mathématique, vol. 2 : Fonctions récursives, théorème de Gödel, théorie des ensembles, théorie des modèles. Paris : Dunod, 2003.