Logique du premier ordre

Master, M1, Université Paris Diderot

Programme

  1. Notions élémentaires de cardinalité : ensembles finis, ensembles dénombrables, puissance du continu. Théorème de Cantor-Bernstein.
  2. Calcul propositionnel. Mise sous forme normale.
  3. Langages du premier ordre. Formules ; structures ; satisfaction ; théories ; modèles.
  4. Syntaxe et sémantique. Théorème de compacité.
  5. Systemes de déduction. Théorème de complétude (langages dénombrables).
  6. Isomorphismes ; équivalence élémentaire.
  7. Théorème de Löwenheim-Skolem.
  8. 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.
Powered by MathJax Valid CSS! Valid XHTML 1.1! Antoine Chambert-LoirDernière mise à jour :