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

Lundi 16 octobre 2006 : Ôzlem Beyarslan (Paris 7) Pseudofinite Fields and Random Hypergraphs and Tournaments

A pseudofinite field is an infinite model of the theory of all finite fields. We will state two results on pseudofinite fields of two different flavors.
In 1980 Duret proved that the theory of pseudofinite fields is not stable by interpreting a random binary graph in any model by the formula

Lundi 23 octobre : J. Lopez-Abad (Paris 7) Suites inconditionnelles dénombrables et non dénombrables

Nous allons présenter plusieurs constructions d'espaces de Banach, en particulier un exemple récent d'un espace de Banach avec " beaucoup " de suites inconditionnelles dénombrables mais sans aucune non-dénombrable. Ces espaces ont la propriété commune d'être définis par une norme implicite à la Tsirelson.

Lundi 30 octobre : D. Bonnay (Département d'Etudes Cognitives, ENS Ulm / IHPST) Invariance, définissabilité et monoïdes

Je présenterai une généralisation d'un résultat de Marc Krasner sur la définissabilité en logique infinitaire et les groupes d'automorphismes. Krasner a montré qu'étant donné un ensemble M, il existe une correspondance bijective entre les ensembles d'opérations sur M clos par definissabilité dans L_∞,∞ et les groupes de permutation sur M. Indépendamment, Solomon Feferman a pose récemment la question de savoir dans quel langage étaient définissables les opérations invariantes par homomorphisme (nous préciserons de quel genre d'homomorphismes il est question). Je montrerai qu'il est possible de répondre à la question de Feferman en généralisant simplement le résultat de Krasner pour obtenir une correspondance entre ensembles d'opérations clos par définissabilité dans L_∞,∞ sans l'égalité et monoïdes d'homomorphismes.

Lundi 13 novembre : Jean-Pierre Ressayre (Paris 7) Arithmetization of the field of reals with exponentiation (S. Boughattas, J-P. Ressayre)

1. Shepherdson proved that a semi-ring A satisfies IE_0 (induction scheme restricted to open formulas) iff it is integral part of a real closed field; and Berarducci asked about extensions of this criterion when exponentiation is added to the language of rings and fields. Let T range over axiom systems for ordered fields with exponentiation; for three values of T we provide a theory in the language of rings plus exponentiation such that the models (A,exp_A) of are all integral parts A of models M of T with A^+ closed under exp_M and exp_A=exp_M restricted to A^+. Namely T=EXP, the basic axioms of real exponential fields; T=EXP+ the Rolle and the intermediate value properties for all 2^x-polynomials; and T=T_{exp}, the complete theory of the field of reals with exponentiation.
2. is recursively axiomatizable iff T_{exp} is decidable. implies LE_0(x^y) (least element principle for open formulas in the language <,+,\times,-1,x^y) but the reciprocal is an open question. satisfies provable polytime witnessing: if it proves $\forall x\exists y:|y|<|x|^k)R(x,y) (where R is an NP relation, k
3. We introduce ``blunt'' axioms for Arithmetics : axioms which do as if every real number was a fraction (or even a dyadic number). The falsity of such a contention in the standard model of the integers does not mean inconsistency; and bluntness has both a heuristic interest and a simplifying effect on many questions - in particular we prove that the blunt version of is a conservative extension of for sentences which are universal quantifications of bounded formulas of the language of rings plus x^y ). Blunt Arithmetics - which can be extended to a much richer language - could become a useful tool in the non standard approach to discrete geometry, to modelization and to approximate computation with reals.

Lundi 20 novembre : Eric Jaligot (Lyon I) Les aventures de generix

Un sous-groupe définissable d'un groupe de rang de Morley fini est dit généreux si la réunion de ses conjugués est générique dans le groupe ambiant. Un sous-groupe définissable et connexe est un sous-groupe de Carter s'il est nilpotent et d'indice fini dans son normalisateur. Je donnerai une description des sous-groupes de Carter généreux, avec notamment un théorème de conjugaison. Tout les arguments employés sont faits avec une grande économie de théorie des groupes, et généralement basés uniquement sur la généricité.

Mardi 21 novembre, dans le cadre du séminaire de Théorie des ensembles, en 4C17 : Ward Henson (Urbana-Champaign) Continuous logic and the model theory of metric structures

Continuous logic is a [0,1]-valued version of the usual first-order logic. Its propositional fragment corresponds to the logic of Lukasiewicz, which was introduced in about 1930. With quantifiers corresponding to the operations of sup and inf on the interval [0,1], this logic was studied in the 1950s and 1960s, and then dropped. Recently it has re-emerged as the appropriate logic for the model theory of metric structures. Its theoretical features have developed rapidly in the last few years, and its applications are being actively pursued. This talk will emphasize (a) the basic model-theoretic features of continuous logic as presented in [1] [2]; (b) its connections to the ultraproduct construction that is widely used in functional analysis, geometric group theory, etc; and (c) some indications of the new application areas that are currently being investigated.

Lundi 4 décembre : J. Nesetril (Charles University, Prague) The mysterious homomorphism order

I will collect and survey some evidence of very nice and profound properties of the homomorphism order of finite (and countable) structures.

Lundi 11 décembre : Florent Madelaine (Université de Durham) Complexité et complexité descriptive des problèmes de satisfaction de contraintes

Les problèmes de satisfaction de contraintes sont maintenant étudiés par une communauté théorique qui regroupe des personnes d'horizon assez varié. En effet, ces problèmes peuvent être approchés par des outils algébriques, des outils logiques et des outils combinatoires. La richesse des approches s'explique peut-être par l'ubiquité de ces problèmes : on les retrouve sous différents noms et formes un peu partout, par exemple en bases de données (problème de jointure, inclusion de requêtes existentielles conjonctives), en théorie des graphes (coloriage de graphes) et en "logique" (problème Sat). L'un des problème important est de classifier ces problèmes par leur complexité et en particulier, d'établir la véracité de la conjecture de la dichotomie, à savoir que tout problème de contraintes est soit facile (dans P) soit difficile (NP-complet). Une autre question intéressante est de donner une caractérisation logique de ces problèmes.
Dans l'exposé, je vais donner une introduction aux problèmes de satisfaction de contraintes et présenter des résultats autour de ces deux questions.

Jeudi 14 décembre à 14 h, Salle 1C1 : Anand Pillay (Leeds) Groups, measures, and the NIP II

In earlier joint work with Hrushovski and Peterzil we proved, among other things, the EXISTENCE of left invariant "Keisler" measures on definable groups G, assuming that the ambient theory T has the NIP (not the independence property) and G has fsg (finitely satisfiable generics). Here (joint with Hrushovski) we extend these results to obtain the UNIQUENESS of such invariant measures (an analogue of the uniqueness of invariant TYPES for connected stable groups).
I may also discuss recent work (with Ealy and Krupinski) on the structure of groups of "small rank", assuming fsg and NIP.

We will discuss the current status of the classification problem for simple groups of finite Morley rank, with a focus on current information regarding even order automorphisms of simple groups, and the necessity of such information.

Lundi 29 janvier : Thomas Blossier (Lyon I) Groupes fortement minimaux et finie-axiomatisation

L'existence d'une théorie aleph_1-catégorique finiment axiomatisée ayant une géométrie non triviale est une question ouverte. En 1994, Hrushovski a montré qu'une telle théorie aurait une géométrie localement modulaire, c.à.d. la géométrie des espaces vectoriels sur le corps gauche K de ses quasi-endomorphismes. Il a alors conjecturé que K serait un anneau de présentation finie. Je présenterai un travail commun avec Elisabeth Bouscaren où l'on montre que cette conjecture est vérifiée pour les expansions de groupes qui sont fortement minimales et finiment axiomatisables.

Lundi 5 février : Antonio Aviles Lopez (Paris 7) Sous-espaces annulés par des polynômes dans les espaces

On expose un exemple de polynôme homogène défini sur un espace de Banach complexe non-séparable dont tous les sous-espaces de racines sont séparables.

Lundi 12 février : Abderezak Ould Houcine (Lyon I) Groupes de rang sans-quantificateurs fini

Dans l'étude des sous-groupes des groupes de rang de Morley fini, on est amené à considérer une notion de rang 'faible' réduit aux formules sans-quantificateurs. Je présentrais des résultats qui généralisent (en utilisant des méthodes différentes) des résultats connus dans le cadre des groupes de rang de Morley fini et des groupes linéaires aux groupes ayant un rang sans-quantificateurs fini. Je terminerai par quelques propriétés des limites de Fraïssé de classes des groupes de type fini closes par certaines opérations.

Lundi 19 février : Olivier Le Gal (Rennes I) Modèle complétude des structures o-minimales

En '68, A. Gabrielov montre un théorème du complémentaire pour les sous-analytiques globaux, qui, repris en '88 par L. van den Dries et J. Denef, implique la modèle complétude -- et la o-minimalité -- de la structure Ran. En '96, Gabrielov donne une version explicite de son théorème. On présente une généralisation de ce résultat pour les structures o-minimales polynomialement bornées, équivalente à la modèle complétude de la structure (R,+,*,F) si F est une quasi-algèbre différentielle de fonctions lisses définissables dans une structure o-minimale polynomialement bornée.

Lundi 26 février : Adrien Deloro (Paris 7) Groupes de rang de Morley fini : une chasse aux monstres

La conjecture de Cherlin-Zilber affirme que tout groupe simple infini de rang de Morley fini est isomorphe à un groupe algébrique sur un corps algébriquement clos. Certaines pathologies restent possibles ; l'exposé portera sur la limitation/description de tels "monstres" dans le cas des petits groupes de type impair. Plus précisément, il s'agit de la réécriture, grâce à la 0-unipotence, d'un résultat de Cherlin et Jaligot qui supposait l'ordinarité du groupe.

Lundi 5 mars : Marcin Petrykowski (Lyon I) Countable coverings of groups

The following theorem has been proved in [1].

Theorem 1 (Newelski) If an $\aleph_0$-saturated group G is the union of countably many 0-type-definable sets, then finitely many of them generate G in 3 steps. (a subset A of G generates G in 3 steps if $G=(A\cupA^{-1})3$)

It turned out that for many groups 2 steps are always sufficient (i.e. for each covering of a group by countably many 0-type-definable sets, finitely many of them generate the group in 2 steps). For instance, it is so in the case where a group is stable or abelian. A similar property of groups (to be defined during the talk) may be defined in a model-theory-free context. We denote it by K2 because it is related to generating a group in 2 steps. Our main result is as follows.

Theorem 2 (MP) AG\subseteq K2\subseteq NF. (here AG stands for the class of amenable groups and NF denotes the class of groups without a free subgroup of rank 2)

[1] Ludomir Newelski, Marcin Petrykowski, "Coverings of groups and types", Journal of the London Mathematical Society 71 (2005), 1-21.

Lundi 12 mars : Itaï Ben Yaacov (Lyon I) Superstabilité et les automorphismes des algèbres de probabilités

Un théorème de Chatzidakis et Pillay affirme que si T est une théorie superstable et T_A (la modèle compagne de T + automorphisme ) existe, alors elle est supersimple. Ceci n'est plus valable dans la logique continue (c.à.d., quand il s'agit d'une classe superstable de structures métriques).
En effet, si T est la théorie des algèbres de probabilités sans atomes alors est \aleph_0 -stable et d'après Berenstein et Henson T_A existe et est stable. Or, on peut démontrer que T_A n'est pas superstable, et donc ne peut être supersimple. Par contre, d'après un travail commun avec Berenstein, T_A est \aleph_0 -stable à perturbation près de l'automorphisme. Cela mène à la conjecture que T_A est toujours supersimple à perturbation près de l'automorphisme, ainsi qu'à l'étude des propriétés des théories \aleph_0 -stable à perturbation près.

Lundi 19 mars : Salma Kuhlmann (Université du Saskatchewan) Truncation closed embeddings of valued fields in fields of generalized power series. (Joint work with Antongiulio Fornasiero and Franz-Viktor Kuhlmann).

An integer part (IP for short) Z of an ordered field K is a discretely ordered subring, with $1$ as the least positive element, and such that for every element x of K, there is an element z of Z such that x is between z and z+1.
Mourgues and Ressayre establish the existence of an IP for any real closed field K by showing that there is an order preserving embedding of K into an appropriate field of generalized power series, such that the image of the embedding is a truncation closed subfield. An IP of K obtained in this way (i.e. from a truncation closed embedding) is called a truncation integer part of K.
In this talk, we analyze IPs from a valuation theoretic viewpoint and summarize their main special features. We investigate their connection to special (additive) complements of valuation rings of ordered fields. This approach reveals new interesting valuation theoretic properties of valued fields; depending on whether such special complements exist. We discuss these properties and their implications, thereby giving an intrinsic valuation theoretic interpretation of truncation closed embeddings in fields of power series.

Lundi 26 mars : Guillaume Malod (Université de Mons) Calculs avec deux opérations

Valiant a défini des classes de complexité pour les suites de polynômes définies à partir des circuits calculant sur un corps. On peut voir les circuits comme un modèle général pour étudier les calculs avec deux opérations. Il est alors intéressant de trouver les hypothèses les plus faibles sur ces opérations permettant de prouver chaque résultat. Nous illustrerons aussi comment cette vision simple des calculs permet de simplifier les preuves.

Lundi 2 avril : Luis Pereira (Paris 7) Arithmétique Cardinale et la Conjecture PCF

On verra comment la théorie PCF de Saharon Shelah est appliquée à l'arithmétique des cardinaux infinis et en particulier quelles sont les conséquences de la conjecture PCF de Shelah dans l'arithmétique cardinale. Après on analysera une approche possible de la conjecture PCF qui fait intervenir des sous-ensembles libres dans des algèbres.

Lundi 23 avril : Richard Lassaigne (Paris 7) Vérification probabiliste et approximation

Cet exposé présente un état de l'art de résultats récents concernant deux types d'approximation qui peuvent être utiles dans le contexte de la vérification pour réduire la complexité en temps et en espace. Dans le premier cas, on introduit une notion d'approximation sur les données, c'est-à-dire sur le modèle à vérifier, définie à l'aide d'une distance. Il est alors possible de concevoir des algorithmes probabilistes permettant de décider, en temps indépendant de la taille du modèle, si la propriété considérée est satisfaite ou si elle est loin, à epsilon près au sens de la distance, de l'être. Dans le second cas, on définit une méthode d'approximation pour la vérification de propriétés quantitatives sur des systèmes probabilistes. Les algorithmes probabilistes d'approximation ainsi obtenus permettent de réduire de manière exponentielle la complexité en espace. Ces algorithmes ont ete implémentés de maniere distribuée dans un model checker probabiliste qui s'est révélé très efficace.

Lundi 30 avril : Thomas Ehrhard (Paris 7) Réseaux d'interaction différentiels: une approche logique du calcul concurrent.

La logique linéaire est un raffinement de la logique intuitionniste qui rend compte de la notion de ressource en donnant un statut logique aux règles structurelles (des connecteurs logiques unaires, les exponentielles, leur sont associés). Une preuve est linéaire si elle utilise ses hypothèses exactement une fois. On verra qu'il est possible de construire des modèles "dénotationnels" de cette logique où cette notion de linéarité coïncide avec la notion usuelle, et que, dans ces modèles, les morphismes peuvent être dérivés. On donnera un statut logique à cette notion de différentiation, et on verra qu'elle permet de modéliser le calcul parallèle et concurrent, tel qu'il a été formalisé dans le pi-calcul (Robin Milner).

Lundi 21 mai : Olivier Frécon (Université de Poitiers) Groupes géométriques de rang de Morley fini.

Les groupes géométriques de rang de Morley fini sont des groupes de rang de Morley fini possédant des propriétés géométriques très rudimentaires, et rencontrées dans de nombreux groupes de rang de Morley fini. Plus précisément, un groupe de rang de Morley fini est dit géométrique si, pour tout couple (x,y) d'éléments de G avec x≠ y, il y a une famille uniformément définissable \mathscr{F}_{x,y}={F_i | i in I } de sous-groupes connexes de G, où I est un ensemble interprétable, vérifiant :
- il y a un sous-ensemble générique U de G × G tel que, pour tout (u,v) in U, il y a un unique F in \mathscr{F}_{x,y} tel que uF=vF;
- il n'y a aucun F in \mathscr{F}_{x,y} tel que xF=yF.

On discutera les liens entre cette notion et celle de groupes de rang de Morley fini définissablement linéaires, qui sont les groupes admettant une représentation linéaire fidèle interprétable sur un anneau de la forme K_1\oplus .... \oplus K_n où K_1,...,K_n sont des corps interprétables. La question centrale étant "est-ce que tout groupe géométrique de rang de Morley fini est définissablement linéaire ?"

Lundi 28 mai : Ali Enayat (Utrecht University) Automorphisms of models of arithmetic

We discuss a recently developed method of constructing automorphisms of models of arithmetic that provides a unified approach to building desirable automorphisms of models of a variety of arithmetical theories (ranging from bounded arithmetic to second order arithmetic). As we shall see, this new method not only leads to refinements of many classical results, but it can also be used to establish a long standing conjecture of Schmerl by showing that the isomorphism types of fixed point sets of countable arithmetically saturated models of M of Peano arithmetic are precisely the isomorphism types of elementary submodels of M.

Françoise Point (Université de Mons-Hainaut) Corps valués de différence vus comme modules valués

C'est un travail en collaboration avec Luc Bélair. Nous considérons les corps valués munis d'une isométrie, comme modules sur l'anneau de Ore des polynomes de Frobenius, dans le cas soit d'égale caractéristique, soit de caractéristique (0,p). Sous certaines hypothèses, nous prouvons un résultat d'élimination des quantificateurs tout d'abord dans le pur language des modules, ensuite dans ce language enrichi par une chaîne de sous-groupes additifs et enfin dans un langage à deux sortes avec une application de valuation. Nous appliquons ce dernier résultat pour montrer que ces structures n'ont pas la propriété d'indépendance.

Immanuel Halupczok (E.N.S. Ulm) Comprendre les ensembles définissables de corps pseudo-finis et similaires

Soit T la théorie des corps pseudo-finis de caractéristique 0. Une méthode pour comprendre ses ensembles définissables Def(T) est de définir des invariants, c.à.d. des fonctions sur Def(T) invariantes sous bijections définissables. Denef-Loeser ont donné un tel invariant très fort: à chaque ensemble définissable X, ils associent un motif virtuel μ(X). Nous allons généraliser cet invariant à d'autres corps similaires. Plus précisément, soit G un groupe pro-cyclique et soit T_G la théorie des corps pseudo-algébriquement clos de caractéristique 0, avec groupe de Galois G. (Pour G = \hat{Z}, T_G = T.) C'est à ces théories qu'on va généraliser l'application μ de Denef-Loeser. L'idée est la suivante. Pour deux groupes G \subset G' comme en haut, on va définir une application θ: Def(T_G) -> Def(T_G'). Si on choisit G' = \hat{Z}, la composition μ θ sera l'invariant voulu. Mais on peut faire encore plus avec les applications θ : en identifiant G à un de ses sous-groupe propres, on obtient une application de Def(T_G) vers lui-même qui permet, dans certains cas, d'obtenir encore plus d'information sur les ensembles définissables que ce qu'on obtient en utilisant seulement l'invariant μ de Denef-Loeser. En particulier, on démontre que μ n'est pas injectif. Il ne sera pas nécessaire d'avoir déjà entendu le mot "motif" pour comprendre l'exposé.

Lundi 18 juin : Zoé Chatzidakis (CNRS - Paris 7) : Application des corps de différence à un théorème de Baker.

(Travail en commun avec E. Hrushovski) Soient k un corps algébriquement clos, et K un corps de fonctions sur k (par exemple K=k(t)). Soit f: P¹ --> P¹ un morphisme définie sur K et de degré d>1. A ces données on peut associer une "hauteur" h, définie sur P¹(K), et satisfaisant h(f(P))=d h(P) pour tout point P de P¹(K). Matthew Baker montre le résultat suivant :

Théorème. Si (P¹,f) n'est pas isomorphe à (P¹,f') avec f' définie sur k, alors il existe r>0 tel que les points de hauteur < r sont en nombre fini.

En utilisant les propriétés des hauteurs et la compacité, on montre facilement que si la conclusion du théorème est fausse, alors il existe n, une variété V et une fonction rationnelle dominante g:V --> V définies sur k, et telles que (V,g) domine (P¹,f^n) (ce qui veut dire : il existe une fonction rationnelle dominante h: V --> P¹, définie sur K, et telle que f^nh=hg). Le résultat que nous montrons, et qui permet d'obtenir le résultat de Baker après quelques manipulations algébriques simples est le suivant :

Théorème. Soient k et K des corps algébriquement clos, K contenant k. Soient V et W des variétés, f: V --> V et g: W --> W des fonctions rationnelles dominantes, telles que (V,f) est définie sur K et (W,g) sur k. Si (W,g) domine (V,f), alors il existe (V',f') définie sur k, de dimension positive, telle que (V,f) domine (V',f').

Je discuterai (brièvement) des ingrédients de la preuve : la dichotomie dans les corps de différence existentiellement clos et ses conséquences ; l'existence de fibrations des variétés de différence, les fibres ayant de bonnes propriétés ; la définissabilité de certains groupes d'automorphismes ; et enfin la correspondance de Galois associée.

Le 25 juin : Pas de séance (Journées Max Dickmann)

Mardi 3 juillet à 14h30 en salle 0D9 : Thomas Scanlon (Berkeley/Orsay) fera un exposé dans le cadre du séminaire DDG et du GdT Différentiel, Difference equations and the André-Oort conjecture.

Page maintenue par Z. Chatzidakis