UNIVERSITE DE PARIS VII, UFR DE MATHEMATIQUES
  Séminaire général de Logique - Année 2002 - 2003

Lundi 7 octobre : Pascal MICHEL (Versailles), PRIMES est dans P

Les classes de complexité P et NP ont été définies au début des années 1970. Puis on a essayé de déterminer, parmi les problèmes dans NP, lesquels étaient dans P et lesquels étaient NP-complets. Parmi les problèmes qui ont résisté à cet effort se trouvait le problème PRIMES : déterminer si un nombre entier est ou n'est pas premier. Agrawal, Kayal et Saxena ont démontré récemment que ce problème est dans P : il existe un algorithme déterministe en temps polynomial ($O(n^{12})$) qui détermine si un nombre entier est ou n'est pas premier. Cet exposé donnera une idée de la démonstration.

Dans ce séminaire, je débuterai par une description des ordres colorés omega-catégoriques. Par la suite, et étant donnée la théorie T d'un ordre coloré omega-catégorique, je parlerai de l'existence d'une modèle compagne de T + (f est un automorphisme) si on rajoute un nombre fini de relations d'équivalences dans le langage. Je discuterai aussi de l'élimination des imaginaires de T et de celle de la modèle compagne de T + (f est un automorphisme).

Lundi 21 octobre : Olivier FINKEL (Paris 7), Une extension effective de la hiérarchie de Wagner aux automates à un compteur

Les oméga langages rationnels sont les langages de mots infinis, sur un alphabet fini, qui sont acceptés par automates finis déterministes avec condition d'acceptation de Muller. D'autres machines finies, plus complexes, comme les automates à pile, les réseaux de Petri, ou les machines de Turing ont été considérées pour la lecture des mots infinis.

L'ensemble des mots infinis sur un alphabet fini \Sigma étant muni de la topologie usuelle de Cantor, les oméga langages rationnels, ainsi que tous les oméga langages acceptés par machines finies déterministes, sont des combinaisons booléennes d'ensembles Boréliens \Pi_2^0, donc de rang de Borel au plus 3.

La hiérarchie de Wadge, qui raffine la hiérarchie Borélienne classe les oméga langages en fonction de leur complexité topologique, à l'aide de la notion de réduction par des fonctions continues. Cette hiérarchie, à la difference de la hiérarchie Borélienne, permet de distinguer les différentes machines finies déterministes lisant des mots infinis.

La hiérarchie de Wadge des oméga langages rationnels est la hiérarchie de Wagner. Celle ci est effective, et les réductions sont données par des transducteurs effectivement calculables.

On étudiera dans cet exposé une extension de la hiérarchie de Wagner aux oméga langages acceptés par automates déterministes équipés d'un compteur. La hiérarchie est obtenue en étendant les notions de chaîne et de superchaîne aux automates à compteur. On obtient alors une extension effective de la hiérarchie de Wagner, dont les reductions sont données par des transducteurs à compteur.

Ce résultat permet aussi de construire des stratégies gagnantes effectives dans certains jeux de Wadge et de Gale-stewart.

Nous ferons, dans cet exposé, un petit tour d'horizon de quelques systemes logiciels d'aide à la construction et à la vérification de preuves formelles. Nous nous limiterons au domaine des logiciels plus ou moins explicitement orientés vers la certification de programmes informatiques. L'accent sera mis sur les choix de conception de tels systèmes en rapport avec les systèmes de formalisations implantés.

J'exposerai les résultats (axiomes, E.Q.) et quelques questions de base de la théorie des modèles des vecteurs de Witt et de leur automorphisme de Frobénius.

La Logique Linéaire (LL) a été introduite comme un raffinement de la Logique Intuitionniste (LJ) basé sur la décomposition de l'implication. Ceci a mis en avant l'importance des règles structurelles et des contraintes de linéarité dans l'étude des preuves. Dans le même esprit, LL a également permis d'analyser le non déterminisme de l'élimination des coupures en Logique Classique (LK), lié à la complète liberté des règles structurelles. Nous verrons comment la polarisation, issue de l'étude de LL, permet une interprétation plus directe de LK, ce qui complète les travaux précédents en précisant la position de LL par rapport à LK et LJ. En particulier, l'utilisation de différentes variantes polarisées de LL fournit un équivalent des traductions de LK dans LJ dans un cadre linéaire.

Van den Dries, Macintyre et Marker ont démontré un résultat d'élimination des quantificateurs pour le corps des réels étendu par l'exponentielle et les fonctions analytiques restreintes. Leur preuve utilise un critère classique de théorie des modèles. Nous donnons une version géométrique de ce résultat, en montrant comment les arguments de valuation employés constituent une extension de la méthode classique du polygône de Newton. Cette "traduction" résulte d'une mise sous-forme réduite des équations log-exp-analytiques, dite "théorème de préparation".

Il y a 40 ans Bialynicki-Birula et Rosenlicht ont montré que toute application polynomiale injective de Rⁿ dans Rⁿ est surjective. Ensuite J. Ax (1969) a généralisé ce résultat aux applications injectives et régulieres f:X-->X, lorsque X est un ensemble algébrique (sur un corps alg. clos) possiblement avec singularités. Par des arguments de théorie des modèles il a réussi à réduire l'énoncé au cas où X est fini. Dans le cas réel A. Borel (1969) a montré le résultat dans le cas ou X est nonsingulière. Le cas réel X avec singularités a été résolu par moi seulement en 1999. L'argument principal est une décomposition finie d'un ensemble algébrique réel en composantes symétriques par arcs qui est plus proche du cas algébriquement clos. Y a-t-il des points communs dans toutes ces preuves?

Après avoir rappelé les premières propriétés de la théorie des corps différentiellement clos de caractéristique 0 (CDC₀), on définira certains des rangs naturels pour cette théorie. On s'intéressera alors aux différentes notions de "types génériques" induites par ces rangs, et plus particulièrement pour les groupes définissables dans la théorie CDC₀.

La correspondance preuves-programmes (dite de Curry-Howard) fournit une méthode objective pour savoir si un axiome est, ou non, "intuitif" (indépendamment du problème de sa consistance relative): il s'agit de lui associer une "instruction", au sens informatique du terme. Problème résolu depuis longtemps pour les axiomes de la logique du second ordre intuitionniste, beaucoup plus récemment pour le tiers exclu, puis les axiomes de ZF. Problème ouvert pour l'axiome du choix, mais résolu pour l'axiome du choix dépendant. L'instruction associée n'est autre que l'horloge du système informatique.

Un théorème de Zilber, qui s'appuie sur un résultat de Henry B. Mann, Mathematica, 1965, p. 107-117, affirme que la structure formée du corps des nombres complexes avec en plus un prédicat U notant les racines de l'unité est superstable, et même oméga-stable, de rang oméga, le groupe U étant un pur module de rang un ; il en est de même si on prend pour U un sous-groupe divisible quelconque de racines de l'unité. La situation n'est pas aussi simple en caractéristique p non nulle, mais je donnerai des exemples où la même situation se produit ; certains dépendent de conjectures arithmétiques sur les nombres premiers. L'étude de ces corps de caractéristique p est motivée par le résultat de Wagner assurant qu'il est très peu probable qu'il existe des "mauvais corps" de rang de Morley fini - soit encore aleph-un catégoriques - et de caractéristique non nulle.

Après une présentation des divers monoïdes pseudo-simplifiables en question (séparatifs et fortement séparatifs), on donne des résultats algébriques de décomposition. On en déduit la décidabilité des théories universelles des diverses classes de monoïdes concernées. Par ailleurs, on évoquera la notion de monoïde de raffinement et de groupe d'interpolation, pour lesquels la question de la décidabilité de leur théorie universelle reste ouverte.

It is not known whether there exists a pair of functions \alpha : n^{\omega} --> m^{\omega} and \beta: [\omega]^{\omega} --> [\omega]^{\omega}, where n>m>1, such that for every x in n^{\omega} and a in [\omega]^{\omega}, if \alpha (x) is almost constant on a, then so is x on \beta (a). Such a pair would provide a proof of the well-known result that the so-called refinement numbers r_n, r_m are equal, that is interesting also under CH (in which case r_n=r_m is trivial). I shall show that such a pair exists under Martin's axiom, and that no Borel pair exists.

Dans un corps K de caractéristique p positive, l'ensemble K^p des éléments qui sont des puissances p-ièmes forme un sous-corps de K. Nous considérons le cas où il existe b₁,...,b_\nu dans K vérifiant K=K^p[b₁,...,b_\nu] et, pour chaque i dans {1,\dots,\nu}, b_i n'appartient pas à K^p[b__j, j dans {1,\dots,\nu}, j différent de i], \nu est alors appelé le degré d'imperfection de K. Soit, pour chaque entier n, (m_i)_{{i dans p^n\nu}} l'ensemble des monômes en b₁,\dots,b_\nu de degré < pⁿ en chaque b_i. Si l'on considère un surcorps L de K vérifiant également L=L^p[b₁,...,b_\nu] et b_i n'appartient pas à L^p[b_j, j dans {1,\dots,\nu}, j différent de i], chaque élément de L s'écrit de façon unique

La fonction de Kolchin, f : N ---> N, associée à x et K est définie ainsi : f(n) est le degré de transcendance de {x_i, i dans p^n\nu} sur K.

Nous utilisons cet outil pour étudier la stabilité des corps séparablement clos de degré d'imperfection \nu.

La définition d'indépendance liée au rang de Morley ne marche pas pour une théorie non-omega-stable comme la théorie d'un corps algébriquement clos valué. Mais on peut définir des notions d'indépendance qui sont équivalentes à l'indépendance classique pour un corps algébriquement clos pur, et qui se généralisent au cas d'un corps muni d'une valuation. Dans cet exposé, je vais présenter plusieurs exemples où on verra que les notions d'indépendance considérées peuvent être différentes et on donnera un critère pour qu'elles coïncident.

Un point qui est devenu une banalité est que, en un certain sens, le théorème de complétude (conséquence de ZFC) garantit que tous les modèles bien fondés d'un seul axiome donne des modèles à tous les axiomes qui en ont, et que tous les modèles pleins d'un seul axiome donne des modèles bien fondés à tous les axiomes qui en ont. Et ça semble s'arrêter la : on ne sait pas dire 'tous les modèles bidule-chouette d'un seul axiome donnent des modèles pleins à tous les axiomes qui en ont'.

Il s'agira essentiellement de regarder quelques axiomes ou schémas d'axiomes, très banals, qui sont habituellement évacués d'un revers de la main comme faux par la théorie ambiante des ensembles.

Ces axiomes sont des sortes de 'portes' de 'l'univers', pour certains, garantissant aux habitants de l'univers que ce dernier est trop petit (non plein), ou 'achevé' (il ne rate rien) ou etc. Un côté qui peut etre intéressant est leur quasi-minimalité : s'il y a des bornes (de quelque nature) ces énoncés sont vrais.

Ceux qui offrent un 'achèvement' vont violemment contre les schémas de réflexion habituels communément acceptés comme 'vrais in the real world'.

d'une manière générale, se pose la question de garantir 'qu'on a tout mis' qui soit possible dans l'univers. Et une remarque apportée par ce qui précède est que, oui, en certains sens, il y a des axiomes qui permettent de garantir ça (contrairement à une vague idée que non, véhiculée par la théorie ambiante des ensembles, et les divers schémas de réflexion et de grands cardinaux, qui sont pourtant consistants avec les 'portes')

Par ailleurs, on mentionnera aussi des axiomes extrêmement naturels (FST pour full set theory), enrichissant ZFC et exprimant 'in some sense' que V contient au moins un certain nombre d'objets qu'il ne 'devrait pas' rater. Et pourtant, ces axiomes posent problème, en ce sens, que le principe qui les inspire conduit à d'autres axiomes qui, eux, sont faux, ou contredisent certains axiomes de grands cardinaux. Corollairement, on remarquera l'aspect 'catalyseur' des principes FST, phénomène qui ne semble pas connu, ou se produire, pour des théories plus faibles genre peano.

Soit (P,\leq) un ordre partiel. On définit l'algèbre de Boole libre sur P, notée F(P). Soit { x_p : p dans P } l'ensemble des générateurs de l'algèbre de Boole libre Free(P) sur P. Soit J l'idéal de Free(P) engendré par { x_p - x_q : p \leq q }. Alors F(P) := Free(P)/J.
Lorsque P est un ordre total, F(P) est appelé l'algèbre d'intervalles sur P. Dans ce cas x_p = [p,\infty).
Si la classe des algèbres d'intervalles est bien connue, il n'en est pas de même de celle des algèbres d'ordres. Nous développerons quelques proprietés de cette dernière classe. Les techniques utilisées sont celles des ordres partiels, des wqo (ensembles bien fondés sans antichaines infinies), des treillis, ...

Les travaux récents de Woodin ont considérablement renouvelé la théorie des ensembles en lui apportant une intelligibilité globale et en restaurant son unité. Pour la première fois, ces résultats ouvrent une perspective réaliste de résoudre le problème du continu, et, à tout le moins, ils établissent le caractère irréfutablement signifiant et précis de celui-ci.

La question considérée est de savoir si tout idéal vérifiant une certaine propriété combinatoire (par exemple "être un P-point faible") peut être inclus dans un "gros" idéal avec la même propriété. Un idéal maximal sera bien sur considéré comme gros, mais on peut faire intervenir d'autres critères, par exemple d'ordre topologique.

This is joint work with Shelah. We define infinitary languages which satisfy the Craig Interpolation Theorem and have a Lindström type model-theoretic characterization. This is in sharp contrast to the general failure of such results for the known infinitary languages.