• Votre sélection est vide.

    Enregistrez les diplômes, parcours ou enseignements de votre choix.

Complétude et indécidabilité

  • Composante

    UFR de philosophie (UFR10)

  • Volume horaire

    26h

  • Période de l'année

    Printemps

Description

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

David Waszek 

  Mercredi 13h30-15h30

  G303 – esc. C, 3e étage

 

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.

Lire plus