Master de philosophie Parcours Logique Cours de logique, et d ...

Master de philosophie
Parcours Logique

Cours de logique, et d'histoire et philosophie de la logique
(extrait de la brochure de la spécialité Lophisc du Master)



Théorie des ensembles 1 (S1)
Susana BERESTOVOY
A la fin du 19e siècle, une profonde crise toucha les mathématiques dans
leurs fondements, soulevant plusieurs questions concernant la nature de
cette discipline et le statut ontologique de ses entités. Dans le cours,
nous présenterons l'univers ensembliste développé par Cantor à travers
lequel certaines réponses ont été envisagées. Nous analyserons notamment
les problèmes à l'origine de l'introduction du transfini et de l'infini
actuel, en opposition à l'infini potentiel, la construction des ordinaux et
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 Zermalo-Fraenkel, en portant un regard
attentif sur l'axiome du choix, axiome à l'efficacité mathématique
indéniable mais à la légitimité largement contestée.
Références
. K.J.B. Devlin, The joy of sets : Fundamentals of contemporary set
theory. Springer, 1993.
. H.B. Enderton, Elements of set theory. Academic Press, 1977.
. M. Machover, Set theory, logic and their limitations. Cambridge
University Press, 1996.
. R. Smullyan et M. Fitting, Set theory and the continuum problem,
Clarendon Press, Oxford, 1996.
. J.L. Krivine, Théorie des ensembles, Cassini, 2007.
Une bibliographie supplémentaire, ainsi que des notes de cours seront
distribuées.

Théorie des ensembles 2 (S2)
Susana BERESTOVOY
Cet enseignement est le prolongement de celui du premier semestre et
développe les questions abordées au sujet de l'axiome du choix. Si
l'adoption de ce dernier est problématique, il est crucial de déterminer
son lien avec les autres axiomes de la théorie de Zermelo-Fraenkel: en est-
il réellement indépendant ou démontrable à partir d'eux ? Si la théorie
privée de cet axiome est cohérente, autrement dit qu'elle ne démontre pas
une contradiction, la théorie enrichie de cet axiome le demeure-t-elle ?
Dans les langages qui nous intéressent, la cohérence d'une théorie est
équivalente à l'existence d'un modèle de cette théorie. Afin de résoudre
ces problèmes, nous étudierons donc de près les différents modèles de la
théorie de Zermelo-Fraenkel, notamment l'univers constructible introduit
par Gödel. Nous serons amenés à discuter certains paradoxes, dont
l'existence d'un modèle dénombrable qui, pourtant, contient lui-même des
ensembles non dénombrables.
Bibliographie : Voir semestre 1.

Complétude et indécidabilité (S1)
Susana BERESTOVOY,
Le but de ce cours est de donner une démonstration du premier théorème
d'incomplétude de Gödel. Nous présentons les notions en jeu dans l'énoncé
de ce théorème: Complétude, consistance, décidabilité, démontrabilité,
théorie axiomatique, arithmétique complète. Nous décrivons en suite la
structure de la démonstration du théorème et traitons les relations qui
existent entre les niveaux qui y interviennent : métathéorie, théorie
formelle et structure, via l'arithmétisation de la syntaxe et la
représentation de fonctions dans une théorie. La caractérisation de la
classe de fonctions représentables et la diagonalisation permettent
d'établir le résultat d'incomplétude.
Références
. G. Boolos et R. Jeffrey, Computability and Logic, Cambridge
University Press, 1989.
. P. Smith, An Introduction to Gödel's Theorems, Cambridge University
Press, 2008.
. R. Smullyan, Gödel's Incompleteness Theorems, Oxford University
Press, 1992.
. E. Nagel & J.R. Newman, La demonstration de Gödel, in Le théorème de
Gödel, Seuil, 1989.
. Une bibliographie supplémentaire, ainsi que des notes de cours
seront distribuées.

Théorie des modèles 1 (S1)
Méven Cadet

La théorie des modèles, développée dans le courant du 20e siècle à partir
des travaux fondateurs d'Alfred Tarski, s'est rapidement imposée comme une
branche centrale de la logique, permettant une étude fouillée des
structures mathématiques au sein d'un cadre formel rigoureusement défini.
Cet enseignement vise à en transmettre les outils désormais classiques.
Nous débuterons par des exemples de propriétés définissables dans ce cadre
(notamment celle d'être infini) et d'autres qui ne le sont pas (notamment
celle d'être fini) jusqu'à démontrer les théorèmes de complétude et de
compacité qui en fixent simultanément les avantages et les limites. Nous
aborderons ensuite l'étude des relations entre les structures à travers les
concepts d'isomorphisme, d'équivalence élémentaire et d'extension
élémentaire puis nous prouverons les théorèmes de Löwenheim-Skolem.
Références
. Van Dalen, Logic and Structure, Springer, 2004.
. J. Bell & M. Machover, A course in Mathematical Logic, North Holland
Publishing Company, 1977.
. R. Cori & D. Lascar, Logique Mathématique, Masson, 2003.
Textes fondateurs :
. Tarski, A., "On the Concept of Logical Consequence", Actes du
Congrès International de philosophie Scientifique, vol. 7, p. 1-11,
1936.
. Tarski, "The Semantical Concept of Truth and the Foundations of
Semantics", Philosophy and Phenomenological Research 4, p. 341-75,
1944.
Textes philosophiques contemporains :
. J. Etchemendy, The concept of logical consequence, Harvard
University Press, 1990.
. G. Sher, The bounds of logic, The MIT Press, 1991.
Pour aller plus loin :
. C.C. Chang & H.J. Keisler, Model Theory, Elsevier Science Ltd, 3e
edition, 1990.
. D. Marker, Model Theory: An introduction, Springer, 2002.

Théorie des modèles 2 (S2)
Susana BERESTOVOY

Un des enjeux fondamentaux de la théorie des modèles est d'établir le
rapport existant entre les modèles d'une théorie et de déterminer si une
théorie décide tous les énoncés de son langage, i.e. si elle est complète.
En utilisant les notions introduites et les résultats démontrés au premier
semestre, nous abordons l'étude de la classe de modèles d'une théorie et
caractérisons les théories k-catégoriques, complètes et modèle-complètes.
Nous présentons les relations entre ces notions et des résultats (test de
Vaught, théorème de Robinson) qui permettent d'établir la complétude d'une
théorie.
Références : Voir semestre 1.

Théorie de la démonstration 1 (S1)
Jean Fichot

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: 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.
Bibliographie
. polycopié (150 p.) distribué en cours et couvrant l'ensemble du
programme.
. David René, Nour Karim, Raffalli Christophe, Introduction à la
logique : Théorie de la démonstration, Dunod, Paris,2001.
. Girard Jean-Yves, Laffont Yves, Tailor Paul, Proofs and types,
Oxford University Press, 1989.
. Girard Jean-Yves, Le point aveugle (tome 1 et 2), Hermann, Paris,
2006 et 2007
. Negri Sara, von Plato Jan, Structural proof theory, Cambridge
University Press, 2001.
. Prawitz Dag, Natural Deduction, Almquist et Wiksell, Stockholm, 1965

Théorie de la démonstration 2 (S2)
G. Pulcini

Variantes et fragments du calcul des séquents pour la logique classique
du premier ordre et pour la logique intuitionniste. Propriétés
structurelles des preuves : admissibilité de l'atténuation et de la
contraction et invariabilité des règles logiques. Démonstration détaillée
du théorème d'élimination des coupures. Brève analyse des théorèmes de
validité et de complétude. Analogies et différences entre calcul des
séquents et déduction naturelle. Réflexions philosophiques sur les
positions anti-realistes liées au calcul des séquents et la signification
des constants logiques.
Bibliographie?
. R. David, K. Nour, C. Raffalli, Introduction à la logique : Théorie
de la démonstration, Dunod, Paris,2001.
. ?J.-Y. Girard, Y. Laffont, P. Tailor, Proofs and types, Oxford
University Press, 1989.
. ?F. Poggiolesi, Gentzen Calculi for Modal Propositional Logic,
Springer, 2010.
. Troelstra, H. Schwichtenberg, Basic Proof Theory, Cambridge
University Press, 2000.

Calculabilité (S1)
Aurélien Ohayon


Nous présenterons dans ce cours quelques contreparties formelles
(machines de Turing, fonctions récursives) à la notion de fonction
calculable. Nous montrerons ensuite l'équivalence de ces différents
formalismes, puis présenterons quelques résultats fondamentaux de la
théorie de la calculabilité, théorie qui apporte des réponses aux questions
des limites de l'informatique. Nous montrerons notamment que certains
problèmes informatiques ne peuvent pas être résolus par des programmes. En
particulier le fameux problème dit "de l'arrêt", parmi d'autres résultats
limitatifs.


Références
. Pierre Wolper, Introduction à l