Lundi 27 juin 2011 : Antonio Avilés López (Universidad de Murcia, Espagne) Sigma-algebras in products and sigma-algebras in Banach spaces
Kunen studied which cardinals k satisfy that all subsets of the product k x k belong to the sigma algebra generated by product sets A x B. We shall relate this to several sigma-algebras defined on Banach spaces and Boolean algebras.
Lundi 30 mai 2011 : Alice Medvedev (University of California, Berkeley) The Recursive Spectrum of a Strongly Minimal Modular Theory of Groups in a Finite Language
( I will define and explain "strongly minimal", "modular", "recursive spectrum", and all other frightening words.) The recursive spectrum of a fixed strongly minimal theory T is the set of integers n such that the model of T of dimension n admits a recursive presentation. How complicated can this set be? Some interesting examples can be constructed by coding complicatedness into an infinite language, or by using Hrushovski constructions. We are working towards showing that the recursive spectrum of a strongly minimal locally modular theory in finite language must be nothing; everything; or only the prime model. The title describes the current state of this joint work with Uri Andrews.
Lundi 23 mai 2011 : Alex Usvyatsov (CMAF, Lisbonne) Minimal stable types in Banach spaces
Stability was introduced to Banach space theory by Krivine and Maurey,
who proved that a stable Banach space embeds an l_p space almost
isometrically. The proof uses analysis of types (and their span) over
stable Banach spaces. We present a slightly different approach to the
study of geometry of stable types in Banach spaces, which introduces
techniques and ideas analogous to those from classical geometric stability
theory.
Specifically, we prove the existence of wide types (which play the role
of non-algebraic types in this context), and provide geometric analysis
of minimal stable wide types. As one consequence, we conclude a structure
theorem for non-separably categorical elementary classes of Banach
spaces, affirming a conjecture by C. Ward Henson. This is a joint work
with Saharon Shelah.
Lundi 16 mai 2011 : Daniel Leivant (Indiana University - Bloomington) The Comprehension Cube
Second order logic is a master descriptive formalism for computation and programming, and yet its standard proof theory far exceeds the realm of computability. Three independent methods can be used to tame the comprehension principle of second order logic so as to convey a more computational contents: restriction to positive formulas, prohibition of set parameters, and ramification. The various combinations of these three give rise to a cube of complexity classes, going from the full analytical hierarchy down to polynomial time. [Note: This is a revised and expanded version of my April CLI seminar]
Lundi 9 mai 2011 : Alain Prouté (IMJ - Equipe de logique) Comment on traite la question de l'indépendance de l'hypothèse du continu et de l'axiome du choix avec la théorie des faisceaux de Grothendieck
Bien sûr, il ne faudra pas s'attendre à avoir des démonstrations complètes. Il faudrait un cours entier pour cela. Je vais essayer de brosser un tableau permettant de comprendre les idées principales, et pourquoi en définitive les travaux de Grothendieck et de Cohen sont très proches l'un de l'autre. D'ailleurs, les logiciens reconnaitront certainement des constructions qu'ils connaissent et je les encourage à intervenir pendant l'exposé, ce qui sera l'occasion de mieux comprendre le lien entre les constructions de Cohen et celles que Tierney (hypothèse du continu) et Freyd (axiome du choix) ont utilisées dans le cadre de la théorie de Grothendieck.
Lundi 2 mai 2011 : Isaac Goldbring (UCLA) Definable functions in metric structures
Model theory for metric structures is a relatively new area of model theory which utilizes a continuous logic that is better suited for studying structures from analysis whose underlying universe is a complete metric space than classical first-order logic. There is a natural notion of definability for sets and functions in this model theory and this notion shares many of the same properties as its classical counterpart. However, understanding exactly which sets and functions are definable in a particular metric structure has turned out to be an interesting endeavor. In this talk, I will discuss two theorems which appear to be the first results in this direction. First, I will show that the definable linear operators on a (real or complex) Hilbert space are exactly the scalar plus compact operators. Second, I will show that a definable function on the Urysohn space is either a projection function or else has relatively compact image. Here, the Urysohn space is the unique (up to isometry) Polish space which is universal and ultrahomogeneous. (There will be more to say about the Urysohn space in my talk in the model theory seminar on Tuesday.) In both cases, I will discuss some applications of our definability results.
Lundi 4 avril 2011 : Hubie Chen (Universitat Pompeu Fabra, Barcelone) Constraint Satisfaction and Local-to-Global Consistency
The constraint satisfaction problem (CSP) is a general search problem where the input is a collection of constraints on a set of variables, and the question is to decide whether or not there is an assignment to the variables satisfying all of the constraints. It can be formalized as the problem of deciding whether or not a primitive positive sentence (a sentence using \{ \exists, \wedge \}) holds on a relational structure. Local-to-global consisency is an attractive and well-studied property for CSP instances: intuitively, this property holds when performing local (bounded-variable) inferences is sufficient to yield an explicit representation of the solution space. In this talk, I will engage in a discussion of local-to-global consistency on both finite structures and infinite structures (omega-categorical structures), and present the algorithmic consequences of this property for both the CSP and the quantified CSP. I will also report on recent work on this property in the context of temporal constraint languages. The speaker will attempt to give this presentation in a self-contained fashion, without requiring (for example) any prior knowledge of constraint satisfaction nor consistency.
Lundi 28 mars 2011 : Gönenç Onay (Paris 7 & Mimar Sinan, Istanbul) Modules valués affinement maximaux
Si K est un corps de caractéristique positive et L un sous-corps de K alors la structure de L-espace vectoriel de (K,+,0) avec l'action du morphisme Frobenius x---x^p s'exprime dans le langage des modules : (K,+,0) est un module sur l'anneau non-commutatif des polynomes tordus L[t;x--x^p]. On s'intéresse au cas où K est un corps valué. De manière un peu plus générale on introduira une notion de module valué et on définera pour ces modules la notion de henselianité et de maximalité provenant de la théorie des corps valués. Les modules valués présentent des phénomènes n'apparaissant pas dans les corps valués. Néansmoins il est possible d'avoir un théorème de type Ax, Kochen et Ershov pour les corps de Kaplansky algébriquement maximaux. Les définitions concernant les corps valués seront données durant l'exposé. L'exposé vise un public général.
Lundi 21 mars 2011 : Raf Cluckers (Université Lille 1 & K.U. Leuven) Nouveaux principes de transfert pour les intégrales motiviques
Dans Ann. of Math. 2010, nous avons demontré avec F. Loeser un premier principe de transfert pour les intégrales motiviques. Il concerne des égalités entre intégrales qui sont vraies sur les p-adiques Q_p si et seulement si elles sont vraies sur F_p((t)) et vice versa, pour chaque p qui est suffisamment grand. Dans un travail en cours avec Gordon et Halupczok, nous démontrons un deuxième principe de transfert concernant des conditions d'intégrabilité: une fonction (venant d'une fonction motivique) est intégrable sur Q_p si et seulement si elle l'est sur F_p((t)), bien sur de nouveau pour p grand. Si l'ancien principe de Ax et Kochen se base sur QE, nos principes de transfert utilisent beaucoup plus: la géometrie des fonctions définissables, théorie des nombres sur les sommes exponentielles, les transformations de Fourier, etc. Les deux principes de transfert donnent des résultats nouveaux dans le programme de Langlands. J'expliquerai tout pour un publique general.
Lundi 7 mars 2011 : Eric Jaligot (Institut Fourier, Grenoble) Sous-groupes de Cartan des groupes definissables dans les structure o-minimales
Un sous-groupe est dit de Cartan, au sens de Chevalley, s'il est nilpotent maximal et si chacun de ses sous-groupes normaux d'indice fini est presque auto-normalisant (dans le groupe ambiant). J'expliquerai pourquoi, dans tout groupe definissable dans une structure o-minimale, il n'y a qu'un nombre fini de classes de conjugaison de tels sous-groupes. On verra aussi que ces sous-groupes existent bien, et meme que leur reunion est un ensemble tres large du groupe ambiant.
Lundi 28 février 2011 : Anatole Khélif (IUFM Paris 7) Exemple de groupe abélien dénombrable G tel que G^aleph 0 et G^aleph 1 ne sont pas infini élémentairement équivalents
Nous donnons un exemple de groupe abélien dénombrable G tel que G^aleph 0 et G^aleph 1 ne sont pas infini élémentairement équivalents. La preuve utilise les complétions p-adiques de Z; le lien avec la propriété de Cantor Bernstein est évoqué. C'est le résultat d'un travail en collaboration avec Saharon Shelah.
Lundi 21 février 2011 : Heike Mildenberger (Universität Freiburg, Allemagne) The cofinality of the symmetric group and other cardinals
The group of permutions of the natural numbers can be written as an increasing chain of proper subgroups. The minimal length of such a chain is called the cofinality of the symmetric group. Its investigation is connected to the search for interesting types of subgroups, comparisons with other common cardinal characteristics of the real numbers and the computation of possible lengths in various models of set theory. There are some customised forcing extensions for increasing these lengths.
Lundi 14 février 2011 : Vincent Astier (University College Dublin) Equivalence élémentaire de treillis d'ouverts définissables
Si R est un corps o-minimal, on peut considérer odef(R^n) le treillis des ouverts définissables de R^n. Je vais essayer d'expliquer pourquoi il peut être intéressant de considérer ces objets, et pourquoi, si S est élémentairement équivalent à R, alors odef(R^n) et odef(S^n) sont élémentairement équivalents en tant que treillis.
Lundi 7 février 2011 : Piotr Kowalski (Wroclaw University & Université Paris Sud) Definable sets and transcendence
Ax's theorem provides definable conditions in differential fields of characteristic zero implying large transcendence degree. In the case of a field of positive characteristic, a derivation has to be replaced with a Hasse-Schmidt derivation. I will discuss different type-definable conditions in Hasse-Schmidt differential fields which still imply large transcendence degree.
Lundi 31 janvier 2011 : Menachem Magidor (Hebrew University, Jerusalem) On reflection properties and the Set Theory of generalized quantifiers
Reflection properties are an important motivation for new axioms of Set Theory. A typical reflection propery has the general form: If a structure has a certain property then there is a "small" substructure having the same property. Reflection properties can be also considered to be downwards Skolem Lowenheim Theorems for generalized logics. In the talk we shall survey some examples where the Set theory involved in analysing the strength of a given reflection property gives a way of classifying generalized logics and quantifiers.
Lundi 24 janvier 2011 : Jean-Louis Krivine (PPS) De nouveaux modèles de ZF
Il y a essentiellement deux façons de construire des modèles de
ZF et d'obtenir des résultats de consistance relative:
La constructibilité (plus généralement les modèles intérieurs)
Le forcing.
La technique de la "réalisabilité classique", mise au point pour
étudier la correspondance preuves-programmes, se révèle être un
troisième méthode, qui donne des modèles complètement différents
de la théorie des ensembles. En particulier, les ordinaux et même
les entiers sont changés.
On obtient, de cette façon, la consistance relative de ZF+DC +
certaines curieuses propriétés de R qui ne peut être montrée par
forcing.
Lundi 17 janvier 2011 : Salma Kuhlmann (Universität Konstanz) Hardy type derivations on fields of generalized series
We consider the valued field $K$ of generalised series (with real coefficients and monomials in a totally ordered multiplicative group $\Gamma$ ). We investigate how to endow $K$ with a series derivation, that is a derivation that satisfies some natural properties such as commuting with infinite sums (strong linearity) and (an infinite version of) Leibniz rule. We characterize when such a derivation is of Hardy type, that is, when it behaves like differentiation of germs of real valued functions in a Hardy field. (Joint work with Mickael Matusinski.)
Lundi 10 janvier 2011 : Françoise Point (FNRS - Mons & Equipe de logique) Ensembles definissables dans les corps topologiques differentiels
Apres un rapide survol de theories de corps differentiels toplogiques, je me concentrerai sur la theorie (CODF) des corps ordonnes differentiels existentiellement clos (axiomatisee par M. Singer). Je montrerai quelques proprietes des ensembles definissables dans les modeles de CODF, en utilisant notamment un resultat recent de Dolich, Miller et Steinhorn.
Lundi 13 décembre 2010 : Joan Bagaria (Universitat de Barcelona) Principles of Structural Reflection and the Hierarchy of Large Cardinals
Beginning in the mid 20th century, a number of prominent set theorists and philosophers have insistingly argued that any intrinsic justification of new set-theoretic axioms, beyond ZFC, and especially the axioms of large cardinals, should be based on strong forms of reflection for the universe V of all sets. However, some results of W. Tait, and more recently of P. Koellner, have definitely established the strong limitations of the reflection principles that have been proposed so far. In this talk we will consider a new form of reflection, Structural Reflection (SR), and will present some results showing that various natural forms of SR are exactly equivalent to some well-known large cardinal axioms, ranging from supercompact to Vopenka's Principle. (Exposé financé par le réseau européen MALOA PITN-GA-2009-238381.)
Lundi 6 décembre 2010 : Frank O. Wagner (ICJ, Université Lyon 1) Le dernier mot sur l'élimination des hyperimaginaires
Une théorie simple CM-triviale qui élimine les hyperimaginaires finitaires les élimine tous. En particulier, une théorie menue simple CM-triviale élimine les hyperimaginaires. Des pistes seront données pour éliminer l'hypothèse de CM-trivialité. (Travail en commun avec Daniel Palacin.)
Lundi 29 novembre 2010 : Paul-André Melliès (PPS) Démonstrations logiques et noeuds topologiques
Lorsque Frege définit son idéographie à la fin du XIXème siècle, il a pour ambition de penser le raisonnement logique comme un objet de nature mathématique, que l'on pourrait étudier de la même manière que l'on étudie un anneau ou une variété algébrique. Frege ouvre ainsi une quête captivante dans laquelle s'inscrira mon exposé: la recherche d'une écriture proprement mathématique des démonstrations logiques. Après un bref panorama historique des notations existantes, j'expliquerai comment tirer profit des travaux contemporains sur les invariants de noeuds et les catégories 2-dimensionnelles pour décrire les démonstrations logiques d'une manière nouvelle et très naturelle, dans des diagrammes de corde 3-dimensionnels. La vertu cardinale de cette notation est de révéler le flux logique produit par la circulation des négations dans la démonstration, et d'opérer ainsi une synthèse inédite entre sémantique des jeux et théorie de la démonstration.
Lundi 22 novembre 2010 : Gabriel Sabbagh (Equipe de logique) Puissances cartésiennes de groupes et équivalence élémentaire (travaux récents de Khélif et Shelah)
Soit G un groupe. Il est bien connu depuis plus de 50 ans que toutes les puissances par des ensembles infinis I et J de G sont élémentairement équivalentes. Assez récemment Jarden et Lubotzky ont démontré que pour un certain groupe abélien infini ces puissances étaient infini oméga équivalentes et je me suis souvenu qu'un résultat plus général avait été établi dans un vieil article de Paul Eklof et moi-même, ce qui a ranimé mon intérêt pour ce sujet et confirme qu'un article secondaire a en moyenne plus d'auteurs que de lecteurs. Diverses questions ont naturellement surgi ; Khélif et Shelah en ont résolu plusieurs. Le but de l'exposé est de présenter les plus simples de leurs résultats, dont la démonstration est du reste particulièrement intéressante, recoupe la démonstration « moderne » du théorème d'Ulm et introduit un outil qui devrait être utile ailleurs. L'exposé sera accessible à tout étudiant fréquentant Chevaleret et intéressé par la logique et on définira tout ce qu'il est utile de définir, y compris « infini oméga équivalents ». Cela est d'autant plus facile que les résultats en question, dont certains seront prochainement publiés dans les CRAS, auraient pu être établis il y a longtemps.
Lundi 15 novembre 2010 : Yann Strozecki (Equipe de logique) Décomposition de matroïdes pour la logique monadique du second ordre
Dans cet exposé on présente les matroïdes qui servent à abstraire la notion d'indépendance linéaire. Ils ont un intérêt particulier en math discrète car l'ensemble des cycles d'un graphe ou des colonnes d'une matrice forment un matroïde. On présente la logique monadique du second ordre qui est très expressive sur les matroïdes. Malheureusement celle-ci n'est même pas décidable sur les matroïdes représentable c'est à à dire venant d'une matrice. Dans la veine des résultats de décision de la logique MSO sur les mots et les arbres, on va montrer qu'elle est décidable en temps linéaire sur certaines classes de matroïdes qui admettent une bonne décomposition. On donnera quelques applications à la complexité de décision et d'énumération. On présentera également une vision générale des décompositions qui permettent de décider MSO efficacement sur des classes d'hypergraphes.
Lundi 25 octobre 2010 : Martin Bays (Equipe de logique) Schanuel conjectures for powers, and the CIT
Schanuel's conjecture in transcendence theory expresses the idea that complex exponentiation is in "general position" with respect to the algebro-geometric structure on the complex numbers. I will discuss how analogous statements, where exponentiation is replaced with the operation of raising to powers, can actually be proved when the powers in question are chosen to be sufficiently generic. I will also explain how a celebrated conjecture in number theory, the "Zilber-Pink conjecture for the multiplicative group", also known as the CIT, can be rephrased model theoretically as such a conjecture of Schanuel type for raising to non-standard integer powers. I will proceed to discuss the, as yet rather limited, applications of the first part of the talk to the second.
Lundi 18 octobre 2010 : Mirna Dzamonja (University of East Anglia, Norwich) Les axiomes du forcing et le successeur d'un cardinal singulier
Nous présentons l'histoire des axiomes du forcing et les difficultés que l'on a pour les axiomes du forcing sur un cardinal singulier. Nous proposons une solution, provenante d'un travail récent de Dz. et Shelah.
Lundi 11 octobre 2010 : Arnaud Durand (Equipe de Logique) Enumération de requêtes conjonctives et polymorphsime min
Dans cet exposé, on s'intéressera à l'énumération de requêtes c'est à dire la génération étapes par étapes des résultats de l'évaluation d'une formule sur une structure finie. La complexité de ces problèmes est évaluée dynamiquement en terme de délai entre deux solutions partielles. L'exposé, assez général, décrira au début les questions principales que l'on se pose dans le domaine de l'énumération de requêtes. Puis, on se concentrera plus précisément sur le cas des requêtes conjonctives (avec éventuellement des inégalités) et des structures stables par opérateur min (appelées X-underbar). Dans ce cadre, on fera aussi un rapide tour d'horizon des techniques utilisées pour "se débarrasser" avec un coût raisonnable des inégalités dans les formules (ou pour exhiber des homomorphismes injectifs entre structures finies), notamment la méthode du color-coding.
Lundi 27 septembre 2010 : Boban Velickovic (Equipe de Logique) Algèbres de Maharam et le problème de Von Neumann
Une algèbre de Maharam est une algèbre de Boole admettant une semi mesure continue. Ces algèbres ont été introduites et étudiées par Maharam dans les années 1940 en relation avec le problème de Von Neumann concernant la caractérisation des algèbres de mesure. La question à savoir si toute algèbre de Maharam est une algèbre de mesure, connue sous le nom 'Control Measure Problem', a été ouvert pendant 60 ans. Il a été finalement résolu en 2005 par Talagrand qui a donné un contrexemple. Dans cet exposé nous présenterons quelques résultats récents concernant les conditions proposées par Von Neumann : la faible distributivité et la condition d'antichaines dénombrables. En particulier, nous allons donner plusieurs caractérisations des algèbres de Maharam.
Lundi 20 septembre 2010 : Pierre Simon (ENS-Paris et Université Paris-Sud) Théories NIP et principe de réflexion de Shelah
Le "principe de réflexion de Shelah" stipule que, dans une théorie stable, les interactions entre un ensemble définissable D et le reste de la structure peuvent se lire à l'intérieur de D lui-même. Un ensemble de résultats tend à montrer que cette propriété s'étend à une classe plus grande : celle des théories NIP, qui comprend de nombreuses structures ordonnées (corps réels clos, corps valués...). Cet exposé sera une introduction aux théories NIP sous l'angle de ce principe de réflexion. Je présenterai aussi une application de ces idées à des résultats sur les paires de structures NIP (travail en commun avec A. Chernikov).
Lundi 13 septembre 2010 : John Baldwin (University of Illinois at Chicago) Complexity and Absoluteness in L_{\omega_1,\omega}
(Ce résumé est aussi disponible en PDF.)
Translation from a sentence of $L_{\omega_1,\omega}$ to an associated
atomic class is a key tool for the study of categoricity in infinitary
logic. We compare the complexity of definition of model theoretic notions
such as omega-stability and excellence for a sentence of
$L_{\omega_1,\omega}$ and the associated atomic class. We show these
properties are $\Sigma^1_2$ on the sentences and $\Pi^1_1$ on the
classes. (Lower bounds have not been established in the atomic class case).
In either case these properties are absolute. But the question of whether
$\aleph_1$-categoricity is absolute remains open for either formulation.
Connecting this study with more classical descriptive set theory we show
that the class of models of a sentence of $L_{\omega_1,\omega}$ whose
automorphism groups admit a complete left invariant metric is $\Pi^1_1$ but
not $\Sigma^1_1$. Techniques from model theory, recursion theory and
descriptive set theory are used. Much of this is joint work with David
Marker.