Lundi 18 juin 2012 à 16h en salle 1D23: Sergei Starchenko (Notre Dame) On Peterzil-Steinhorn subgroups
In the paper "Definable compactness and definable subgroups of o-minimal groups" Y. Peterzil and C. Steinhorn showed that to any unbounded curve in a group definable in an o-minimal structure one can associate a definable one-dimentional subgroup. Roughly, it is a subgroup that is "tangent at infinity" to the curve. In this talk we show that the same can be done for algebraic curves in algebraic groups over arbitrary algebraically closed fields.
Lundi 18 juin 2012 à 14h: Dogan Bilge (Lyon) Rigid moieties of relational homogeneous structures
Given a countable set X, a moiety of X is a subset which is countable and co-countable. A rigid embedding of a structure M into a structure N is an embedding where each automorphism of M extends uniquely to an automorphism of N. We show the existence of rigid moieties in various homogeneous relational structures including universal K_n-free graphs, Henson's continuous family of digraphs and the universal structure in a finite relational language. We finally prove the following: Theorem 1. Let \cal{K} be a not totally disconnected free amalgamation class in a finite relational language L and assume that all the one-point sets in \cal{K} are isomorphic. Then every countably infinite L-structure, whose age lies in \cal{K}, can be embedded as a rigid moiety into the Fraïssé limit of \cal{K}, denoted K. Moreover, there are continuum many such embeddings which are not conjugate in Aut(K).
Lundi 11 juin 2012 : Jacques Duparc (Lausanne) Complexité topologique des langages infinis reconnus par automates
La décidabilité de la logique monadique du second ordre - que ce soit avec un successeur (S1S, Büchi - 1960) ou avec plusieurs successeurs (SkS, Rabin- 1969) - repose sur la notion d'automate à lecture infinie. Les langages ainsi reconnus s'apparentent à des ensembles de réels qui peuvent être comparés en fonction de leur complexité topologique. En effet, pour S1S les automates lisent des mots infinis sur un alphabet fini, alors que pour S2S les automates lisent des arbres. On rappellera en quoi ces langages de mots infinis sont bien compris et relativement simple, et on montrera pourquoi ceux des arbres infinis sont "infiniment" plus compliqués et toujours mal compris. Si le temps le permet on montrera qu'il en va de même pour les modèles du $\mu$-calcul modal.
Lundi 4 juin 2012 : Dimitris Vlitas (Paris) A canonical partition theorem for uniform families of finite strong subtrees
Extending a result of Miliken, we prove a Ramsey classification result for equivalence relations defined on uniform families of finite strong subtrees of a fixed tree U that has some finite uniform branching but is of infinite length. In particular we show that given an equivalence relation on a uniform family of finite strong subtrees of U two strong subtrees are in the same class if and only if they agree on a set of nodes and a set of levels. Completing the line of research parallel to that of Erdös-Rado and Rudlak-Rödl.
Lundi 21 mai 2012 : Andreas Weiermann (Gand) Phase transitions for Gödel incompleteness
We consider true assertions formulated in the language of PA which depend on an order parameter (which might be a primitive recursive real number or a Delta_0-definable non decreasing function). We assume that these assertions are always true, monotone with respect to PA-unprovability, PA-provable for "small" values of the order parameter and PA-unprovable for sufficiently "large" values of the order parameter. In this situation there emerges a phase transition when the order parameter exceeds a threshold value. We survey some basic and beautiful examples and we will explain their underlying rationale. Surprisingly methods of analytic combinatorics in the style of Flajolet and Sedgewick are very useful in this context.
Lundi 14 mai 2012 : Julien Melleray (Lyon) Eléments d'ordre fini dans les groupes d'automorphismes de limites de Fraïssé
On va s'intéresser à certaines propriétés des éléments d'ordre finis dans des groupes d'automorphisme de limites de Fraïssé satisfaisant de fortes propriétés d'amalgamation; on montrera par exemple que dans ces groupes il existe, pour tout n, un élément générique d'ordre n, et que tout autre élément du groupe est un produit de quatre conjugués de cet élément d'ordre n. Si le temps le permet, je présenterai des applications à des groupes d'automorphismes de structures non discrètes. (travail en commun avec D. Bilge)
7 mai 2012 : Laura Fontanella (Paris) "Grandes" propriétés pour petits cardinaux
Les grands cardinaux sont au centre de la recherche contemporaine en théorie des ensembles, mais l'existence de grands cardinaux est une hypothèse très forte qui n'est pas acceptée à l'unanimité par la communauté scientifique. Cependant, dans certains cas, on peut isoler des propriétés typiques de grands cardinaux qui peuvent être satisfaites également par des petits cardinaux. Nous analyserons trois de ces propriétés : la tree property, la strong tree property et la super tree property. Nous discuterons de résultats de consistance relative qui établissent que certains petits cardinaux peuvent satisfaire ces propriétés.
Lundi 2 avril 2012 : Maryanthe Malliaris (Jerusalem) Regular ultrafilters and first-order theories
Keisler's order, introduced in 1967, gives a way of comparing the complexity of first-order theories. The talk will discuss some recent progress of Malliaris and Shelah on this order. I will assume basic knowledge of ultrapowers (Los' theorem) and model theory (types, saturation); otherwise, I intend to give all relevant definitions.
Lundi 26 mars 2012 : Pierre Pansu (Orsay) Difficulté d'approximation
Les premiers résultats de difficulté d'approximation (en supposant P différent de NP) remontent au début des années 90 (théorème PCP). Une hypothèse un peu plus forte (dite conjecture des jeux uniques) permet aujourd'hui de trouver le seuil optimal d'approximabilité pour de nombreux problèmes. Le calcul du seuil convoque souvent des mathématiques diverses et profondes (analyse harmonique, géométrie). On racontera l'histoire, exemplaire de ce point de vue, du problème MAX CUT.
Lundi 12 mars 2012 : Joan Bagaria (Universitat de Barcelona) Large cardinals in Abelian group theory
I will present some results in the theory of infinite Abelian groups that involve the use of large cardinals. Starting with the Eda-Los Theorem on group homomorphisms, which involves measurable cardinals, and following with results of Dugas and Gobel on group radicals and torsion classes, which make use of strongly compact cardinals, I will present some recent results, obtained in a joint work with Menachem Magidor, in which we solve some questions regarding the large cardinals needed for some of the results in this area. The solution hinges on building a model of set theory in which the first omega_1-strongly compact cardinal is singular.
Lundi 5 mars 2012 : Christina Brech (São Paulo) How to characterise P(N)/Fin
In the sixties, Parovicenko obtained a characterisation of the Boolean algebra P(N)/Fin under the continuum hypothesis. Since then a lot of effort has been made to obtain a characterisation of P(N)/Fin in the Cohen model or even in ZFC. We will discuss some of the trials and show, under the assumption that c is a regular cardinal, the existence and uniqueness of a Boolean algebra which is P(N)/Fin under CH and in the Cohen model. This is a joint work with Antonio Avilés.
Lundi 27 février 2012 : Davide Penazzi (University of Leeds) Internality and integrability
There are many notions of integrability for a differential equation over the field of the complex numbers; for example an equation is algebraically integrable if there are enough independent rational first integrals. In the model theoretic context, (almost) internality of the solution set of an equation to the constants gives rise naturally to some integrability. Indeed, for a certain class of differential equations, Chatzidakis and Hrushovski proved that the solution set is almost internal to the constants over C(t)^{alg} if and only if it is algebraically integrable. We generalize this result and show that (almost) internality corresponds to the equation having enough first integrals in C(t,a1,...,ak) where a1,...,ak are specific solutions of some differential equations. This is joint work with R. Nagloo and A. Pillay.
Lundi 13 février 2012 : Bruno Zanuttini (Université de Caen) Clones relationnels gelés
(Clones relationnels gelés) Dans les années 1940, Emil Post a classifié l'ensemble des opérateurs booléens en clones, qui peuvent être vus comme des classes closes en termes d'expressivité (de circuits qu'ils permettent de construire). Dans les années 1990, l'équipe de Peter Jeavons a revisité cette classification en termes de complexité des problèmes de satisfaction de contraintes : une correspondance de Galois est établie entre le treillis des clones et un treillis de classes de relations booléennes, appelées clones relationnels. Si deux langages de relations génèrent le même clone relationnel, alors le problème de satisfaction de contraintes a la même complexité lorsque l'on en restreint les relations à l'un ou l'autre des langages. Ces résultats ont été très largement utilisés pour déterminer, de façon exhaustive en un certain sens, la complexité de problèmes portant sur des formules booléennes, en particulier en intelligence artificielle. Néanmoins, ils permettent d'obtenir des résultats à réductions polynomiales près. Ils ne font donc pas la différence entre une restriction autorisant une complexité en O(c^n), et une pour laquelle on ne sait pas mieux faire que \Theta(d^n) avec d>c. En outre, les réductions obtenues par les techniques de Jeavons introduisent des variables auxiliaires, et ne sont donc pas adaptées pour tous les problèmes. Dans cet exposé, je présenterai un raffinement des notions de Jeavons permettant d'obtenir des réductions préservant la complexité exacte des problèmes, et élargissant le champ des problèmes abordables. Cette notion de "clones relationnels gelés" pose notamment des questions intéressantes, telles que l'existence d'un unique problème SAT "minimalement NP-complet". Ce travail est commun avec Gustav Nordh, de l'Université de Linköping (Suède).
Lundi 6 février 2012 : Immanuel Halupczok (Universität Münster, Allemagne) Stratifications d'ensembles définissables dans des corps Henséliens
Dans R, une façon de décrire un ensemble définissable est de donner une décomposition cellulaire. Une autre façon (moins connue en théorie des modèles) est de donner une stratification de Whitney. Celle-ci a deux avantages: elle ne dépend pas de l'ordre des coordonnées et elle donne plus d'information. Dans un corps K valué Hensélien de caractéristique résiduelle 0, l'existence de décompositions cellulaires est aussi un résultat classique. Le but de mon exposé est de présenter une notion de stratification dans ce contexte: les "t-stratifications". Entre autre, elles donnent une description précise des ensembles définissables à isométrie (ultramétrique) près. L'existence des t-stratifications implique aussi le résultat correspondant dans R: En choisissant pour K un modèle non-standard de R, les t-stratifications permettent de retrouver les stratifications de Whitney classiques.
Lundi 23 janvier 2012 : Margarita Otero (Universidad autonoma de Madrid & ICJ, Université Lyon 1) Solvable definable groups
I will discuss some topics on solvable groups definable in o-minimal structures. I will focus on joint work with Elías Baro and Eric Jaligot on existence and definability of some relevant subgroups of solvable definable groups.
Lundi 16 janvier 2012 : Artyom Chernikov (ICJ - Université Lyon 1) Forking ideal
Invariant ideals in the Boolean algebra of definable sets play crucial role in the model-theoretic classification theory. Perhaps, the most important of them is the forking ideal introduced by Shelah for the purposes of classifying stable theories. Since then it proved useful in much larger classes of theories. Sometimes this ideal allows one to define a symmetric notion of independence between arbitrary subsets, analogous to the linear independence in vector spaces and to the algebraic independence in algebraically closed fields. Even when symmetry fails, it still carries a lot of information about the interaction of types. An important property this ideal may satisfy is a certain chain condition (a requirement that there are no arbitrarily large anti-chains in the corresponding filter). We will describe a recent demonstration that this chain condition is satisfied by the forking ideal in a large class of first order theories without tree property of the second kind, NTP_2. This class contains both simple and NIP theories, and also for example the ultraproduct of p-adics. Combined with results of Hrushovski, this implies certain amalgamation properties for types. Joint work with Itai Ben Yaacov.
Lundi 9 janvier 2012 : Todor Tsankov (IMJ - Equipe de logique) Les flots minimaux de S_infty
Si G est un groupe topologique, un G-flot est un espace compact sur lequel G agit de manière continue. Un intérêt spécial est accordé aux flots minimaux -- ceux qui n'ont pas de propres sous-flots -- à cause de leur riche structure et du fait que tout flot contienne un sous-flot minimal. Il existe toujours un G-flot minimal universel dont tous les G-flots minimaux sont des quotients, mais si G est un groupe localement compact ce flot n'est jamais métrisable et il est difficile à décrire de manière explicite. En revanche, une riche théorie a été développée pour décrire les flots minimaux universels de certains groupes d'automorphismes des limites de Fraïssé et des liens importants avec la théorie de Ramsey structurelle ont été découverts (surtout dans un article de Kechris, Pestov et Todorcevic). Le fait que le flot minimal universel d'un groupe soit calculable et relativement petit donne la possibilité de classifier ses quotients, tous les flots minimaux du groupe. Dans cet exposé je vais décrire tous les flots minimaux de S_infty, le groupe des permutations des entiers.
Lundi 12 décembre 2011 : Michael Pinsker (Équipe de logique) Reducts of the random partial order
I will present a recent result which states that up to first-order interdefinability, there exist precisely 5 structures which are first-order definable in the universal homogeneous partial order. I will also outline the proof of this result, which is achieved by finding all closed permutation groups which contain the automorphism group of this order. The method for finding the groups relies on a Ramsey-theoretic analysis of permutations acting on the order, which makes it possible to find regular patterns in such permutations and make them accessible to finite combinatorial arguments.
Lundi 28 novembre 2011 : Katrin Tent (Universität Münster, Allemagne) On the Isometry Group of the Urysohn Space
The Urysohn space can be characterized as the unique complete, separable and homogeneous space which embeds every finite metric space. Using model theoretic techniques we prove that the normal closure of any unbounded isometry is the whole isometry group. This result extends to many other natural classes of very homogeneous structures and generalizes a number of known results.
Lundi 21 novembre 2011 : Matteo Viale (Università di Torino) Forcing and absoluteness as means to prove theorems
The forcing method has been introduced by Cohen in the early sixties to prove the independence of the continuum problem. Forcing can be presented as an "algorithm" which takes as inputs a model M of ZFC and a boolean algebra B belonging to M and produces a boolean valued model MB of ZFC. The first order theory of MB depends on the first order theory of M and on the combinatorial properties of B. Since its introduction forcing has been the most powerful tool to prove independence results in set theory. In this talk we shall take a different attitude and show that forcing is a powerful tool to prove theorems in ZFC. The talk aims to be accessible to a general audience of logicians. In particular we try to make the most part of it accessible to an audience who does not have any acquaintance with forcing. Those interested in the argument of this seminar can consult the preprint Martin's maximum revisited available at my web-page. Longer abstract (PDF)
Lundi 14 novembre 2011 : Margaret Thomas (Universität Konstanz, Allemagne) The density of algebraic points on definable sets
The results outlined in this talk concern the program of bounding the density of rational and algebraic points lying on sets definable in o-minimal expansions of the real field. Following Pila and Wilkie's influential work in this area, Wilkie has conjectured an improvement to their main result for sets definable in the real exponential field. We shall survey the progress that has been made towards this, including the proven one-dimensional case of the conjecture and some partial results for certain surfaces. These results are joint work with Gareth O. Jones.
Lundi 7 novembre 2011 : Achim Blumensath (Liafa, Universite Paris Diderot) Algorithmic Model Theory
This talk is intended to give an overview of algorithmic model theory. The focus will be on operations on structures that preserve the decidability of theories. In particular, I will present in detail a classification theorem describing the expressive power of monadic second-order interpretations.
Lundi 24 octobre 2011 : Ivan Tomasic (Queen Mary, Londres) Twisted Galois Stratification
The aim is to present the development of difference algebraic geometry and its applications to counting solutions of difference polynomial equations over fields with powers of Frobenius. We prove, using Hrushovski's version of twisted Lang-Weil estimate, a twisted version of Chebotarev's theorem for a Galois covering of difference schemes, and use it to deduce an important direct image theorem: the image of a `twisted Galois formula' by a morphism of difference schemes is again a twisted Galois formula. A logician's translation of the above statement is that the theory of fields with powers of Frobenius, or ACFA, has quantifier elimination in the language of twisted Galois formulae.
Lundi 17 octobre 2011 : Clément Lasserre (IMJ, Équipe de logique) La notion de structure QFA (exposé annulé)
Depuis son introduction par Nies en 2003, la notion de structure quasi finiment axiomatisable (QFA) a connu quelques développements. Nous sommes à même d'en présenter des exemples variés, particulièrement en ce qui concerne les groupes, et d'établir des liens avec d'autres notions comme celles de primalité et de bi-interpretabilité avec l'arithmétique. Cet exposé a pour but de présenter les résultats principaux et de rendre compte des résultats de ma thèse.
Lundi 10 octobre 2011 : Hervé Fournier (IMJ, Équipe de logique) Monômes dans les circuits arithmétiques et hiérarchie de comptage
La représentation d'un polynôme par un circuit arithmétique le calculant est économique en terme d'espace, mais la complexité d'opérations même simples sur des polynômes ainsi représentés peut devenir importante. On s'intéresse à la complexité de deux questions à propos des polynômes représentés par des circuits arithmétiques : tester si un monôme est présent et compter les monômes. En étudiant ces questions sur diverses classes de circuits, on obtient des problèmes complets pour des sous-classes de la hiérarchie de comptage qui possédaient jusqu'à présent peu ou aucun problème complet naturel. (Travail en commun avec Guillaume Malod et Stefan Mengel.)
Lundi 3 octobre 2011 : Dmitry Sustretov (Oxford University) Non-algebraic Zariski geometries
A Zariski geometry is a first-order structure that has predicates for closed sets of topologies on cartesian powers of its universe. These topologies must satisfy certain conditions that make them look like Zariski topologies of cartesian powers of an algebraic variety over an algebraically closed field. Zilber trichotomy is a conjecture about the structure of "one-dimensional" first-order structures, it roughly says that their geometric structure is determined by classical algebraic objects that are interpretable (groups, fields). The trichotomy conjecture has been refuted in full generality by Hrushovski. Model-theoretically, one-dimensional Zariski geometries form an interesting class of structures for which Zilber trichotomy holds. On the other hand, the axiomatics of Zariski geometry can be seen as an abstract framework to do geometry. Hrushovski and Zilber have shown that one-dimensional non-locally modular Zariski geometries satisfying a non-degeneracy condition (very ampleness) actually are algebraic varieties. However, if this condition is dropped, one can construct Zariski geometries that are not interpretable in an algebraically closed field. In the talk I will consider several examples of such structures and discuss the proofs of their non-algebraicity.