Lundi 21 septembre 2009 : Deirdre Haskell (McMaster; Université Paris 7) La densité VC pour les formules dans quelques théories avec NIP
La dimension VC et la densité VC sont des propriétés d'une collection
d'ensembles qui vient de la théorie de la probabilité. C'était Laskowski
qui a aperçu le lien avec la notion NIP de la théorie des modèles. Ce lien
donne beaucoup d'exemples de collections d'ensembles ayant la dimension
VC finie. En général, il est difficile de trouver des bornes supérieures
pour la dimension VC, et les bornes connues sont assez grandes. Mais il
est plus facile de borner la densité VC.
Dans cet exposé, je vais expliquer toutes les définitions ci-dessus pour
esquisser un théorème qui donne une borne minimale de la densité VC des
formules pour quelques théories ayant la propriété NIP.
Lundi 28 septembre 2009 : Todor Tsankov (Université Paris 7) Relations d'équivalence engendrées par des actions profinies
Je ferai un survol de la théorie des relations d'équivalence définissables en me concentrant sur celles dont les classes sont dénombrables. Comme elles peuvent toutes être réalisées comme les relations d'équivalence orbitales d'une action d'un groupe dénombrable, on est naturellement amené à étudier ces actions. Je vais considérer une classe particulière d'actions - les actions profinies (les limites inverses d'actions sur des ensembles finis) et montrer une nouvelle caractérisation des relations d'équivalence orbitales engendrées par de telles actions.
Lundi 5 octobre 2009 : Manuel Bodirsky (École Polytechnique) All reducts of the Random Graph are model-complete
(Joint work with Michael Pinsker.) I will present a classification theorem for locally closed transformation monoids which contain the automorphism group of the random graph: such a monoid is locally generated by the permutations in the monoid,or contains a constant operation,or contains an operation that maps the random graph injectively to an induced subgraph which is a clique or an independent set. As a corollary, our techniques yield a new proof of Simon Thomas' classification of the five closed supergroups of the automorphism group of the random graph; our proof uses different Ramsey-theoretic tools than the one given by Thomas, and is perhaps more straightforward. Since the monoids under consideration are endomorphism monoids of relational structures definable in the random graph, we are able to draw several model-theoretic corollaries: One consequence of our result is that all structures with a first-order definition in the random graph are model-complete. Moreover, we obtain a classification of these structures up to existential interdefinability. I will finally discuss how these results can be applied to classify the computational complexity of graph constraint satisfaction problems.
Lundi 12 octobre 2009 : Adrien Deloro (IMJ) Petites représentations en rang de Morley fini
Les groupes de rang de Morley fini peuvent être vus comme une généralisationmodèle-théorique desgroupes algébriques. S'ils sont surtout connus pour une conjecture de Cherlin et Zilber, on peut aussi poser des questions plus immédiatement géométriques, liées à leurs représentations. Je présenterai deux résultats jumeaux sur l'algébricité de petites représentations dans un paysage de rang de Morley fini. L'un des deux a été obtenu avec Gregory Cherlin.
Lundi 26 octobre 2009 : Olivier Finkel (Équipe de Logique) Sur les langages de figures infinies acceptés par systèmes de pavages
On rappellera les notions d'acceptation de langages de mots bi-dimensionnels infinis, ou figures infinies, par systèmes de pavages, en considérant diverses conditions d'acceptation. On présentera des résultats sur la complexité topologique de ces langages, puis on verra que de nombreux problèmes de décision sur ces langages sont hautement indécidables, c'est à dire situés au delà de la hiérarchie arithmétique. Beaucoup sont même $\Pi^1_2$-complets c'est à dire complets au second niveau de la hiérarchie analytique. On verra aussi que certaines questions sur ces langages dépendent des modèles de la théorie des ensembles, ce qui conduit à des problemes situés au troisieme niveau de la hierarchie analytique. Certains résultats similaires sont obtenus pour les langages de mots infinis acceptés des machines simples comme les automates a un compteur ou a deux rubans.
Lundi 9 novembre 2009 : Martin Bays (University of Oxford) Model theory of some exponential maps
I will discuss an approach due to Zilber to the model-theoretic study of the complex exponential map and its analogues, focusing on some recent progress in the case of elliptic curves. No prior knowledge of the relevant mathematics will be assumed.
Lundi 16 novembre 2009 : Sylvain Perifel (LIAFA, Universite Paris 7) Borne inférieure pour le calcul d'un polynôme non explicite
En complexité algébrique on s'intéresse au nombre d'additions et de multiplications nécessaires pour calculer des polynômes. On peut facilement montrer des bornes inférieures lorsque le degré ou le nombre de variables est grand, par exemple, mais pour les polynômes intéressants il semblait qu'aucune borne inférieure n'était connue. J'expliquerai comment on peut montrer une telle borne inférieure par diagonalisation (en supposant l'hypothèse de Riemann pour traiter le cas des constantes arbitraires). Mais en réalité, ce genre de borne inférieure était connu depuis plus de 30 ans dans les travaux de Strassen, Lipton et Schnorr, bien que presque oublié. J'expliquerai la méthode très élégante de Schnorr (1978) et suggèrerai des pistes de recherche pour obtenir un polynôme "explicite" (c'est-à-dire dont les coefficients sont calculables efficacement).
Lundi 23 novembre 2009 : Victor Dalmau (Universitat Pompeu Fabra, Barcelona) Constraint Satisfaction: Logic, Dualities, and Algebra
The Constraint Satisfaction Problem (CSP) is the computational problem consisting in deciding, given two relational structures A and B, whether there is a homomorphism from A to B. In its full generality, CSP is NP-complete which has motivated the identification of subcases tracables of the problem. One of the most studied family of restrictions is obtained by fixing the target structure, B, giving rise to the so-called, non-uniform CSP with template B, CSP(B). One of the most useful approaches to study CSP(B) has been the consideration of the logic necessary to define the set of negative instances. This approach links together logic, combinatorics (via the notion of duality or obstruction set), and universal algebra. In this talk we shall survey this approach.
Lundi 30 novembre 2009 : Giuseppina Terzo (Napoli) Exponential Algebra and Schanuel's Conjecture
In last years Schanuel's Conjecture (SC) has played a fundamental role in the Theory of Transcendental Numbers and on in decidability issues. Macintyre and Wilkie proved the decidability of the real exponential field, modulo (SC), solving in this way a problem left opened by A. Tarski. Moreover, Macintyre proved that the exponential subring of R generated by 1 is free on no generators. In this line of research we obtained that in the exponential ring (C, e^x), there are not further relations except i^2 = -1 and e^{i\pi} = -1 modulo SC. Assuming Schanuel's Conjecture we proved that the E-subring of R generated by \pi is isomorphic to the free E-ring on \pi. These results have consequences in decidability issues both on (C, e^x) and (R, e^x). Moreover, we generalize the previous results obtaining, without assuming Schanuel's conjecture, that the E-subring generated by a real number not definable in the real exponential field is freely generated. We also obtain a similar result for the complex exponential field.
Lundi 7 décembre 2009 : Lionel NGUYEN VAN THE (Université Paul Cézanne - Aix-Marseille III) Partitions de l'espace d'Urysohn
Construit en 1925 par Paul Urysohn, l'espace d'Urysohn est le premier exemple d'espace métrique séparable dans lequel tout espace métrique séparable se plonge de manière isométrique. Au cours de cet exposé, je présenterai les résultats de partition (de type Ramsey) récents et moins récents qui lui sont désormais associés.
Lundi 14 décembre 2009 : Jordi Lopez Abad (ICMAT, Madrid) Examples of non-separable $L_1(\mu)$-preduals.
We present a unified method for constructing several uncontable direct limits of copies of $\ell_\infty^n$ spaces. In particular, examples of non-separable Gurarij spaces, preduals of $\ell_1(\omega_1)$ and the dual constructions of generic simplices will be exposed. We will discuss some striking differences between these non-separable constructions and the corresponding separable examples where the generic objects tend to be unique.
Lundi 11 janvier 2010 : Franck Benoist (Université Paris Sud) Sous-groupe maximal divisible pour les variétés semi-abéliennes en caractéristique p
L'étude du sous-groupe maximal divisible p^\infty G(K), pour G une variété semi-abelienne au dessus d'un corps séparablement clos non parfait K, est essentielle dans la preuve par Hrushovski de la conjecture de Mordell-Lang. J'expliquerai le lien entre les propriétés modèle-théoriques de ce sous-groupe et l'exactitude du foncteur G \mapsto p^\infty G(K). En particulier, j'exhiberai une variété semi-abélienne G pour laquelle p^\infty G(K) n'a pas de rang de Morley relatif. C'est un travail commun avec Elisabeth Bouscaren et Anand Pillay.
Lundi 18 janvier 2010 : Alexey Sossinsky (Moscou,UIM) et Iegor Reznikoff (Universite Paris 10) The Conway-Kochen Free Will Theorem and Freedom in Mathematical Logic
In a recent paper, John Conway and Simon Kochen proved a
quantum-mechanical theorem asserting in that, in certain
experiments, if the experimenter is endowed with free will,
then so is the quantum particle participating in the experiment.
By "endowed with free will" means that the actions of the
subject are not determined by the subject's prehistory. This
is indeed a mathematical theorem, its proof is a logical argument
which deduces, from certain axioms of quantum theory (in weak
form), that experiments with nondeterministic outcomes exist,
provided that the experimenter is free to chose the setup of
the experiment. Surpisingly, the axioms do not involve any
randomness assumptions and the proof is based on an elementary
statement about cubes in Euclidean 3-space.
On the other hand, the question of free and independent
axiomatization is a classical topic in mathematical logic going
back to the work of Tarsky and developed over the years by
one of the speakers. The main goal of the talk is to answer the
following question: Is there any conceptually significant
relationship between freedom in quantum mechanics and freedom
in mathematical logic?
No knowledge of quantum mechanics is required to understand the
talk (at least formally).
Lundi 25 janvier 2010 : Zoé Chatzidakis (Équipe de logique) Bases canoniques de types de rang fini
Je vais parler de la CBP (canonical base property) pour les types de
rang SU fini. Cette propriete a ete introduite par Pillay et
Ziegler, qui ont montre que les corps differentiellement clos et les
corps aux differences existentiellement clos de caracteristique
0 la satisfont. On ne sait pas si la CBP est toujours verifiee.
Je vais d'abord rappeler la definition de la base canonique, et
donner quelques exemples naturels. Puis, je mentionnerai un resultat
de reduction du probleme, qui permet d'etendre le resultat de
Pillay-Ziegler aux corps aux differences existentiellement clos de
caracteristique arbitraire. Enfin, je parlerai de consequences de la
CBP, en particulier la UCBP, une propriete introduite par Moosa et
Pillay.
L'expose devrait etre accessible a toute personne ayant quelques
connaissances en algebre.
Lundi 1er février 2010 : J.A. Makowsky (Technion Haifa) Application of Logic to Generating Functions: Holonomic Sequence
In a recent paper, John Conway and Simon Kochen proved a
quantum-mechanical theorem asserting in that, in certain
experiments, if the experimenter is endowed with free will,
then so is the quantum particle participating in the experiment.
By "endowed with free will" means that the actions of the
subject are not determined by the subject's prehistory. This
is indeed a mathematical theorem, its proof is a logical argument
which deduces, from certain axioms of quantum theory (in weak
form), that experiments with nondeterministic outcomes exist,
provided that the experimenter is free to chose the setup of
the experiment. Surpisingly, the axioms do not involve any
randomness assumptions and the proof is based on an elementary
statement about cubes in Euclidean 3-space.
On the other hand, the question of free and independent
axiomatization is a classical topic in mathematical logic going
back to the work of Tarsky and developed over the years by
one of the speakers. The main goal of the talk is to answer the
following question: Is there any conceptually significant
relationship between freedom in quantum mechanics and freedom
in mathematical logic?
No knowledge of quantum mechanics is required to understand the
talk (at least formally).
Lundi 15 février 2010 : Bruno Poizat (ICJ, Université Lyon 1) Transformations
Une fonction est par définition une application de {0, 1}^n dans {0, 1},
ou plus généralement dans un corps fini k , ou plus généralement encore
dans un anneau A finiment engendré. Comme toute fonction f s'exprime
comme un polynôme à coefficients dans A, nous appelons complexité de f le nombre minimal d'additions et de multiplications qu'il faut pour
l'obtenir à partir de variables et de constantes.
Nous appelons transformation une application linéaire inversible entre
fonctions, qui satisfait à la condition de Fubini : T(f).T(g) = T(f.g)
quand les uples de variables de f et de g sont disjoints. Un exemple
de transformation est la duale inverse, qui décrit les coefficients du
polynôme canonique de f. Nous étudierons les effets des transformations
sur la complexité des fonctions.
Cet exposé s'adresse a des mathematiciens normaux, et ne suppose aucune
connaissance préalable sur les classes de complexite de calcul (P, NP, #P,
PSPACE, etc.).
Cliquez ici pour voir les transparents de l'exposé.
Lundi 22 février 2010 : Luc Bélair (UQAM, Montréal) Les séries de Laurent comme module
La théorie des modèles du corps des séries de Laurent sur un corps de caractéristique non nulle reste pratiquement inconnue. Je vais parler de quelques résultats et questions sur la théorie des modèles des séries de Laurent sur un corps, vues comme module (avec structures additionnelles).
Lundi 8 mars 2010 : Michael Pinsker (Equipe de Logique; TU Wien; Einstein Inst. Math. Jerusalem) Reducts of homogeneous structures with the Ramsey property
For a given countably infinite ultrahomogeneous structure S in a
finite relational language, we are interested the problem of
classifying its reducts, i.e., those relational structures which have
a first-order definition in S. A conjecture of Simon Thomas from 1991
states that the number of such reducts is, up to
first-order-interdefinability, always finite. The conjecture holds for
many prominent structures, such as the dense linear order or the
random graph.
The reducts of S, factored by the equivalence of
first-order-interdefinability, correspond precisely to the closed
supergroups of the automorphism group of S. The problem thus is to
find these groups. This seems to be more feasible if S (or at least S
together with a suitable order) has the Ramsey property, i.e., if its
set of finite induced substructures is a Ramsey class: This is because
in that case, one can use Ramsey-theoretic methods in order to find
regular ``patterns'' in any permutation, and the group generation
process can be understood better. In the lecture, I will show how to
find such patterns. I will also explain how under this additional
assumption one can prove that the number of minimal closed supergroups
of the automorphism group of S is finite.
Finer classifications of reducts (e.g., up to existential or primitive
positive interdefinability) require the study of other objects such as
closed transformation monoids and closed clones that contain the
automorphisms of S; we discuss the advantages of S having the Ramsey
property for such investigations.
Lundi 15 mars 2010 : Sedki Boughattas (Equipe de Logique)
Lundi 22 mars 2010 : Philip Scowcroft (Wesleyan University) Existentially closed dimension groups
A dimension group is a special kind of partially ordered Abelian group first studied in connection with operator algebras. Existentially closed dimension groups are to dimension groups as algebraically closed fields are to fields. This talk will explain all the terms in its title and characterize the existentially closed dimension groups.
Lundi 29 mars 2010 : Martin Koerwien (CRM, Barcelona) Absoluteness of categoricity
Many model theoretic notions are absolute (i.e. independent from the choice of our set theoretic universe), especially in the model theory of first order logic. In this talk, we present an example due to S. Shelah showing that in relatively mild extensions of first order logic, the very basic model theoretic notion of categoricity is not absolute. For that purpose, we will recall the notion of Abstract Elementary classes (AEC) and make use of a basic theorem about them. Analyzing that example, we will be able to present sufficient conditions for non-absoluteness of categoricity in AEC's and then we will discuss those conditions. This is joint work with Sy Friedman.
Lundi 12 avril 2010 : Anand Pillay (University of Leeds) Measures in model theory
Lundi 3 mai 2010 : Jean Berthet (ICJ, Université Lyon 1) T-Algèbre des algèbres basées en groupes
On peut démontrer à partir du théorème des zéros de David Hilbert une caractérisation « algébrico-géométrique » des corps algébriquement clos (CAC) parmi les anneaux intègres (AI), anneaux de coordonnées des variétés irreductibles. Nous montrerons dans un premier temps que la notion modèle-théorique de T-radical introduite par Gregory Cherlin permet d'en comprendre et d'en généraliser la connexion avec la caractérisation modèle-théorique des CAC comme AI existentiellement clos. L'approche moderne en géométrie algébrique permet grâce à la représentation des variétés affines par des foncteurs, d'étudier les objets géométriques de manière plus intrinsèque et plus générale, en sortant du contexte précédent de la catégorie des anneaux intègres et de leurs plongements pour travailler dans la catégorie des anneaux et de leurs homomorphismes, ce qui est suggéré par l'équivalence entre les variétés affines et les algèbres réduites de présentation finie. A partir d'une caractérisation des corps algébriquement clos dans cette catégorie plus vaste, on peut développer en Logique Positive un cadre universel qui propose une version abstraite des idéaux premiers et radiciels relatifs à une théorie du premier ordre, des variétés affines et de leur représentation par des foncteurs. Le théorème des zéros devient alors un corollaire de la Modèle-Complétude Positive, et l'on dispose alors d'une notion de T-radical plus proche de celle utilisée couramment en algèbre (radical, radical réel, radical différentiel...). Nous proposons d'en exposer ici une version modérée qui permet de formuler la théorie des idéaux dans le langage de l'Algèbre Universelle et de la théorie des groupes. En particulier, cela fournit une possibilité d'étudier ces phénomènes en général pour des théories d'anneaux avec symboles fonctionnels additionnels.
Lundi 10 mai 2010 : Matt Foreman (University of California - Irvine et Fondation Sciences Mathématiques de Paris) The classification program for ergodic measure preserving transformations
In 1932 von Neumann proposed a program for the classification of measure preserving transformations. After an enormous amount of work was done on this problem, including the development of entropy and spectral invariants, the program stalled in the late 70's and early 80's. In this talk I will review the history and discuss recent joint work with Rudolph and Weiss that demonstrates rigorous ``anti-classification theorems", illustrating that there are fundamental obstacles to any classification. I will finish by mentioning a very recent joint result with Weiss extending the anti-classification result to C^\infty maps on the 2-torus.
Lundi 17 mai 2010 : Thomas Blossier (ICJ, Université Lyon 1) Groupes définissables dans le mauvais corps
Un mauvais corps (corps de rang de Morley fini muni d'un sous-groupe multiplicatif propre divisible) a été construit il y a quelques années par Baudisch, Hils, Martin-Pizarro, Wagner. Ce mauvais corps a été obtenu en collapsant le corps vert construit auparavant par Poizat. Dans un travail commun avec Martin-Pizarro et Wagner, nous avons entamé une étude des groupes définissables dans certains amalgames de Hrushovski, puis obtenu une description complète des groupes définissables dans le mauvais corps vert. Notre description montre en particulier qu'il n'y a pas de nouveaux groupes simples définissables dans ce mauvais corps (c.à.d qu'ils sont tous algébriques comme l'affirme la conjecture d'algébricité de Cherlin et Zilber).
Lundi 31 mai 2010 : Pandelis Dodos (National Technical University of Athens) The Halpern-Lauchli theorem, its density version and its applications
The Halpern-Lauchli theorem is a deep pigeon-hole principle concerning partitions of finite products of finitely branching trees. We shall discuss some recent advances on this theorem, as well as, some of its applications in the geometry of Banach spaces.
Lundi 7 juin 2010 : Janak Ramakrishnan (ICJ, Université Lyon 1) Ordres linéaires définissables dans des structures o-minimales
Nous présenterons une classification complète des ordres linéaires définissables dans des structures o-minimales. En gros, pour n'importe quel groupe o-minimal M et ordre linéaire définissable dans M, il y a un plongement définissable de cet ordre dans un produit cartésien, M^n, avec son ordre lexicographique. Le nombre naturel n est borné par deux plus la dimension de l'ordre, et les projections des première et dernière coordonnées sont finies. Un groupe o-minimal est une structure o-minimale qui est un groupe ordonné avec éventuellement de la structure supplémentaire. Ce résultat améliore un résultat de Steinhorn et Onshuus.
Lundi 21 juin 2010 : Zlatan Damnjanovic (Departement of Philosophy, Univerisity of South California) From Strings to Numbers
The talk articulates a minimal, formalist framework for the representation of mathematical reasoning. We develop basic arithmetic in an elementary theory of concatenation, simulating induction and primitive recursion without taking the standard natural numbers for granted. The concatenation theory is proved to be mutually interpretable with the well-known arithmetical theory Q.