Logique

Master, M1, Université Paris Cité

Programme

Ordonner : relations d'ordre, ensembles bien ordonnés, ordinaux, arithmétique des ordinaux. Théorèmes de Zermelo et Zorn.
Compter : ensembles finis, ensembles dénombrables, puissance du continu. Théorème de Cantor-Bernstein. Cardinaux. Cofinalité, hypothèse du continu.
Parler : Qu'est-ce qu'une formule ? Variables, termes, quantificateurs…
Interpréter : Modèles et structures. Théorème de compacité, théorème de Löwenheim–Skolem, théorème de Tarski.
Raisonner : Qu'est-ce qu'une démonstration ? Théorème de complétude de Gödel.

Lieu, horaires

Le cours a lieu à partir du 9 septembre 2025, le mardi de 13h45 à 15h15 (SG/2013) et le mercredi de 13h45 à 15h15 (SG/2013) à l'université Paris Cité.

Les travaux dirigés seront assurés par Patrick Simonetta, le mardi de 15h30 à 17h30 (SG/2013) et le jeudi de 15h30 à 17h30 (SG/2013).

Évaluation

Deux contrôles d'1h, en classe, un contrôle de 2h en classe, et un examen final de 3h.

7 octobre, contrôle en classe, 16h30–17h30
13 novembre, contrôle en classe, 2h
2 décembre, contrôle en classe, 1h
examen final, 3h

Les trois contrôles en classe constitueront le contrôle continu.

Documents disponibles

Moodle (accès restreint)
Rédaction (infidèle et incomplète) du cours (PDF), version du 1^er octobre 2025
Une feuille d'exercice sur les filtres, pour celles et ceux qui veulent aller plus loin

Biblographie indicative

Cori, René, et Daniel Lascar (2000). Mathematical Logic: A Course with Exercises. Part I: Propositional Calculus, Boolean Algebras, Predicate Calculus. Traduit par Donald H. Pelletier. Vol. 1. Oxford University Press.
Cori, René, et Daniel Lascar (2000). Mathematical Logic: A Course with Exercises. Part II: Recursion theory, Godel's Theorems, Set theory, Model theory. Traduit par Donald H. Pelletier. Vol. 2. Oxford University Press.
Cori, René, et Daniel Lascar (2003). Logique mathématique, tome 1. Calcul propositionnel, algèbre de Boole, calcul des prédicats. Dunod.
Cori, René, et Daniel Lascar (2003). Logique mathématique, tome 2. Fonctions récursives, théorie des modèles. Dunod.
Dehornoy, Patrick (2017). La théorie des ensembles: introduction à une théorie de l’infini et des grands cardinaux. Tableau noir 106. Calvage & Mounet.
Doxiadis, Apostolos, et Christos H. Papadimitriou (2009). Logicomix—An epic search for truth. Bloomsbury Press, New York.
Krivine, Jean-Louis (1969). Théorie axiomatique des ensembles. Le Mathématicien 1. Presses Universitaires de France.
Krivine, Jean-Louis (1998). Théorie des ensembles. Nouvelle bibliothèque mathématique 5. Cassini.
Mendelson, Elliott (2015). Introduction to Mathematical Logic. 6th éd. Textbooks in Mathematics. CRC Press.

Résumé des séances

mardi 9 septembre: Introduction du cours. Calculer. Fonctions booléennes. Toute fonction booléenne peut s'exprimer uniquement avec les symboles $\vee,\wedge,\neg$. Formules booléennes, théorème de lecture unique (discussion des variantes préfixe ou avec parenthèses, représentation sous forme d'arbre). Évaluation, substitutions. Formes normales. (Références pour cette partie: le premier chapitre du livre de Cori et Lascar, ou le premier chapitre du livre de Mendelson.)
mardi 23 septembre: Filtres. Exemples (filtre de Fréchet, filtres liés à la topologie, ensembles filtrants). Caractérisation des ultrafiltres. Existence d'ultrafiltres.
mercredi 24 septembre: Théorème de Zorn et existence d'ultrafiltres. Ultraproduits, extension de structures aux ultraproduits. Théorème de Łos (début de la démonstration).
mardi 30 septembre: Fin de la démonstration du théorème de Łos. Ultrafiltres et convergence dans les espaces compacts.
mercredi 1^er octobre: Un espace topologique séparé est compact si et seulement si tout ultrafiltre converge. Espace topologique des types, des théories ; caractère séparé, totalement discontinu, compact (énoncé).
mardi 7 octobre: Compacité de l'espace des types. Notion de démonstration formelle.
mercredi 8 octobre: Démonstrations formelles, théories cohérentes.
mardi 14 octobre: Théories henkiniennes. Leur réalisation canonique est un modèle.
mercredi 15 octobre: Théorème de complétude de Gödel. Discussion informelle sur le théorème d'incomplétude et les 1^er (hypothèse du continu) et 10^e (équations diophantiennes) problèmes de Hilbert, ainsi que sur son programme.

Antoine Chambert-Loir— Dernière mise à jour :