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

Le 13 octobre : Frank WAGNER (Lyon I - IHES) La configuration de groupe pour les théories 2-simples (d'après Kim)

Je rapporterai sur une construction de de Piro, Kim et Young qui, dans une théorie 2-simple, obtiennent un groupe hyperdéfinissable à partir d'une configuration de groupe algébrique.

Gabrielov a montré la modèle complétude (ou élimination d'un quantificateur, ou théorème du complément) du corps des réels enrichi par un ensemble E de fonctions analytiques restreintes qui est clos par dérivation partielle. L'exposé donne une preuve qui s'applique aussi lorsque E contient des fonctions Gevrey-analytiques restreintes. La méthode de preuve devrait avoir d'autres applications.

La question qui nous concernera est la suivante : Soit K un corps de nombres (c.à.d. une extension algébrique finie de Q) et soit O_K l'anneau d'entiers algébriques dans K. Existe-t-il un algorithme pour déterminer si une équation diophantienne quelconque a une solution dans O_K?

Si K=Q, il s'agit du dixième problème d'Hilbert classique (résolu par Matijasevich). Les travaux de Denef, Lipschitz, Pheidas et Shlapentokh montrent que la question a une réponse négative pour certaines classes d'anneaux d'entiers algébriques, mais la question générale reste encore ouverte.

Dans cet exposé on montrera que certaines conditions arithmétiques sur le corps K impliquent que Z est un sous-ensemble diophantien de O_K, ce qui implique une réponse négative à la question.

We show a sufficient condition guaranteeing that an elementary theory of a generic omega-stable structure in arbitrary relation language obtained by the Hrushovski's construction does not admit elimination of imaginaries.

Hausdorff a introduit les opérations lexicographiques sur la classe des chaines, étendant ainsi à cette classe l'arithmétique ordinale inventée par Cantor. Il étudia les propriétés propres à ces opérations, et s'intéressa particulièrement à utiliser ces méthodes pour construires des chaines n-transitives.
Plusieurs questions s'offrent naturellement, auxquelles nous avons pu apporter une réponse. La première partie de l'exposé consistera en un survol des résultats principaux de Hausdorff, tandis que la deuxièe partie exposera nos nouveaux résultats, et les idées principales utilisées dans les preuves.

Je démontrerai que dans une théorie 2-simple, la définissabilité "descend à la base canonique": Si a \in dcl(b,c) et c' = bc(ab/c), alors a \in dcl(bc'). Ceci était bien connu pour une théorie stable, et est faux en général dans une théorie simple. J'en déduirai l'existence d'un système fondamental pour un type p-interne, et le théorème de la configuration de groupe.

I shall present some results on groups of rational points of reductive algebraic groups over local fields and their definable subgroups in analogy with real algebraic groups.
I then try to show how one can consider the family of all local fields, in adelic framework, and try to apply the theory to arithemtic of varieties beyond abelian varieties, for example complex analytic or moduli varieties.

We show how the fields of real (and complex) numbers may be equipped with a derivative that respects exponentiation. In this way we deduce versions of Schanuel's Conjecture for suitably generic reals (and complexes) from Ax's version of SC for differential fields. As an application we show how the use of SC may be avoided in Zilber's proofs of the stability of expansions of the complex field by power functions.

In 1984, shortly after the foundations of the general theory of o-minimality were layed by Pillay and Steinhorn, the second author asked whether the "smallest" interesting o-minimal structure, namely the ordered additive group of rationals, could have a proper o-minimal expansion. This question was very much in the spirit of the model theory of the period and in this talk I shall survey some of the work that was, at least in part, motivated by it. Indeed, this work pretty well forces us to look for the required expansion using bounded analytic functions (on the real unit interval), which map rationals to rationals, and I shall conclude the talk by showing how such an approach can be made to work. The details of the argument, which will be given on Friday, are a modification of those given in my talk to this seminar on 18 February 1997.

Le 12 décembre à 10h, salle 7D1 : Alex WILKIE (University of Oxford) Fusing o-minimal structures

We exhibit a bijective analytic function f:R -> R which also maps the real algebraics bijectively onto the rationals and hence "fuses" the additive group of rationals onto the field of real algebraics. This function f is constructed as the real part of a limit of complex analytic functions, the limit being taken in a suitable Banach Space which we shall describe in detail. For reasons discussed in Tuesday's talk, the fused structure cannot be o-minimal, but a theorem of Gabrielov guarantees that it is when we restrict the field operations to the unit interval-thereby obtaining a positive answer to Steinhorn's question. The construction also shows that the two (additive) circle groups-the rationals (modulo 1) and the real algebraics (modulo 1) can coexist o-minimally on the same set.

Je discuterai de l'adaptation "correcte" de la superstabilité (et de la supersimplicité) aux structures métriques, et des analogues des types minimaux et réguliers dans ce contexte.

C'est un travail en commun avec Aleksander Kechris et Vladimir Pestov. Dans ce travail nous étudions certains liens entre la théorie de Fraïssé des classes avec amalgamation et les structures ultrahomogènes, la théorie de Ramsey, et la dynamique topologique des groupes d'automorphismes des structures dénombrables.

Lors d'un précédent séminaire, on avait mentionné des axiomes avec un statut un peu spécial en ce sens qu'ils annonçaient aux habitants de "(L?)'univers" V de ZFC qu'ils étaient "arrivés en haut", à quelques inaccessibles pres. On continue dans cette voie-la, d'essayer de classer les énoncés-bornés, et les désirs inassouvis que les habitants de V peuvent, en quelque sorte, reprocher au père noël (sans qu'il n'ait rien à répondre) de n'avoir pas satisfait dans V. En particulier, des remarques plutot simples seront présentées sous cet angle non-traditionnel, à propos du forcing. Par ailleurs, on remarquera aussi l'unicité absolue (même en dehors de V) des objets non-existants, mais désirables dans V (ce qui, classiquement en maths, les rend encore plus désirables).

La conjecture d'algébricité de Cherlin-Zilber énonce qu'un groupe simple de rang de Morley fini est un groupe algébrique sur un corps algébriquement clos. Cette conjecture, donc la classification des groupes simples de rang de Morley fini, est un problème ouvert auquel ont été appliquées des méthodes de la théorie des modèles et aussi de la théorie des groupes finis. Dans le cadre de la deuxième approche, des méthodes adaptées de la classification des groupes finis et simples se sont averées très efficaces. En particulier, la conjecture a été vérifiée pour les groupes simples de rang de Morley fini qui contiennent des 2-sous-groupes infinis d'exposant borné et qui satisfont à certaines hypothèses inductives (K^*-groupes). Des résultats obtenus depuis quelques années permettent d'espérer qu'on peut modifier cette approche inductive de façon à obtenir une preuve de la conjecture d'algébricité pour tous les groupes simples de rang de Morley fini ayant des 2-sous-groupes infinis d'exposant borné. J'essayerai d'éclairer les raisons de cet optimisme.

We will touch upon several interesting applications of the measure defined by Chatzidakis, Macintyre and van den Dries, like exponential sums, (fancy) Cebotarev, probabilistic Independence Theorem. Time permitting, we may mention the motivic side of the above.

Diverses constructions de modèles non-archimédiens de la théorie Th(R, exp) de l'exponentielle réelle ont été données dans les 10 dernières années. Dans cet exposé, nous en ferons d'abord un bref survol. Nous expliquerons ensuite une méthode basée sur la construction de certaines chaines lexicographiques. Les modèles ainsi obtenus sont des corps de séries formelles à support borné (par un cardinal infini régulier), et ont des propriétés singulières que nous discuterons. Nous apporterons ainsi une réponse à une question posée par D. Marker.

Abstract : We shall show that \Sigma is a consistent intuitisnictic theory and \Gamma is a set of formulas in n free variables which is intuitionistically consistent with and locally omitted by \Sigma, then there is a spectral space, Z, and a sheaf of structures over Z, A, such that

Nous présentons les classes de complexité algébriques de Valiant VP, VNP et VQP, définies à partir des circuits. Nous donnons de nouvelles caractérisations qui engendrent de nouvelles preuves de complétude. Nous donnons aussi l'équivalent en théorie de la complexité du problème de l'obtention du permanent à partir du déterminant par substitution de variables.

I will describe the main known results about the Model Theory of valued fields in positive characteristic (algebraically closed valued fields, Kaplansky fields, tame fields), and then list the most important open problems. I will talk about a few positive and negative results for power series fields over finite fields. I will discuss the role of additive polynomials and finally introduce the notion of "extremal field" and describe the open questions connected with it.

Etant donnés deux ordinaux theta et alpha, on considère l'ensemble "^alpha theta" des alpha-suites de theta (ou de manière équivalente des applications de alpha dans theta). Muni de l'ordre lexicographique, I devient un ensemble totalement ordonné. On donnera dans cet exposé une condition nécessaire et suffisante sur les ordinaux theta, theta', alpha, alpha' pour qu'il y ait isomorphisme entre "^alphatheta" et "^alpha'theta'". Ceci répond à une question posée dans un précédent séminaire général par Salma Kuhlmann.

On présente une simple généralisation du forcing en théorie des modèles et son application aux modèles de type fini engendrés par n éléments. On obtient en particulier un théorème de compacité pour les modèles engendrés par n éléments, un théorème d'omission des types et une condition suffisante pour l'existence de 2^\aleph_0 modèles de type fini élémentairement équivalents.

Les groupes de type fini (il y en a 2 puissance aleph zéro) et les groupes de présentation finie (il y en a aleph zéro) sont des êtres fascinants, objets de résultats profonds : un des plus anciens est le théorème de G. Higman dont on rappellera l'énoncé. Un résultat plus récent dit que les modèles de type fini de la théorie universelle d'un groupe libre (non commutatif) sont de présentation finie.
L'exposé, non technique, traitera des aspects les plus simples de deux questions presque disjointes :
(en collaboration avec Anatole Khélif) : un groupe de type fini pseudofini (i.e., modèle de la théorie des groupes finis) est-il fini?(I)
(en collaboration avec Francis Oger) Y a-t-il des choses intéressantes à dire sur les groupes de type fini G "quasifiniment axiomatisables" (Nies), c'est à dire tels qu'il existe un énoncé ayant G pour unique (à isomorphisme pres) modèle de type fini?(II)
Rappelons qu'un groupe de type fini est un groupe engendré par un ensemble fini. Cela devrait suffire pour suivre l'exposé.
P.S. Ces questions ont un sens pour d'autres structures : il est facile de voir que (I) a une réponse positive pour les anneaux commutatifs. On se borne au cas des groupes par goût.

Un problème central dans la théorie des formes quadratiques - soit sur les corps et sur certaines classes d'anneaux, soit dans des versions axiomatiques - est l'étude de la structure des idéaux Iⁿ de l'anneau de Witt engendrés par certaines formes quadratiques appelées "formes de Pfister" (de degré n). J'expliquerai ce problème en guise d'introduction. Dans le reste de l'exposé je donnerai un aperçu des résultats suivants.
1) En combinant le théorème de compacité (ou de complétude) avec notre propre solution aux conjectures de Marshall et de Lam (1997 et 99), Miraglia et moi-même prouvons l'existence d'une borne récursive uniforme pour le nombre de formes de Pfister d'un degré donné n, suffisant à répresenter une forme quadratique quelconque de dimension m appartenant à Iⁿ, pour plusieurs classes de corps ordonnables : corps pythagoriciens ou de nombre de Pythagore fixé, corps préordonnés. "Uniforme" veut dire que la borne ne dépend ni du corps ni des coefficients de la forme quadratique donnée.
2) Nous trouvons une classe très large de groupes spéciaux réduits pour lesquels il y a une borne simplement exponentielle dans les entiers n et m. Pour les groupes (corps) d'indice de stabilité fini il existe une borne quadratique en [m/2ⁿ].

I will discuss recent work casting doubt on the conjecture that these are the same.

Hausdorff proved that scattered linear orders are exactly the orders that are obtained from the class of well orders by closing under inversions, restrictions and lexicographic sums. Abraham and Bonnet characterised the class of scattered FAC (finite antichain condition) partial orders as another class of sets, closed under the above operations and augmentations. In a joint work Katherine Thompson and I considered the uncountable cardinals kappa for which there is a kappa-saturated linear order, with the idea of classifying the FAC orders that do not embed such an order. Such orders are called kappa-scattered. Partial orders of size kappa that have the property that for every a< b the set {x: a< x < b} has size kappa, are called kappa-dense, and partial orders that do not have a weakly kappa-dense subset are called strongly kappa-scattered. We define a hierarchy of sets and prove that it includes all strongly kappa-scattered FAC posets, and that the hierarchy is included in the class of all FAC kappa-scattered posets. For kappa=aleph_0 our hierarchy agrees with the one from the Abraham-Bonnet theorem.

Un semigroupe est un ensemble muni d'une opération associative. A partir d'un automate A, il est très naturel d'associer à chacun des mots w la relation binaire f(w) sur l'ensemble Q des états de A, définie par (p,q) est dans f(w) si il y a un chemin étiqueté par w qui mène de l'état p à l'état q. Cette application est un morphisme du semigroupe libre des mots finis sur l'alphabet de A, dans le semigroupe des relations binaires sur Q. De cette manière, le comportement d'un automate peut être simulé par un morphisme de semigroupe.

Pour l'étude des automates sur les mots finis, il est apparu souvent très pratique d'utiliser des morphismes de semigroupes sans référence à l'automate sous-jacent. Un certain nombre de constructions sont en réalité plus naturelles sur les semigroupes que sur les automates eux-mêmes.

Passer des mots finis aux mots infinis nécessite d'équiper la notion algébrique de semigroupe d'un produit infini, l'idée essentielle restant la même.

A l'aide d'un jeu infini à deux joueurs, nous montrons comment les propriétés topologiques des ensemble omega-rationnels se reflètent dans les certaines propriétés des omega-semigroupes.

Un groupe G est dit "avoir la propriété de Bergman" si pour toute partie génératrice symétrique X de G il existe un entier n tel que tout élément de G est produit d'au plus n éléments de X.
Bergman a montré que le groupe des permutations d'un ensemble infini vérifie cette propriété. Droste et Holland ont prouvé que le goupe des automorphismes d'une chaîne 2-transitive vérifie aussi cette propriété. Nous tenterons une étude la plus approfondie possible de cette propriété.
Nous étudierons les liens entre cette propriété et le fait de ne pas être une réunion dénombrable croissante de sous-groupes propres. L'étude concernera d'abord les puissances booléennes de groupes finis, et ensuite le cas général. Cela permettra de donner des réponses (plus ou moins complètes) à certaines des questions ouvertes posées par Bergman. Les liens avec la stabilité en théorie des modèles seront brièvement évoqués.

We consider the strengths of the following theories: Pi^1_3-CA_0 , Delta^1_3-CA_0, Sigma^0_3-Determinacy, and AQI, where the last asserts that every arithmetic quasi-inductive operator converges.
The latter theory results in rather large ordinals, and has been used in various areas, including computer science (Kreutzer Aachen). We mention the relations of this with Pi^1_2-CA_0 and the work of Rathjen, but are principally concerned with the location of strategies for certain games in the Goedel L-hierarchy.

A selftransformation of a structure is a permutation of its base which permutes its parametrically definable sets and relations. The universe of a structure is formed by the sets and relations which are definable in it with parameters. Two universes are similar if they have a common elementary extension (the notion of elementary extension does not depend of the structure chosen to generate the small universe).

Problem 1. Consider an omega-one-compact structure, any permutation of its base being a selftransformation ; is the structure interpretable in the language of equality ?

Problem 2. Is any complement of the group of permutations with finite support in the group of selftransformations of the ordering of the rationnals n-transitive for every n ?

Problem 3. Learn French, read the definitions in Section 4, and find two non isomorphic but similar narcissic universes.

Problem 4. Use the skill gained in the solution of the preceding problem to understand the meaning of Question 4 in this paper.

Problem 5. Find a non narcissic cat, that is, a non trivial universal second order theory for which Craig's Interpolation Lemma remains valid.

Problem 6. Find two similar universes which are not the universes of two elementarily equivalent structures.

Problem 7. Classify the universes which are similar to the universe of an omega-one-categorical relation, or more generally the universes which are similar to the universe of a classifiable relation.

Problem 8. Define a meaningful notion of second order forking.

Problem 9. Unicity of the intrinsecal structure of the universe, provided it has one (see the block of definitions opening Section 9).

Problem 10. Necessity of the stability hypothesis in Proposition 9.6.

We consider a covering of a (saturated) group G by countably many type-definable sets. It turns out that in this case the group is generated by finitely many of them in 2 or 3 steps. There are variants of this result for coverings of types and (outside model theory) colourings of groups and graphs. Involved here are weak generic types, amenable groups and in general extensions of some core notions of stability theory to the unstable context. There may be some interactions with descriptive set theory. The results show some similarity between a saturated group and a compact topological group.

A classical problem, going back to von Neumann, is to describe in algebraic terms (completeness, saturation, distributivity and so on) those Boolean algebras which can appear as measure algebras of probability spaces. Maharam offered a criterion in topological terms: let us say that a "Maharam algebra" is a Dedekind complete ccc Boolean algebra carrying a metrizable topology for which the Boolean operations are continuous and order-convergent sequences are topologically convergent. Recently, Balcar, Jech and Pazak have shown that a Dedekind complete ccc Boolean algebra is a Maharam algebra iff {0} is a G_{delta} set in the order-sequential topology. It follows easily that when Todorcevic's p-ideal dischotomy is true, then every weakly sigma-distributive Dedekind complete ccc Boolean algebra is a Maharam algebra.