Cours fondamental : Calculabilité et incomplétude.
- Semaine 1 :
- Semaine 2 (mercredi):
- Système à la Hilbert, équivalence avec la déduction naturelle ; substitution dans les déductions ; normalisation.
- vendredi : cours Arnaud Durand
- Semaines 3 à 8 : cours Arnaud Durand
- Semaine 9 :
- calculabilité : 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, le lemme
de "bourrage" démontré sans référence aux machines, par le
théorème de point fixe ; axiomatisation des familles de
fonctions universelles pour les fonctions récursives,
équivalence par fonctions récursives, et par injections
récursives.
- Feuille d'exercice (théorème
de Rice-Shapiro).
- Sous-ensembles définissables au premier
ordre des entiers naturels : formules et ensembles
Σ0 et Σ1. Fonction β
de Gödel, Caractérisation des fonctions récursives sans
récurrence.
- Résumé de cours sous forme de feuille d'exercices.
- Semaine 10 :
- Partiel le 25/11/09.
- Hiérarchie arithmétique (cours (résumé) et
exercices) : définition de la hiérarchie, propriété de clôture des
classes Σn et Πn, énumération des classes
Σn / Πn ; la hiérarchie est stricte ; il
n'existe pas de relation arithmétique qui énumère tous les prédicats
arithmétiques, première version du théorème de Tarski.
- Semaine 11 :
- Arithmétisation de la syntaxe : le codage des
formules, les prédicats et fonctions utiles, en particulier la
substitution, sont primitives récursives ; théorème de Tarski ; théorie
récursivement axiomatisable, théorie décidable ; codage des
démonstrations : la démontrabilité est Σ1. Un théorème
d'incomplétude faible : si une théorie récursivement axiomatisable a
pour modèle N, il existe des formules vraies dans
N et non démontrables dans la théorie.
- semaine 12 :
-
Système R- (axiomatisation des formules Σ0
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
et donc R-.
-
Le 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
Σ0 vraies dans N, alors il existe un
énoncé Π1 vrai dans N et non démontrable
dans T ; Si de plus T est Σ-cohérentes (théories ne démontrant que
des formules Σ1 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.
- Feuille d'exercices sur le théorème de Gödel.
- semaine 13 :
- 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).
- Second théorème d'incomplétude ; conditions de
dérivabilité de 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.
-
Quelques indications très rapides et très incomplètes pour une
démonstration sémantique du 2nd théorème d'incomplétude en théorie des
ensembles.
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).
En dehors des deux premières références, ces livres couvrent largement plus
sur le sujet que ce qui est abordé en cours.
(dernière modification le vendredi 18/12/2009, 19:40:53 CET)