Option logique

3- Théorie de la calculabilité (3 ECTS)   K4041515

Dans ce cours on se propose d’étudier, d’un point de vue formel, des notions comme celles de calcul et d’algorithme. Plus précisément, il s’agira de fournir une analyse logico-mathématique de notions qui concernent l’exécution d’une action de manière purement mécanique, c’est-à-dire sans faire appel à des formes d’intuition ou d’ingéniosité quelconques. Les instruments privilégiés pour poursuivre cette étude seront les fonctions récursives, suivant la tradition de K. Gödel et S.C. Kleene. Après avoir défini la classe de ces fonctions, on démontrera des théorèmes qui les concernent. D’une part, on établira des résultats positifs, comme la possibilité de ramener chacune de ces fonctions à une certaine forme normale, en donnant ainsi la possibilité d’avoir un modèle abstrait et universel de représentation des processus mécaniques de calcul. De l’autre, on établira des résultats négatifs – ou mieux limitatifs –, comme l’impossibilité de décider à l’avance si chaque processus mécanique s’arrêtera ou pas.

Bibliographie : 

• Polycopié distribué en cours, couvrant l’ensemble du programme et contenant une sélection d’exercices.
• Boolos, G., Burgess, J. & Jeffrey, R. (2007). Computability and Logic (5ème édition). Cambridge: Cambridge University Press.
• van Dalen, D. (2001). Algorithms and decision problems: A crash course in recursion theory. Dans D.M. Gabbay et F. Guenthner (dir.), Handbook of Philosophical Logic (2ème édition), Vol. 1, p. 245-311. Dordrecht: Kluwer. 
• van Dalen, D. (2004). Logic and Structure (5ème édition). Berlin: Springer (chap. 8).
• Epstein, R.L. & Carnielli, W.A. (2008). Computability: Computable functions, logic and the foundations of mathematics (3ème édition). Socorro (New Mexico): Advanced Reasoning Forum.
• Odifreddi, P. & Cooper, B. (2012). “Recursive functions”. Dans E.N. Zalta (dir.), The Stanford Encyclopedia of Philosophy, <http://plato.stanford.edu/entries/recursive-functions/>.
• Odifreddi, P. (1989). Classical Recursion Theory. Amsterdam: Elsevier.
• Rogers, H. (1987). Theory of Recursive Functions and Effective Computability. Cambridge (Mass.): MIT Press.

       Terwijn, S. (2008). Éléments de théorie de la calculabilité, trad. fr. M. Cadilhac, manuscrit, <http://www.math.ru.nl/~terwijn/publications/syllabus_fr.pdf>.

Voir la page complète

2- Théorie de la démonstration (3 ECTS)    K4041315

Résumé 

Variantes et fragments de la déduction naturelle classique du premier ordre. Propriétés des preuves sans coupures. Elimination des coupures et applications : démonstrations de cohérence et d'indépendance, constructivité (le cas intuitionniste: arithmétique de Heyting ; aspects constructifs de la logique classique : déduction naturelle multi-conclusions).

Bibliographie

Un polycopié et des exercices seront donnés sur l'EPI du cours. 

David R., Nour K., Raffalli C., Introduction à la logique : Théorie de la démonstration, Dunod, Paris,2001. 

Negri S., von Plato J., Structural proof theory, Cambridge University Press, 2001.

Prawitz D., Natural Deduction, Almquist et Wiksell, Stockholm, 1965. Réédition Courier Dover Publications, 2006. 

Voir la page complète

2- Théorie des modéles (3 ECTS)   K4041115

Ce cours propose d’introduire à la théorie des modèles classique. L’approche dite « modèle-théorique » de la logique classique vise à caractériser les structures qui satisfont les théories du premier ordre de manière à pouvoir les comparer (en l’occurrence leurs propriétés sémantiques et mathématiques, comme leur expressivité, leur nombre, leur taille, etc.). Tout à fin de mieux les classer et de comprendre leur globalité. Dans ce cours, nous partirons d’un langage interprété pour la logique du premier ordre, présenterons un théorème de complétude dans ce cadre, puis étudierons les résultats les plus fondamentaux, positifs ou négatifs, de la théorie des modèles classique : définissabilité, compacité, théorème de Löwenhein-Skolem et ses conséquences, interpolation, caractérisation de Lindström, etc.

Bibliographie indicative:

-C.C Chang and H.J Keisler, Model Theory, 3rd Ed., Dover Books 2012
-Wilfrid Hodges, A Shorter Model Theory, Cambridge University Press, 1997. 
-Jouko Väänänen, Models and Games, Cambridge University Press, 2011

Voir la page complète