Archives de l’auteur : nportier

Logique 2022

Logique, cours de L3, second semestre
Plan du cours (les numéros de cours ne sont pas toujours respectés à la lettre)

  1. Le calcul propositionnel et son théorème de compacité. Cours 1
  2. La syntaxe de la logique du premier ordre et les preuves en déduction naturelle  Cours 2
  3. La sémantique de la logique du premier ordre : interprétation (modèle), vérité, morphismes  Cours 3
  4. Le théorème de complétude de Gödel Lien entre la syntaxe et la sémantique.
    1. Le théorème de correction  Cours 4
    2. Le théorème de complétude  Cours 5
  5. Le théorème de compacité. Quelques applications.  Cours 6
  6. L’arithmétique de Peano Cours 7
  7. Les théorèmes d’incomplétude de Gödel Cours 7 et 8
    1. L’arithmétisation de la syntaxe
    2. Les théorèmes de Tarski, Gödel
  8. La théorie des ensembles Cours 9 à 11
    1. La théorie naïve des ensembles et la définition des ordinaux
    2. Les axiomes de Zermelo-Fraenkel
    3. L’axiome du choix et l’axiome de fondation
  9. Applications selon le temps qu’il reste
    1. L’élimination des quantificateurs dans les corps réels clos Cours 12
    2. L’élimination des quantificateurs dans les corps algébriquement clos Cours 13

Bibliographie pour le cours:

  • Logique mathématique, René Cori et Daniel Lascar, deux tomes chez Dunod (et première édition Axiomes). Cours et exercices. Plusieurs exemplaires à la bibliothèque. Dans le premier tome : Calcul propositionnel, Algèbre de Boole, Calcul des prédicats, Théorèmes de complétude. Second tome : Récursivité (inclus les machines de Turing) , Formalisation de l’arithmétique, théorèmes de Gödel, théorie des ensembles, un peu de théorie des modèles. (à la Bib)
  • Introduction à la logique, Théorie de la démonstration, René David, Karim Nour et Christophe Raffalli, Dunod (à la Bib)
  • cours de Zoe Chatzidakis (cours de logique, automne 2014)
  • Jean-Louis Krivine, théorie des ensembles (chez Cassini, ou la vieille version aux PUF)
  • Le cours sur le théorème de Gödel d’Alexandre Miquel
  • Quantifier Elimination following Muchnik, Christian Michaux et Adem Ozturk

Videos de vulgarisation:

Bibliographie pour la plage :

  • Logicomix : an epic search for the truth (roman graphique disponible en français et en anglais à la bibliothèque)
  • La logique, Gilles Dowek, Dominos Flammarion
  • et pourtant… ils ne remplissent pas N ! Claude Lobry (à la bib)
  • Le théorème de Gödel, point sciences, Ernest Nagel/James R. Newman, Kurt Gödel/Jean-Yves Girard
  • Gödel, Escher, Bach – Les brins d’une guirlande éternelle: Les brins d’une guirlande éternelle, Douglas Hofstadter (disponible en français et en anglais à la bibliothèque)

Thèse


présentée devant l’UNIVERSITÉ CLAUDE BERNARD – LYON I
pour obtenir le titre de DOCTEURE EN SCIENCES
dans la spécialité MATHÉMATIQUES
par
Natacha PORTIER

Complexité algébrique
Stabilité polynomiale des corps différentiels
&
Résolutions universelles pour des problèmes NP-complets

soutenue le mercredi 9 décembre 1998

Jury :

Vincent BLONDEL
chargé de cours à l’Université de Liège, examinateur
Fokko du CLOUX
professeur à l’Université Claude Bernard de Lyon, examinateur
Françoise DELON
directrice de recherches au CNRS à Paris VII, présidente du jury
Christian MICHAUX
chef de travaux à l’Université de Mons, rapporteur
Bruno POIZAT
professeur à l’Université Claude Bernard de Lyon, directeur de thèse

Rapporteurs :

Felipe CUCKER, professeur à l’Universitat Pompeu Fabra de Barcelone,
Christian MICHAUX, chef de travaux à l’Université de Mons.

Résumé :

La première partie est consacrée à l’étude de la complexité algébrique des corps différentiels de caractéristique nulle. Nous pouvons définir les classes P et NP sur un corps différentiel K (cf le livre « Les petits cailloux » de Bruno Poizat) . En utilisant le théorème des témoins de L. Blum, M. Shub et S. Smale, nous montrons la P-stabilité de la théorie des corps différentiels de caractéristique nulle : la restriction d’un problème P sur un corps différentiel K à un sous corps k de K est encore P. Nous en déduisons que la question P=NP? a la même réponse dans tous les corps différentiellement clos de caractéristique nulle. Nous montrons ensuite que la dérivée ne nous permet pas de calculer plus vite les grandes racines et les grandes puissances d’un élément.
La deuxième partie est une généralisation de l’article de Manindra Agrawal et Somenath Biswas : « Universal Relations ». Les auteurs définissent pour le cas des calculs au sens ordinaire, une notion plus forte que la NP-complétude. Par définition, à chaque problème NP-complet X est associé un problème Y, que nous appelons résolution associée à X, qui est P, et tel que x soit dans X si et seulement s’il existe y, de longueur polynomiale en elle de x, tel que (x,y) soit dans Y. Un tel y est appelé solution de x pour X. Si toute résolution R se réduit à Y, de manière à ce que les solutions pour R se déduisent des solutions pour Y, Y sera appelée résolution universelle. Les auteurs montrent ensuite un théorème qui permet de prouver qu’une résolution est universelle. Nous généralisons cette définition et ce théorème aux calculs effectués dans une structure arbitraire, en particulier aux calculs sur les réels définis dans l’article « On a theory of computation and complexity over the real numbers : NP-completeness, recursive functions and universal machines » de L. Blum, M. Shub et S. Smale, puis nous étudions des exemples.