Logique du premier ordre
Master, M1, Université Paris Diderot
Programme
-
Notions élémentaires de cardinalité : ensembles finis, ensembles dénombrables,
puissance du continu. Théorème de Cantor-Bernstein.
-
Calcul propositionnel. Mise sous forme normale.
-
Langages du premier ordre. Formules ; structures ; satisfaction ; théories ;
modèles.
-
Syntaxe et sémantique. Théorème de compacité.
-
Systemes de déduction. Théorème de complétude (langages dénombrables).
-
Isomorphismes ; équivalence élémentaire.
-
Théorème de Löwenheim-Skolem.
-
Théories complètes. Critère de Vaught.
Lieu, horaires
Le cours a lieu le mardi de 15h30 à 17h30,
à l'Université Paris-Diderot (HF/404B).
Les travaux dirigés seront assurés par François Le Maître, d'une part
le lundi de 13h45 à 15h45 (GM/191C)
et d'autre part
le jeudi de 13h15 à 15h15 (OG/164), en alternance avec le cours de complexité.
Il y aura un cours supplémentaire le mardi 13 décembre, de 15h45 à 17h45, salle 136 du bâtiment Olympe de Gouges.
L'examen aura lieu le lundi 9 janvier, de 9h à 12h, salle 2007 du bâtiment Sophie Germain. Il sera sans documents.
Documents disponibles
Résumé des séances
- mardi 13 septembre
- Introduction du cours. Compter.
Rappels de théorie des ensembles, paradoxe de Russell, théorème de Zorn (admis).
Cardinal d'un ensemble fini.
Ensembles dénombrables, dénombrabilité de $\mathbf N\times\mathbf N$,
d'une réunion dénombrable d'ensembles dénombrables, d'un produit fini d'ensembles dénombrables.
Cardinaux, théorèmes de Cantor et Cantor-Bernstein.
- mardi 20 septembre
- Arithmétique des cardinaux.
- mardi 27 septembre
- Parler.
Alphabets, mots , cardinal de l'ensemble des mots dans un alphabet donné.
Langages du premier ordre, exemples. Termes ; principe de récurrence selon la définition d'un terme ;
hauteur d'un terme. Critère de reconnaissance d'un terme et théorème de lecture unique.
- mardi 4 octobre
- Substitution de variables par des termes ;
sous-termes et arbre d'évaluation. Formules :
formules atomiques, principe de récurrence selon la définition d'une formule ; hauteur d'une formule. Théorème de lecture unique. Variables libres, variables liées.
- mardi 11 octobre
- Interpréter.
Réalisations d'un langage. Interprétations des termes et des formules. Compatibilité par substitution.
- mardi 18 octobre
- Retour sur la compatibilité par substitution dans les formules.
Théories, modèles.
Théorème de compacité de Gödel ; espace des théories complètes
est un espace topologique compact et totalement discontinu.
Ultraproduits de structures, théorème de Łos.
- mardi 8 novembre
- Extensions élémentaires, théorème de Tarski–Vaught.
Théorèmes de Löwenheim–Skolem et de Tarski
(« Löwenheim–Skolem ascendant »).
- mardi 15 novembre
- Fin de la preuve du théorème de compacité. Raisonner.
Règles de déduction : axiomes logiques, modus ponens, généralisation.
Démonstration et satisfaction.
- mardi 22 novembre
- Théories cohérentes.
- mardi 29 novembre
- Théories henkiniennes. Existence d'un modèle.
Antoine Chambert-Loir—
Dernière mise à jour :