LOG – Logique (2ème semestre, 6 ECTS)

Alexandre Miquel

Cours : Natacha Portier

TD : Guilhem Gamard & Alexis Ghyselen

Cours de Logique Mathématique, partant des bases de la logique jusqu’aux résultats majeurs du tournant des années 30 (dont les théorèmes d’incomplétude de Gödel).

Contenu indicatif du cours :

Théorie naïve des ensembles :

  •  Constructions en théorie des ensembles, théorème de Cantor-Bernstein.
  • Ordinaux, cardinaux, bonne fondation, hiérarchie de Veblen.
  • L’axiome du choix et ses différentes formes.

Théories du premier ordre :

  • Langages du premier ordre, système de déduction (déduction naturelle).
  • Notion de théorie du premier ordre, d’extension conservative.
  • Exemples: l’Arithmétique de Peano (PA) et la Théorie des ensembles de Zermelo-Fraenkel (ZF).

Modèles de Tarski :

  • Structures, notions d’isomorphisme et d’équivalence élémentaire
  • Théorèmes de complétude, de compacité et de Löwenheim-Skolem.
  • Applications à PA et à ZF.

Théorèmes d’incomplétude :

  • Indécidabilité de l’arithmétique, lien avec les fonctions récursives,
  • Théorèmes d’incomplétude de Gödel.

Prérequis : pas de prérequis particulier si ce n’est une connaissance élémentaire des objets manipulés (ensembles, connecteurs/quantificateurs logiques, démonstrations usuelles en mathématiques).