Cours fondamental : Calculabilité et incomplétude (2013-2014).

• Semaine 1 (17/09/2013) :
  • Fonctions récursives primitives.
  • énumération des fonctions récursives primitives. Fonctions récursives partielles, et fonctions récursives totales. Ensembles récursivement énumérables.
• Semaine 2 (24/09/2013) :
  • Machines à registres. Fonctions calculables par machines à registre ; forme normale de Kleene.
• Semaine 3 (31/09/2013) :
  • Théorème d'énumération (fonctions et machines universelles) ; indice d'une fonction récursive partielle ; lemme de bourrage.
  • Théorème de paramétrisation (s-m-n).
  • Ensembles récursivements énumérables : définition et caractérisations.
  • Polycopié (version provisoire), pages 1 à 34.
• Semaine 4 (7/10/2013) :
  • Réduction récursive, ensembles complets ; théorèmes du point fixe de Kleene.
  • Applications du théorème s-m-n et des théorèmes de point fixe : la fonction d'Ackermann est récursive ; axiomatisation des familles de fonctions universelles pour les fonctions récursives, équivalence par fonctions récursives ; équivalence par injections récursives, et bijection récursive.
• Semaine 5 (14/10/2013) (A.D.) :
• Semaine 6 (21/10/2013) (A.D.) :
• Semaine 7 (28/10/2013) (A.D.) :
  • Toussaint
• Semaine 8 ( 4/11/2013) :
  • Ensembles Sigma ; les graphes des fonctions récursives partielles sont Sigma ; caractérisation des fonctions récursives sans récurrence ; les ensembles récursivement énumérables sont Sigma.
  • Hiérarchie arithmétique.
• Semaine 9 (11/11/2013) :
  • la classe des ensembles définissable dans l'arithmétique du 1er ordre n'est pas définissable dans l'arithmétique du premier ordre ; la vérité des formules de l'arithmétique n'est pas définissable dans l'arithmétique ; codage des formules.
  • Polycopié (version provisoire), mise à jour pages 1 à 82.
  • Partiel 15/11/2013
• Semaine 10 (18/11/2013) :
  • Codage des démonstrations ; théories récursivement axiomatisables et décidables ; une forme faible du théorème d'incomplétude (si T est récursivement axiomatisable et a pour modèle N alors T il existe une formule vraie dans N non démontrable dans T.
  • Système R^- (axiomatisation des formules Σ₀ vraies dans N) et R (on ajoute le schéma d'axiomes qui exprime que tout élément standard est inférieur à tout élément non standard) de Robinson. Une théorie a pour conséquence R^- si et seulement si elle démontre toutes les formules Σ vraies dans le modèle standard N des entiers naturels. L'arithmétique de Peano PA et l'arithmétique finie de Robinson Q ont pour conséquence R (en particulier elles sont Σ-complètes, c'est-à-dire que toutes les formules Σ vraies dans N sont démontrables.
• Semaine 11 (25/11/2013) :
  • Premier théorème d'incomplétude de Gödel : Si T est une théorie récursivement axiomatisable cohérente, qui démontre tous les énoncés Σ₀ vraies dans N, alors il existe un énoncé Π₁ vrai dans N et non démontrable dans T ; Si de plus T est Σ-cohérente (théories ne démontrant que des formules Σ₁ vraies dans N), la négation de cet énoncé n'est pas non plus démontrable dans T. Existence de théories non Σ-cohérentes.
  • Théorème d'indécidabilité de Church, et d'incomplétude de Gödel-Rosser : une théorie arithmétique cohérente qui étend R est indécidable, et donc, si de plus elle est récursivement axiomatisable, elle est incomplète (par la représentation des ensembles récursifs dans de telles théories).
  • Indécidabilité du calcul des prédicats dans le langage de l'arithmétique ; N muni des opérations usuelles est fortement indécidable, c'est-à-dire que toutes les théories ayant N pour modèle sont indécidables ; quelques résultats d'indécidabilité par définissabilité de N (muni des opérations usuelles).
• Semaine 12 ( 2/12/2013) :
  • Second théorème d'incomplétude ; conditions de dérivabilité de Hibert-Bernays-Löb ; quelques conséquences simples, dont le théorème de Löb.
  • Exemple d'application du second théorème d'incomplétude en théorie des ensembles : ZF n'est pas finiment axiomatisable au dessus de Z.
  • Une démonstration sémantique du 2nd théorème d'incomplétude en théorie des ensembles (cf. Krivine chjap. 9).
• Semaine 13 ( 9/12/2013) :
• Semaine 14 ( 16/12/2013) :
  • Examen 16 décembre 2013

Bibliographie

• R. Cori, D. Lascar, Logique mathématique : cours et exercices (tome 2, Masson, 1993)
• Raymond Smullyan, Les théorèmes d'incomplétude de Gödel (Masson, 1993), trad. Gödel incompletness theorems, Oxford University Press 93.
• C. Smorynski, Logical Number Theory I : an Introduction (Springer Verlag, 1991)
• P. Oddifredi, Classical recursion theory (North Holland, 1989)
• H. Rogers, Theory of recursive functions and effective computability (Mc Graw-Hill, 1967)
• S.C. Kleene, Introduction to metamathematics (North Holland, 1952).
• Jean-Louis Krivine, Théorie des ensembles, (Cassini 1998 et 2007) chap. 9 (pour le second théorème d'incomplétude).

En dehors des deux premières références, ces livres couvrent largement plus sur le sujet que ce qui est abordé en cours.

Master

• Site du M2