Résumé de section

  • Semestre 1

    Théorie des ensembles

     Mirna Džamonja Cantor

    Au cours du 19e siècle, une crise profonde toucha les mathématiques dans leurs fondements, soulevant plusieurs questions concernant la nature de cette discipline et le statut ontologique de ses entités. Cela a engendré le programme de Hilbert envisageant une axiomatisation complète des mathématiques. Dans le cours, nous présenterons l’univers ensembliste développé par Cantor à travers lequel certaines  réponses  ont été envisagées.

    La théorie des ensembles est en fait la science de l’infini ou au moins de sa manifestation mathématique. Nous analyserons notamment les infinis différents ( !), la construction des ordinaux et des cardinaux, ainsi que leurs arithmétiques, dont la distinction est exigée dans le cas infini. Aux travaux précurseurs de Cantor succédèrent plusieurs tentatives de formalisation de la théorie des ensembles. Nous verrons les motivations à la source de ces entreprises,  puis étudierons la plus célèbre : l’axiomatique de Zermelo-Fraenkel, en portant un regard attentif sur l’axiome du choix, axiome à l’efficacité mathématique indéniable mais à la légitimité parfois contestée.   

    Extrait de la bibliographie du cours

    K.J.B. Devlin, The joy of sets : Fundamentals of contemporary set theory. Springer, 1993.

    M. Dzamonja, Théorie des ensembles pour les philosophes, Sarrebruck, Editions universitaires européennes, 2017.

     

    Théorie des modèles

     Andy Arana Skolem

    La théorie des modèles étudie les structures mathématiques et leurs descriptions linguistiques. On commence avec une enquête sur la définissabilité, concernant en particulier l’expressivité des langues spécifiques (par exemple, le langage de l'arithmétique). On continue avec l'élimination des quantificateurs et les théories o-minimals : c'est-à-dire, les théories des nombres réelles. Ensuite, on considère les modèles premiers, atomiques, et saturés, et la notion d'un type. Enfin, on peut commencer une enquête sur les théories omega-catégorique et les théories stables, vers une étude de la géométrie des ensembles minimales et la théorie des modèles géométrique.

    Extrait de la bibliographie

    B. Poizat, Cours de théorie des modèles, Nur al-Mantiq wal-Ma'rifah, 1985.

    D. Marker, Model Theory: An Introduction, Springer, 2002

    B. Zilber. « Model Theory », dans A Course in Mathematical Logic for Mathematicians par Y. Manin, deuxième edition, Springer, 2009.

     

    Théorie de la démonstration

    Jean Fichot Gentzen

    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) … Si le temps le permet : théories de Harrop, arithmétique de Heyting ; aspects constructifs de la logique classique : théorème de Kreisel, théorème de Herbrand). Déduction naturelle multi-conclusions…

    Extrait de la bibliographie

    David René, Nour Karim, Raffalli Christophe, Introduction à la logique : Théorie de la démonstration, Dunod, Paris, 2001.

    Negri Sara, von Plato Jan, Structural proof theory, Cambridge University Press, 2001.

     

     

    Calculabilité Kleene

    Alberto Naibo

    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èrmes 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.

    Ce cours est conçu de manière jumelée et complémentaire avec le cours “Complétude et indecidabilité” (S1).

    Extrait de la bibliographe

    Boolos, G., Burgess, J. & Jeffrey, R. (2007). Computability and Logic (5ème éd.). Cambridge: Cambridge U. P.

    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.


     

    Philosophie des mathématiques

    Jean Fichot Brouwer

    Logique et mathématiques constructives

    L’accent sera mis sur les questions suivantes (entre autres) : comment peut-on justifier le rejet d’une loi logique ? Ce refus peut-il se fonder uniquement sur des arguments de nature mathématique ? Si d’autres arguments, conceptuels et philosophiques, sont en plus nécessaires, quels sont-ils ? De la logique et des mathématiques, laquelle de ces deux disciplines est première ? Quels rapports entretiennent les notions d’effectivité humaine et de calculabilité mécanique ? etc.

    Extrait de la bibilographie

    Dummett M.A.E. Elements of intuitionism. Clarendon Press, Oxford, 2000.

    Largeault J. Intuition et intuitionisme, Mathesis, Vrin, Paris, 1993.

     

    Semestre 2

    Complétude et indécidabilité Kurt Gödel (1906-1978)

    Pierre Wagner

    L’objectif de ce cours est d’exposer la démonstration du premier théorème d’incomplétude de Gödel, d’en distinguer plusieurs versions et de discuter certains de ses enjeux philosophiques. Selon ce célèbre théorème, dont la première version paraît en 1931, toute théorie formelle de l’arithmétique est incomplète, pourvu qu’elle soit axiomatisable et cohérente, et qu’elle ne soit pas trop faible. Cela signifie qu’il existe des énoncés du langage de l’arithmétique qui ne sont ni démontrables ni réfutables dans une théorie de l’arithmétique dès lors que celle-ci satisfait les conditions qui sont généralement attendues d’une telle théorie. L’intérêt de ce théorème ne réside pas seulement dans ses conséquences, mais également dans les méthodes utilisées pour sa démonstration. Le second théorème de Gödel, dont l’intérêt philosophique n’est pas moindre, sera également discuté. L’un et l’autre font partie d’une série de célèbres résultats négatifs obtenus en logique dans les années trente du xxe siècle.

    Extrait de la bibliographie

    P. Smith, An Introduction to Gödel’s Theorems, Cambridge University Press, 2007, 2e éd. 2013.

    T. Franzén, Gödel’s Theorem. An Incomplete Guide to Its Use and Abuse, A K Peters, 2005.

     

    Logique et fondements de l'informatique

     Alberto Naibo Herbrand

    Ce cours consiste en une introduction à des problèmes fondamentaux de l’informatique théorique, abordés d’un point de vue logique. Le cours sera plus précisément centré autour de l’étude d’un langage de programmation abstrait introduit au début des années trente par A. Church: le lambda-calcul. On présentera d’abord une version pure de ce calcul. Puis, en focalisant l’attention sur le problème de la terminaison des programmes, on introduira une version typée. On montrera ensuite que les propriétés fondamentales de cette version typée peuvent être étudiées d’un point de vue purement logique, grâce à la correspondance dite de Curry-Howard. Cette correspondance assure en effet l’existence d’un isomorphisme entre les règles de réécriture (ou règles d’exécution) pour les programmes écrits en lambda-calcul typé et les règles de réduction (ou règles de normalisation) pour les preuves écrites en déduction naturelle minimale ou intuitionniste. On terminera par la présentation d’une extension du lambda-calcul typé à des systèmes non logiques, comme le système de déduction naturelle pour l’arithmétique constructive.

    Extrait de la bibliographie

    Polycopié distribué en cours, couvrant l’ensemble du programme et contenant une sélection d’exercices.

     

    Barendregt, H. & Barendsen, E. (2000). Introduction to Lambda Calculus. Manuscrit (disponible en ligne à l'adresse: http://www.cse.chalmers.se/research/group/logic/TypesSS05/Extra/geuvers.pdf).

     
     

    Logique des modalités

    francesca poggiolesiSaul Kripke (né en 1940)

    Ce cours se propose d’examiner les principaux systèmes de logique modale tant d’un point de vue formel que d’un point de vue philosophique.

    Le terme « logique modale » est aujourd’hui employé pour indiquer un domaine d’investigation très vaste et très varié.  Dans ce domaine on a pourtant isolé un certain nombre de systèmes qui représentent la base et le fondement de toute étude relative à la logique modale. Nous analyserons ces systèmes en détail.

    -        D’un point de vue formel, nous étudierons les principaux systèmes de logique modale à travers trois formalisations différentes : les axiomes à la Hilbert, la sémantique des mondes possibles et les systèmes de preuves. Nous allons examiner les relations entre ces trois formalisations différentes et nous mettrons aussi en relief le lien avec la logique du premier ordre.

    D’un point de vue conceptuel, nous introduirons les principales interprétations liées à nos systèmes de logique modale. Nous commencerons par les concepts de nécessité et de possibilité, puis nous nous arrêterons sur une interprétation en termes d’obligation et de permission. Finalement nous consacrerons une analyse approfondie à une interprétation épistémique des modalités, c’est-à-dire en termes de connaissance et de croyance. Cette dernière interprétation nous permettra de dire quelques mots sur les développements les plus récents de logique modale, à savoir la logique dynamique..

    Extrait de la bibliographie

    J. Garson, "Modal logic", Stanford Encyclopedia of Philosophy, Spring 2016 ed.

    F. Poggiolesi, Gentzen calculi for modal propositional logic, Springer, 2010.

     

    Philosophie de la logique

    Pierre Wagner

    La prédicativité (cours mutualisé M1 et M2) Poincaré (1854-1912)

    Une définition est dite « imprédicative » si elle présuppose une totalité à laquelle appartient l’objet à définir, ce qui se produit par exemple lorsque l’ensemble des entiers naturels est défini comme le plus petit ensemble inductif. Le procédé général de l’imprédicativité peut sembler vicieusement circulaire et il fut rejeté par Russell et Poincaré au motif qu’il serait source de certains paradoxes logiques bien connus. Les définitions imprédicatives se révèlent cependant d’usage courant et décider de s’en passer entièrement suppose l’élaboration d’une stratégie de remplacement. Une caractérisation précise fait en outre apparaître de multiples formes d’imprédicativité. Dans ce cours, nous discuterons plusieurs définitions de la prédicativité, ainsi que les questions qu’elles soulèvent tant d’un point de vue historique que dans la philosophie de la logique contemporaine.

    Extrait de la bibliographie

    R. Adams, "A survey of predicativity", en ligne.

    G. Heinzmann, éd., Poincaré, Russell, Zermelo et Peano. Textes de la discussion (1906-1912) sur les fondements des mathématiques: des antinomies à la prédicativité, Paris, Albert Blanchard, 1986.

    .