Séminaires : Séminaire Général de Logique
|
|
|
|
| Equipe(s) | Responsable(s) | Salle | Adresse |
|---|---|---|---|
| Logique Mathématique |
O. Finkel, T. Ibarlucía, A. Khélif, S. Rideau, C. Sureson |
salle 2015 | Sophie Germain |
| Titre | Date | Début | Orateur(s) | Salle | Adresse | |
|---|---|---|---|---|---|---|
| + | Higher amalgamation in measurable structures | 20/05/2019 | 15:10 | David Evans | ||
| Measurable structures were introduced by Macpherson and Steinhorn in 2008. Their definition abstracts certain properties of pseudofinite fields (following work of Chatzidakis, van den Dries and Macintyre) and has as a consequence that MS-measurable structures are supersimple of finite rank.
We give a higher amalgamation property which holds in MS-measurable structures (and more general contexts) which is a straightforward consequence of an infinitary formulation due to Towsner of the Hypergraph Removal Lemma. It is an open question whether omega-categorical MS-measurable structures are necessarily one-based. Hrushovski constructions could potentially give counterexamples, but it is not known whether these can be MS-measurable. However, as a consequence of the higher amalgamation result, we can at least give an example of an omega-categorical supersimple Hrushovski construction which is not MS-measurable. |
 | |||||
| + | Le plongement topologique et la réduction continue sur la première classe de Baire | 13/05/2019 | 15:10 | Raphaël Carroy | ||
| Une fonction entre espaces polonais de dimension zéro est de première classe de Baire lorsqu'elle est ponctuellement la limite d'une suite de fonctions continues. Cet exposé sera centré sur deux quasi-ordres entre fonctions de première classe de Baire: le plongement topologique et la réduction continue.
Un plongement topologique entre espaces est une injection continue dont la fonction inverse est également continue. Un plongement topologique d'une fonction $f$ dans une fonction $g$ est une paire $(a,b)$ de plongements topologiques vérifiant l'équation $b \circ f = g \circ a$. Une réduction continue de $f$ à $g$ est une paire $(a,b)$ de fonctions continues vérifiant l'équation $f = b \circ g \circ a$. On parlera de la complexité de ces deux quasi-ordres: on identifiera des sous-classes de fonctions sur lesquelles ils sont des bons-quasi-ordres, c'est à dire bien fondés et sans antichaînes infinies. On verra également que le plongement topologique n'est pas toujours un bon-quasi-ordre, dans certains cas il est en fait complet pour les quasi-ordres analytiques. |
| |||||
| + | De la descente infinie à la programmation avec des types (co)inductifs | 15/04/2019 | 15:10 | Alexis Saurin | ||
| La logique de la programmation s'est développée depuis la mise en évidence des liens étroits qu'entretiennent théorie de la démonstration et théorie de la programmation. La correspondance, dite de Curry-Howard, entre
1) formules logiques et types de données 2) preuves et programmes 3) élimination des coupures (ou normalisation de preuve) et exécution d'un programme a stimulé une intense activité visant à comprendre le contenu logique des structures de programmation et le contenu calculatoire des formes du raisonnement ou des axiomes logico-mathématiques et a renouvelé les perspectives sur la programmation comme sur la théorie de la démonstration. Dans cet exposé, on s'intéressera à diverses formes de raisonnements par induction, de la récurrence usuelle à la descente infinie, et aux systèmes de preuves qui les formalisent. Je considérerai notamment des logiques à points fixes (dérivées du mu-calcul, qui permettent d'exprimer aussi bien des enoncés inductifs que coinductifs), dans lesquelles j'étudierai des systèmes de preuves non bien-fondés où les dérivations sont des arbres potentiellement infinis (éventuellement réguliers). Je présenterai les principaux résultats de la théorie de la démonstration infinitaire (en particulier l'élimination des coupures), ses relations avec les preuves finitaires ainsi que des perspectives d'application à la programmation. |
| |||||
| + | Collapsing large ordinals | 08/04/2019 | 15:10 | Anton Freund | ||
| This talk discusses the power of "almost" order preserving collapsing functions, which map large ordinals (uncountable resp. non-recursive) to smaller ones (countable resp. recursive). More precisely, I will consider collapsing functions in the context of dilators (J.-Y. Girard): Let $D$ be a dilator, i.e. a particularly uniform function from ordinals to ordinals. It can happen that we have $D(\alpha)>\alpha$ for every ordinal $\alpha$, so that $D$ has no fixed-point. The best we can expect is a collapsing function $D(\alpha)\rightarrow\alpha$ that is almost order preserving, in a sense that will be made precise in the talk. If such a function exists, then $\alpha$ is called a Bachmann-Howard fixed-point of $D$. I will show that the following holds over a weak base theory: The statement that "every dilator has a Bachmann-Howard fixed-point" is equivalent to the existence of admissible sets, and hence to $\Pi^1_1$-comprehension (full details can be found in arXiv:1809.06759). |
| |||||
| + | Expansions de corps dp-minimaux avec une derivee et applications aux theories de paires denses de corps | 25/03/2019 | 15:10 | Françoise Point | ||
| L'etude des corps topologiques differentiels est traditionnellement divisee en deux branches, l'une traite le cas ou il y a une interaction (forte) entre la derivee et la topologie et l'autre ou le comportement de la derivee sera generique. Nous nous placons dans ce dernier cas. Sous certaines conditions sur une theorie modele-complete de corps topologiques, on peut axiomatiser la theorie T^*_D de la classe des expansions differentielles existentiellement closes.
Le but de l'expose est d'expliquer quelques resultats de transferts entre T et T^*_D et de montrer comment les appliquer aux theories de paires denses de modeles de T. Il s'agit d'un travail en commun et en cours avec Pablo Cubides (Dresden). |
| |||||
| + | Des preuves aux programmes, aux systèmes dynamiques. Perspectives géométriques en complexité algorithmique | 18/03/2019 | 15:10 | Thomas Seiller | ||
| La question de la séparation des classes de complexité fait actuellement face à un manque cruel de méthodes. En effet, de nombreux résultats, appelés barrières, démontrent que les méthodes de preuve connues ne permettront pas de répondre aux questions ouvertes principales. Le principal programme de recherche qui pourrait circonvenir aux barrières est le programme de complexité géométrique de K. Mulmuley. Celui-ci propose de montrer des résultats de séparation via des techniques de géométrie algébrique, et a été introduit après l'obtention d'un résultat de bornes inférieures une variante algébrique de PRAMs, un modèle de machines parallèles ad-hoc.
Cet exposé expliquera comment certaines méthodes récentes venant de la logique permettent de proposer une nouvelle approche à la question de la séparation. Basée sur une interpretation dynamique des programmes, celle-ci suggère une correspondance entre l'expressivité des modèles de calcul étudiés et certains invariants venant de théorie ergodique. Je présenterai également un travail en collaboration avec L. Pellissier, qui a consisté à relire la preuve de séparation ayant inspiré le programme de complexité géométrique via ce nouveau point de vue, faisant apparaitre le rôle de l'entropie topologique des systèmes dynamiques associés aux machines. Au-delà de renforcer l'intuition d'une correspondance entre classes de complexité et certaines classes de systèmes dynamiques, cette abstraction du résultat nous permet également de renforcer le résultat de séparation pour montrer que le problème maxflow (problème complet pour la classe P) n'est pas calculable efficacement par une machine parallèle travaillant avec des entiers. |
| |||||
| + | Isolation, compression schemes, and density of compressibility | 11/03/2019 | 15:10 | Martin Bays | ||
| In model theory, various notions of isolation - ways in which the full information of a type may be determined by a fragment of it - have been important tools for the analysis and classification of models of a theory. Meanwhile, much has been written in machine learning theory on sample compression schemes - ways to code information on a concept in a bounded part.
These related ideas came together in work of Chernikov and Simon on NIP and distal theories, where they found in particular that a theory is distal precisely when every type satisfies a certain isolation notion, termed "compressibility". A model-theoretically natural question to ask of such an isolation notion is whether isolated types are dense in the natural topological space of types. Meanwhile, a recent result of Chen, Cheng, and Tang provides a strong form of compression scheme for a finite concept class, bounded in terms of its VC dimension. In work joint with Itay Kaplan and Pierre Simon, we give a certain generalisation of this last result to infinite concept classes, and use it to obtain density of compressible types in countable NIP theories. |
| |||||
| + | Symmetry and Self-Similarity in the Higher Infinite | 04/03/2019 | 15:10 | Joan Bagaria | ||
| The Higher Infinite is the realm of the Large Cardinals, namely very large infinite cardinal numbers with strong combinatorial properties and whose existence cannot be proved from the standard Zermelo-Fraenkel axioms of set theory with Choice (ZFC). Large cardinal axioms of set theory assert the existence of such cardinals, which form a hierarchy that measures the consistency strength of mathematical theories. In this talk we will present some results, some old as well as some recent ones, that point to a unified view of the large cardinal hierarchy in terms of symmetry and self-similarity of the set-theoretic universe. |
| |||||
| + | Diophantine sets of number fields and their rings of integers --- à 16h en salle 1016 | 25/02/2019 | 16:00 | Hector Pasten | ||
| A subset of a ring is diophantine if it is positive existentially definable in the language of rings. In number fields or in their rings of integers, every diophantine set is listable (i.e. recursively enumerable) and one can ask whether every listable set is diophantine. For instance, a classical theorem of Davis, Matiyasevic, Putnam, and Robinson shows that for the usual integers Z the answer is positive. I will discuss some general conjectures and some partial results suggesting that in the number field case not every listable set is diophantine, while in the case of rings of integers every listable set should be diophantine.
|
| |||||
| + | Meta-iteration trees and mouse pairs | 18/02/2019 | 15:10 | Benjamin Siskind | ||
| The fundamental objects of study in inner model theory are iterable premice---fine-structual models of set theory which have winning strategies in certain iteration games. In the standard iteration game, two players work to produce an iterate N of a premouse M via a tree of iterated ultrapowers called a normal iteration tree. In a variant game, players produce an iterate N not via a single iteration tree but via a linear stack of normal trees. Recent work has revealed connections between these games, which have various applications in inner model theory. The key framework for understanding these connections is the theory of meta-iteration trees: iteration trees of iteration trees. Using this framework, we show that any nice winning strategy S in the standard game extends to a winning strategy S* in the variant game. Moreover, every iterate N obtainable via a play by S* in the variant game is actually obtainable via a play by the original strategy S. This is joint work with John Steel.
|
| |||||
| + | Jeux de gabarit: un modèle homotopique et interactif de la logique linéaire différentielle | 04/02/2019 | 15:10 | Paul-André Melliès | ||
| La sémantique des jeux permet de décrire toute formule logique comme un jeu de dialogue et toute démonstration comme une stratégie interactive. Dans cet exposé introductif, j'expliquerai comment la notion de jeu de gabarit est née du désir de mieux comprendre la structure algébrique et combinatoire en espace et en temps de la sémantique des jeux. Mon exposé sera organisé en trois parties. J'expliquerai tout d'abord ce qu'est un modèle catégorique de la logique linéaire différentielle formulée par Thomas Ehrhard. Je décrirai ensuite le modèle des distributeurs et espèces généralisées formulé il y a dix ans par Marcelo Fiore, Nicola Gambino, Martin Hyland and Glynn Winskel, et les liens que ce modèle entretient avec la notion d'opérade en topologie algébrique. Je conclurai en décrivant le modèle des jeux de gabarit, et en expliquant les raisons pour lesquelles on doit faire interagir les démonstrations logiques modulo une notion d'homotopie, formulée dans le cadre des catégories modèles de Quillen. |
| |||||
| + | Structures dont l'anneau de Grothendieck est $\mathbb{Z}/N\mathbb{Z}$ | 28/01/2019 | 15:10 | Esther Elbaz | ||
| Les anneaux de Grothendieck ont été introduits en théorie des modèles au début des années 2000. Ils sont une généralisation de la notion d'anneau de Grothendieck connue en géométrie algébrique. Il existe un parrallèle entre mes propriétés combinatoires d'une structure et les propriétés algébriques de son anneau de Grothendieck. Ces anneaux apparaissent également en intégration motivique, où ils sont utilisés pour exprimer de manière uniforme les formules de certaines fonctions de comptage.
On peut se demander quels anneaux peuvent apparaître comme anneaux de Grothendieck. On ne savait pas jusque récemment, s'il en existait de finis. Dans cet exposé, nous montrerons que pour tout nombre entier $N$, nous allons construire une théorie dont tous les modèles admettent $\mathbbZ/N \mathbbZ$ comme anneau de Grothendieck. |
| |||||
| + | Roots of exponential polynomials | 21/01/2019 | 15:10 | Paola d'Aquino | ||
| Zilber identifies a new class of exponential fields (pseudo-exponential fields), and proves a categoricity result for every uncountable cardinality. He conjectures that the classical complex exponential field is the unique model of power continuum. Some of the axioms of Zilber have a geometrical nature and they guarantee solvability of systems of exponential equations over the field. In the last 15 years much attention has been given to extend classical results for the complex exponential field to the pseudo-exponential fields, and vice versa much effort has been put in proving for the complex field properties of solutions of exponential polynomials which follow from the axioms of Zilber. Analytic methods have been substituted by algebraic and geometrical arguments. I will review some of the first results on this and I will present more recent ones obtained in collaboration with A. Fornasiero and G. Terzo
|
| |||||
| + | Logic and Cech-Stone remainders | 14/01/2019 | 15:10 | Alessandro Vignati | ||
| We study the properties of Cech-Stone remainder spaces, spaces of the form beta X minus X for a locally compact X where beta X denotes the Cech-Stone compactification of X. We focus on how logic interacts with the study of these objects. We approach such spaces both model theoretically, by looking at the continuous model theory of the C*-algebra of complex valued functions on beta X minus X, and set theoretically, by arguing that their homeomorphism structure depends on the axioms in play. |
| |||||
| + | On Extended Constructibility | 10/12/2018 | 15:10 | Juliette Kennedy | ||
| If we replace first order logic by second order logic in the original definition of Gödel’s inner model L, we obtain HOD (result due to Myhill-Scott). In this talk after giving some historical background we consider inner models that arise if we replace first order logic by a logic that has some, but not all, of the strength of second order logic. Typical examples are the extensions of first order logic by generalized quantifiers, such as the Magidor-Malitz quantifier ([21]), the cofinality quantifier ([32]), or stationary logic ([6]). Our first set of results show that both L and HOD manifest some amount of robustness in the sense that they are not very sensitive to the choice of the underlying logic. Our second set of results shows that the cofinality quantifier gives rise to a new robust inner model between L and HOD. We show, among other things, that assuming a proper class of Woodin cardinals the regular cardinals above \aleph_1 of V are weakly compact in the inner model arising from the cofinality quantifier and the theory of that model is (set) forcing absolute and independent of the cofinality in question. |
| |||||
| + | Calculer avec le théorème de complétude de Gödel | 03/12/2018 | 15:10 | Hugo Herbelin | ||
| Dans un premier temps, nous donnerons une analyse du contenu calculatoire de la preuve de Henkin du théorème de complétude (dans le cas d'une théorie récursivement énumérable).
Dans un deuxième temps, on s'intéressera à la traduction de forcing de l'énoncé de complétude pour s'apercevoir qu'on obtient alors un énoncé de complétude vis à vis des modèles de Kripke. En ré-interprétant la preuve standard de complétude vis à vis des modèles de Kripke en style direct (dans le même sens où la logique classique est un « style direct » pour raisonner intuitionnistiquement au travers des traductions négatives de Kolmogorov-Gödel-Gentzen), on obtiendra une preuve originale et calculatoire très simple du théorème de complétude... mais qui utilise une allocation mémoire ! |
| |||||
| + | Forcing, réalisabilité classique et propriétés de préservation | 26/11/2018 | 15:10 | Hadrien Batmalle | ||
| La réalisabilité classique est une technique d'interprétation des énoncés d'une théorie par des programmes. Elle permet de construire des modèles et apparaît comme une généralisation du forcing. Si l'interprétation de théorèmes par des programmes a un intérêt évident en informatique, l'étude des modèles de ZF obtenus par réalisabilité classique est aussi intéressante en soi: en effet, sauf dans les cas dégénérés, ces modèles sont très différents des modèles de forcing; par exemple ils ne conservent pas les ordinaux. Cela permet d'exhiber des propriétés pathologiques qu'on ne savait pas obtenir précédemment (on a donc un outil supplémentaire pour les preuves d'indépendance) mais présente aussi de nouvelles difficultés. En particulier, si on sait bien souvent en forcing quels sont les critères que doit vérifier la structure des conditions pour obtenir telle ou telle propriété dans le nouveau modèle, la réalisabilité est, pour le moment, beaucoup plus difficile à aborder. On présentera ici quelques
techniques récentes de réalisabilité classique à rapprocher de techniques bien connues en forcing: l'opérateur de bar-récursion, qui joue un rôle analogue aux ensembles de conditions omega-clos (Krivine 2014) et un nouveau résultat de transfert de propriétés du modèle de départ qui est utilisé dans les mêmes situations que des critères de type conditions d'antichaîne. On appliquera ce dernier résultat à la construction de modèles de réalisabilité pour la négation du choix dénombrable et la négation de l'hypothèse du continu, et donc de programmes réalisant ces énoncés. |
| |||||
| + | Les séries d'arbres et la complexité algébrique | 19/11/2018 | 15:10 | Guillaume Malod | ||
| Un résultat de Nisan de 1991 donne une caractérisation exacte de la complexité de calcul d'un polynôme non-commutatif par un modèle appelé branching program, via les rangs de certaines matrices. Fijalkow, Lagarde, Ohlmann et Serre ont récemment remarqué que ces résultats étaient en fait des cas particuliers de théorèmes sur les séries formelles de mots et d'arbres et ont cherché à les exploiter ceux-ci pour les appliquer à la complexité algébrique.
J'essaierai de faire une présentation synthétique de ces différents résultats. |
| |||||
| + | Anneaux et groupes dimensionnels | 12/11/2018 | 15:10 | Frank Wagner | ||
| Je définirai une notion générale de dimension sur les ensembles interprétables d'une structure, et j'analyserai les anneaux et groupes qui peuvent être munis d'une telle dimension. |
| |||||
| + | Sur la sémantique des langages de programmation probabilistes | 05/11/2018 | 15:10 | Thomas Ehrhard | ||
| La sémantique dénotationnelle, introduite par Scott et Strachey à la fin des années 1960, consiste à interpréter les programmes par des fonctions définies sur des "domaines" qui sont le plus souvent des ensembles partiellement ordonnés dans lesquels, intuitivement, un élément est d'autant plus grand qu'il est plus défini. On présentera une sémantique dénotationnelle des programmes probabilistes basée sur les "espaces cohérents probabilistes" dans laquelle les programmes sont interprétés par des fonctions analytiques dont toutes les dérivées sont positives, on donnera des exemples et on présentera diverses propriétés de ce modèle (adéquation, pleine abstraction etc). |
| |||||
| + | Ingrédients modèle-théoriques dans la preuve de la conjecture de Mordell-Lang | 29/10/2018 | 15:10 | Frank Benoist | ||
| La preuve de la conjecture de Mordell-Lang pour les corps de fonctions par Hrushovski en 1996 constitue un exemple marquant d'application des méthodes de la théorie des modèles à la géométrie algébrique. Depuis, dans un travail commun avec Elisabeth Bouscaren et Anand Pillay, nous avons donné une preuve, se voulant plus abordable, de ce résultat, par réduction à la conjecture (démontrée) de Manin-Mumford. J'expliquerai les relations entre ces deux énoncés et présenterai les outils et méthodes de théorie des modèles qui interviennent dans la preuve. L'exposé se veut accessible aux non-spécialistes.
|
| |||||
| + | The special $\aleph_2$-Aronszajn tree property and GCH | 15/10/2018 | 15:10 | David Aspero | ||
| Assuming the existence of a weakly compact cardinal, we build a forcing extension in which GCH holds and every $\aleph_2$-Aronszajn tree is special. This answers a well-known question from the 1970's. I will present the proof of this theorem, with as many details as possible. This is joint work with Mohammad Golshani.
|
| |||||
| + | An invitation to dependence logic | 08/10/2018 | 15:10 | Jouko Vaananen | ||
| I will give an introduction to dependence logic and to the team semantics on which it rests. Dependence logic is an inquiry into the first order and algorithmic properties of dependence and independence relations in mathematics, statistics and computer science. I will discuss connections to model theory, database theory, quantum physics, social choice and set theory. It is perhaps surprising that the opposite of dependence is not independence, but rather anonymity or privacy, extending the investigation into another notoriously important field. |
| |||||
| + | L'exposé est reporté à une date ultérieure - Uniform Roe algebras and rigidity, part II | 24/09/2018 | 15:10 | Alessandro Vignati | ||
| This talk is the second part of Farah's talk from two weeks ago. From a coarse metric space X one associates a C*-algebra known as the Uniform Roe algebra of X. This algebra has a canonical quotient called the Uniform Roe corona of X. We study the question of what information on spaces X and Y one can infer when the Uniform Roe coronas of X and Y are isomorphic, and how answers to this question depend on the set theoretical axioms in play. This is joint work with Bruno Braga and Ilijas Farah. |
| |||||
| + | Bernoulli disjointness | 17/09/2018 | 15:10 | Andrew Zucker | ||
| Building on recent work of Glasner and Weiss, we will consider a countable group G and define the notion of disjointness between two G-flows X and Y. We then consider the question of when every minimal flow is disjoint from the Bernoulli shift. Time permitting, we will discuss an application of these ideas to an old problem in topological dynamics due to Ellis and/or Furstenberg.
|
| |||||
| + | Uniform Roe algebras and rigidity | 03/09/2018 | 15:10 | Ilijas Farah | ||
| I will start by defining the coarse equivalence of metric spaces. This is an equivalence relation meant to capture the large scale geometry of a given space.
To a coarse metric space one can associate a C*-algebra called uniform Roe algebra. When does isomorphism of uniform Roe algebras associated imply coarse equivalence of the underlying coarse spaces? A recent result of Spakula and Willett gives sufficient conditions in the case of coarse metric spaces. These conditions are uniform discreteness and property A (the ‘coarse’ variant of amenability). I will discuss a weakening of these conditions. Very recently, these rigidity results were extended to Roe coronas (quotients of uniform Roe algebras modulo the compact operators). No previous knowledge of coarse spaces, Roe algebras, or logic is required. (This is a joint work with Bruno De Mendoca Braga and Alessandro Vignati.) |
| |||||
| + | Global Structure Theorems for the space of measure preserving transformations | 02/07/2018 | 15:10 | Matthew Foreman | ||
| In joint work with B. Weiss we show that there is a very large class of ergodic transformations (a “cone” under the pre-ordering induced by factor maps) whose joining structure is identical to another class, the “circular systems”. The latter class is of interest because every member can be realized as a Lebesgue-measure preserving diffeomorphism of the torus T^2.
Using this theorem, we are able to conclude that the joining structure among diffeomorphisms includes that of a cone of diffeomorphisms. This solves several well-known problems such as the existence of ergodic Lebesgue measure preserving diffeomorphisms with an arbitrary compact Choquet simplices of invariant measures and the existence of measure-distal diffeomorphisms of T^2 of height greater than 2. (In fact we give examples of arbitrary countable ordinal height.) As a bonus result we give a class of diffeomorphisms T of the torus “Godel's diffeomorphisms” for which T being isomorphic to T^-1 is independent of ZFC. |
| |||||
| + | Types Quantitatifs: Fondements et Applications | 04/06/2018 | 15:10 | Delia Kesner | ||
| Des techniques quantitatives émergent aujourd'hui dans différents domaines de l'informatique pour faire face aux défis posés par le calcul sensible à la consommation des ressources.
Dans cet exposé on discutera de la pertinence de la théorie des types quantitatifs associés aux langages de programmation d'ordre supérieur (avec filtrage, opérateurs de contrôle, réductions infinis). En commençant par l'exemple phare du lambda-calcul, on présentera ses fondements, des extensions puissantes et plusieurs applications intéressantes. |
| |||||
| + | High Davies-trees in infinite combinatorics | 07/05/2018 | 15:10 | Daniel Soukup | ||
| The goal of this talk is to explore a general method based on trees of elementary submodels which can be used to highly simplify proofs to numerous results in infinite combinatorics. While countable elementary submodels have been employed in such settings already, we also present the corresponding technique with countably closed models of size continuum. The applications range from various theorems on paradoxical decompositions of the plane, to coloring sparse set systems, results on graph chromatic number and constructions from point-set topology. Our main purpose is to demonstrate the ease and wide applicability of this method in a form accessible to anyone with a basic background in set theory and logic. |
| |||||
| + | Théorie de Ramsey sans principe des tiroirs, et propriété de Ramsey adverse | 05/03/2018 | 15:10 | Noé de Rancourt | ||
| La théorie de Ramsey de dimension infinie est une branche de la théorie de Ramsey dans laquelle on cherche à obtenir des sous-structures homogènes de structures données lorsqu'on colorie des suites infinies d'éléments de cette structure. Son théorème fondateur est le théorème de Galvin-Prikry, mais de nombreux théorèmes similaires ont été démontrés par la suite. Tous reposent sur un principe des tiroirs, c'est-à-dire un résultat dans lequel on colorie non pas des suites de points, mais seulement des points.
Le premier résultat de type Ramsey sans principe des tiroirs a été démontré par Gowers dans les années 90, dans le cadre des espaces de Banach. L'abandon du principe des tiroirs a un prix : on ne peut pas obtenir de sous-structures réellement homogènes mais seulement des sous-structures qui le sont "presque", le "presque" étant ici exprimé en terme de jeux. Dans cet exposé, je présenterai un théorème de type Ramsey sans principe des tiroir dans un cadre abstrait, généralisant à la fois le théorème de Galvin-Prikry et celui de Gowers. Ce résultat motivera l'introduction de la propriété de Ramsey stratégique, une propriété des ensembles de suites d'entiers qui, dans ZFC, est satisfaite par tous les ensembles analytiques. J'introduira par la suite la propriété de Ramsey adverse, une propriété généralisant à la fois la propriété de Ramsey stratégique et la détermination des jeux sur les entiers. En terme d'implications, cette propriété se situe entre la détermination des jeux sur les réels et celle des jeux sur les entiers, mais on ne sait pas exactement où ; j'énoncerai quelques résultats concernant la propriété de Ramsey adverse pour les ensembles projectifs sous des hypothèses supplémentaires de théorie des ensembles, qui permettront de mieux la situer. |
| |||||
| + | Borel complexity and potential canonical Scott sentences | 26/02/2018 | 15:10 | Chris Laskowski | ||
| Given a first order theory or a sentence $\Phi$ of $L_\omega_1,\omega$, we define the class of potential canonical Scott sentences of $\Phi$. Simply by comparing cardinalities, we obtain new results about the Borel complexity of $(Mod(\Phi),\iso)$, the class of countable models of $\Phi$. In particular, we find examples of first order theories T for which Mod(T) is not Borel complete, yet the isomorphism relation on Mod(T) is not Borel.
This is joint work with Douglas Ulrich and Richard Rast. |
| |||||
| + | Definably amenable groups and the fixed point property | 19/02/2018 | 15:10 | Rafael Zamora | ||
| We proved an analogue of the fixed point property for definably amenable groups. This work is joint with J.F. Carmona, K. Davila and A. Onshuus. |
| |||||
| + | Abstract Algebraic Theory of Quadratic Forms and Rings (joint work with M. Dickmann) | 12/02/2018 | 15:10 | Francisco Miraglia | ||
| Let A be a commutative unitary semi-real (– 1 is not a sum of squares) ring in which 2 is a unit; let T = A^2 or a proper preorder of A. We shall describe first order axioms such that if the pair (A, T) is a model of these statements, then there is a special group, G_T(A), naturally associated to (A, T), faithfully coding the T-theory of diagonal quadratic forms with unit coefficients in A. Under mild restrictions, these axioms are necessary and sufficient for G_T(A) to faithfully code representation and T-isometry of non-singular diagonal quadratic forms with coefficients in A.
We shall present significant classes of rings satisfying these axioms and establish interesting results concerning the behavior of quadratic form theory over these classes of rings. The needed concepts will be presented during the talk, which contains only part of the results published in: M. Dickmann, F. Miraglia, Faithfully Quadratic Rings, Memoirs of the AMS, 1128, (November 2015). |
| |||||
| + | Vers une reconstruction pour des théories non aleph0-catégoriques | 20/11/2017 | 15:10 | Itaï Ben Yaacov | ||
| Soit T une théorie a0-catégorique, et G(T) le groupe d'automorphismes d'un modèle dénombrable (ou séparable, en logique continue), muni de la topologie de la convergence simple. Nous savons depuis longtemps que
1. Deux théories a0-catégoriques T, T' sont bi-interprétables ssi G(T) et G(T') sont isomorphes en tant que groupes topologiques. 2. Un groupe topologique G est (isomorphe à) un G(T), en logique classique (continue), ssi G est un groupe Polonais oligomorphe (Roelcke précompact). Le 2 est un résultat de « reconstruction » : à partir d'un groupe topologique ayant une propriété abstraite, on produit une théorie, qui est d'ailleurs essentiellement unique. De surcroît, des propriétés modèle-théoriques de la théorie (stabilité, NIP) sont équivalentes à des propriétés dynamiques du groupe. Comme la stabilité ou NIP ont un sens pour les théories non a0-catégoriques, la question d'une généralisation de cette correspondance se pose. Je propose une approche qui consiste à associer à une théorie non pas un groupe, mais un groupoïde topologique. En particulier, à partir de ce groupoïde on peut récupérer une théorie bi-interprétable avec la théorie du départ. Ceci est une toute première étape dans un travail en cours, la suite duquel pourrait être le problème de thèse de mon étudiant Mangraviti. |
| |||||
| + | Notions de clôtures aux différences de corps aux différences. | 13/11/2017 | 15:10 | Zoé Chatzidakis | ||
| Un corps aux différences est un corps avec un automorphisme distingué. La modèle compagne de leur théorie, ACFA, est supersimple. En analogie avec ce qui se passe pour les corps différentiels de caractéristique 0 et la théorie DCF0, on peut se demander si les modèles premiers (d'ACFA) existent et sont uniques à isomorphisme près.
Je donnerai d'abord les raisons évidentes pour une réponse négative. Puis j'investiguerai la question si sur certains corps aux différences il existe des modèles premiers uniques, et là encore, donnerai un contre-exemple. Il se trouve cependant qu'en regardant d'autres notions de clôtures, provenant de notions de modèles aleph-epsilon saturés ou kappa-saturés, et en imposant une condition naturelle au corps de base K, on peut montrer que les modèles aleph-epsilon premiers (ou kappa-premiers) existent et sont uniques à K-isomorphisme près. Ce résultat est faux en caractéristique positive. |
| |||||
| + | Densité forte des types définissables | 06/11/2017 | 15:10 | Pablo Cubides Kovacsics | ||
| Récemment, l'importance de la densité des types définissables a été relevée par différentes preuves de l'élimination des imaginaires dans les corps valués algébriquement clos. Dans cet exposé, on introduira des variantes de cette propriété et on donnera des exemples de théories les satisfaisant. Comme application, on obtiendra une preuve de l'élimination des imaginaires de la théorie des corps ordonnés différentielement clos (CODF). Il s'agit d'un travail un commun avec Quentin Brouette et Françoise Point.
|
| |||||
| + | Application of logic to C*-algebras | 23/10/2017 | 15:10 | Alessandro Vignati | ||
| We survey through some of the most recent applications of logic to C*-algebras. In particular we introduce the basics of the model theory of C*-algebras and we survey through the different layers of saturation certain algebras can have. Finally, we exploit some of the connections between saturation and the structure of automorphisms of reduced product C*-algebras.
This will be a logician-friendly talk: no advanced knowledge of C*-algebras is needed. |
| |||||
| + | Around the model theory of modular invariants. | 16/10/2017 | 15:10 | Andrés Villaveces | ||
| The model theoretic analysis of the j-function has taken two apparently different paths in recent years. One of these has been inspired by arithmetic geometric considerations, has been done in infinitary logic and has produced some categoricity results (Harris). The other one (due initially to Freitag and Scanlon, later Aslanyan) has focused on the differential equations satisfied by the j-function. I will describe these two approaches, as well as some recent lines of generalization. The last part is joint work with Alex Cruz.
|
| |||||
| + | Introduction aux mathématiques à rebours | 09/10/2017 | 15:10 | Ludovic Patey | ||
| Les mathématiques à rebours sont un domaine fondationnel qui vise à trouver les axiomes optimaux pour prouver les théorèmes de la vie de tous les jours. Elles se placent dans l'arithmétique du second ordre, avec une théorie de base, RCA, capturant informellement les "mathématiques calculables". Nous reviendrons sur les justifications historiques des mathématiques à rebours, présenterons ses principales observations, ainsi que l'approche moderne des mathématiques à rebours comme formalisme de classification de phénomènes calculatoires. |
| |||||
| + | inp-minimal groups | 02/10/2017 | 15:10 | Jan Dobrowolski | ||
| We will discuss some topics related to inp-minimal groups, including a sketch of the proof of the joint result with J. Goodrick stating that every left-ordered inp-minimal group is abelian (which generalizes P. Simon's result about bi-ordered groups). |
| |||||
| + | Menger compacta as projective Fraisse limits with emphasis on dimension one | 29/05/2017 | 15:10 | Slawomir Solecki | ||
| In each dimension d, there exists a canonical compact, second countable space, called the d-dimensional Menger space, with certain universality and homogeneity properties. For d = 0, it is the Cantor set, for d = infinity, it is the Hilbert cube. I will concentrate on the 1-dimensional Menger space. I will prove that it is a quotient of a projective Fraisse limit. I will describe how a property of projective Fraisse limits coming from Logic, called the projective extension property, can be used to prove high homogeneity of the 1-dimensional Menger space.
This is joint work with Aristotelis Panagiotopoulos. |
| |||||
| + | L'arithmétique de Skolem et ses extensions | 22/05/2017 | 15:10 | Alexis Bès | ||
| L'arithmétique de Skolem est la théorie du premier ordre des entiers naturels munis de la multiplication (sans l'addition). Cet exposé proposera un aperçu des principaux résultats de décidabilité autour de (N,*) et ses extensions, ainsi que des liens avec les automates. On présentera d'abord la preuve par Mostowski de la décidabilité de (N,*), basée sur les produits de structures et la décidabilité de l'arithmétique de Presburger, puis la preuve de Hodgson, basée sur les automates. On montrera ensuite comment la notion de produit généralisé introduite par Feferman et Vaught permet d'obtenir des extensions décidables de (N,*), comme par exemple (N,*,"x et y ont autant de diviseurs premiers") ou (N,*,"x et y sont premiers et x < y"). On verra enfin que ce dernier exemple (dû à F.Maurin), conduit à une notion naturelle d'automate pour les mots sur un alphabet infini. |
| |||||
| + | Infinite constraint satisfaction problems | 15/05/2017 | 15:10 | Joanna Ochremiak | ||
| We study the homomorphism problem for infinite relational structures which can be defined by finitely many first-order formulas over the natural numbers with equality. We determine the decidability status of this problem depending on whether the signature or/and the number of tuples in a single relation are allowed to be infinite.
Joint work with Bartek Klin, Eryk Kopczyński, Sławek Lasota and Szymon Toruńczyk. |
| |||||
| + | Mesures invariantes d'homéomorphismes minimaux | 27/03/2017 | 15:10 | Julien Melleray | ||
| Je reviendrai sur une caractérisation, due à Ibarlucia et moi-même, des ensembles de mesures invariantes d'homéomorphismes minimaux d'un espace de Cantor, et examinerai la question de savoir si cette caractérisation peut être simplifiée (en supprimant une des hypothèses dite de "divisibilité approximative"). J'expliquerai pourquoi cette caractérisation fait apparaître un lien avec de la théorie de Fraïssé et discuterai quelques questions ouvertes (selon le temps). |
| |||||
| + | Polynomial Identity Testing of Sum of ROABPs | 20/03/2017 | 15:10 | Arpita Korwar | ||
| Polynomials are fundamental objects in mathematics. Though univariate polynomials are fairly well-understood, multivariate polynomials are not. Arithmetic circuits are the primary tool used to study the complexity of polynomials in computer science. They allow for the classification of polynomials according to their complexity.
Polynomial identity testing (PIT) asks if a polynomial, input in the form of an arithmetic circuit, is identically zero. One special kind of arithmetic circuits are read-once arithmetic branching programs (ROABPs), which can be written as a product of univariate polynomial matrices over distinct variables. We will be studying the characterization of an ROABP. In the process, we can give a polynomial-time PIT for the sum of constantly many ROABPs. |
| |||||
| + | Quelques applications de l’axiome de Martin aux espaces de Banach | 13/03/2017 | 15:10 | Gilles Godefroy | ||
| L’axiome de Martin est un axiome qu’on peut ajouter aux axiomes de ZFC, qui est compatible avec la négation de l’hypothèse du continu et qui a pour effet de "pousser vers le dénombrable" tous les cardinaux inférieurs au continu. La théorie des espaces de Banach non séparables est assez différente suivant qu’on accepte, ou non, cet axiome. Nous verrons cela sur quelques exemples simples, qui ont en commun que l’axiome de Martin permet de construire des systèmes (presque) biorthogonaux transfinis. |
| |||||
| + | A solution to a problem of von Neumann | 06/03/2017 | 15:10 | Matthew Foreman | ||
| In 1932 von Neumann proposed classifying the statistical behavior of diffeomorphisms of manifolds. In modern language this is restated as classifying the equivalence relation of measure theoretic isomorphism. The main theorem in this talk is that the classification problem is impossible. The equivalence relation is not Borel. As part of the proof a “Global Structure Theorem” is proved that settle a couple of open questions about another classical problem, the “realization problem.” This is joint work with B. Weiss.
|
| |||||
| + | La Conjecture de Zilber et ses contre-exemples | 27/02/2017 | 15:10 | Isabel Müller | ||
| Dans une tentative de classer la géométrie des ensembles fortement minimaux, Zilber les avait conjecturés pour se diviser en trois types différents: Les géométries triviales, les géométries qui ressemblent à des espaces vectoriels et ceux qui ressemblent à des corps. Hrushovski a ensuite réfuté cette conjecture en introduisant une construction intelligente qui avait été modifiée et utilisée beaucoup depuis. Son contre-exemple à la conjecture de Zilber a fourni une structure, qui n'était pas monobasée, donc ne pouvait pas être de type trivial ou de type espace vectoriel, mais elle interdisait une certaine configuration point-ligne-plan qui est toujours présente dans les corps. Hrushovski appela cette propriété CM-trivial et plus tard Pillay, avec quelques corrections d'Evans, à défini toute une hiérarchie de nouvelles géométries, où à la base on trouve les géométries monobasées (1-ample) et les géométries non-CM-triviales (2-ample) et sur le dessus on trouve des corps, qui sont n-ample pour tout n. Récemment, Baudisch, Pizarro et Ziegler et indépendamment Tent ont fourni des exemples prouvant que cette hiérarchie d'ampleur est stricte. Tandis que leurs exemples sont omega-stables de rang infini, il est resté ouvert si on peut trouver des géométries de rang fini qui sont au moins 2-amples mais n'interprètent pas un corps. Avec Katrin Tent, nous avons produit une structure presque fortement minimale qui est 2-ample, mais pas 3-ample, en utilisant une construction à la façon de Hrushovski. Dans cet exposé, nous donnerons un aperçu de la conjecture et de ses contre-exemples, motivant pourquoi notre nouvelle structure s'inscrit naturellement dans le tableau. |
| |||||
| + | Some news from the Crane Beach | 20/02/2017 | 15:10 | Charles Paperman | ||
| First-order logic over words is known to be equivalent to the circuits complexity class AC0 when equipped with arbitrary predicates. In this talk I will present result about the expressivity of first order logic when we restrict the class of predicates. I will focus in particular on the Crane Beach Property. Introduced more than a decade ago, this property is true of a logic if all the expressible languages admitting a neutral letter are regular. Finally I will present it's closely tied to the counting (in)ability of a logic as an application. |
| |||||
| + | Non-classical Quantifiers Over Non-classical Logics | 13/02/2017 | 15:10 | Alejandro Petrovich | ||
| In the literature there are several papers on the study of quantifiers in non-classical logics. Part of these works consists of considering the fragment corresponding to the study of monadic logic, that is, the fragment where the predicate symbols depend only on a fixed variable or a constant symbol. Although the connectives of propositional logic are non-classical, quantifiers are interpreted in the classical sense. The purpose of this paper is to introduce different notions of quantifiers in the particular case of the infinite valued logic (IVL) developed by Lukasiewicz. The algebraic models of this theory turn out to be MV algebras endowed with an additional operator, where MV-algebras are the algebraic models corresponding to the logic IVL. When quantifiers are interpreted classically, these structures are called monadic MV-algebras and are generalizations of the well known monadic Boolean algebras introduced by Halmos [Ha62].
References: [Ha62] P. Halmos, Algebraic Logic, Chelsea Publishing Company, 1962. [Sch77] Schwartz, D., Theorie der polyadischen MV-algebren endlicher Ordnung, Math. Nachr., 78 (1977) 131--138. [Sch80] Schwartz, D., Polyadic MV-algebras, Zeitschrift f\"ur Math. Logik und Grundla\-gen der Mathematik, 26 (1980) 561--564 . |
| |||||
| + | Abstract Algebraic Theory of Quadratic Forms and Rings | 30/01/2017 | 15:10 | L'exposé de Francisco Miraglia prévu le 30 janvier est annulé | ||
|
Abstract (joint work with M. Dickmann): Let A be a commutative unitary semi-real (– 1 is not a sum of squares) ring in which 2 is a unit; let T = A2 or a proper preorder of A. We shall describe first order axioms such that if the pair (A, T) is a model of these statements, then there is a special group, $G_T(A)$, naturally associated to (A, T), faithfully coding the T-theory of diagonal quadratic forms with unit coefficients in A. Under mild restrictions, these axioms are necessary and sufficient for $G_T(A)$ to faithfully code representation and T-isometry of non-singular diagonal quadratic forms with coefficients in A. We shall present important classes of rings satisfying these axioms and extract significant results concerning the behavior of quadratic form theory over these classes of rings. The needed concepts will be presented during the talk, which contains only part of the results that appeared in: M. Dickmann, F. Miraglia, Faithfully Quadratic Rings, Memoirs of the AMS, 1128, (November 2015). |
| |||||
| + | Universal objects among Boolean algebras and Banach spaces | 23/01/2017 | 15:10 | Christina Brech | ||
| An element B of a given class of Boolean algebras is universal if every other element of the class is isomorphic to a subalgebra of B. In the context of Banach spaces, we have similar notions considering isomorphisms or isometries of Banach spaces. We will discuss the existence of universal objects for some classes of Boolean algebras and of Banach spaces and their interaction. We are particularly interested in the classes of all objects of a fixed size - cardinality of Boolean algebras and density character of Banach spaces - and we shall compare the countable/separable and the uncountable/nonseparable settings.
|
| |||||
| + | Groupes définissables dans des corps enrichis | 16/01/2017 | 15:10 | Silvain Rideau | ||
| Un résultat de Pillay affirme qu'un groupe définissable dans un corps différentiellement clos peut être plongé dans un groupe algébrique. Des théorèmes semblables ont été prouvés depuis pour de nombreuses structures de corps enrichis: corps séparablement clos, corps avec automorphisme générique, corps réels clos... De plus, la preuve de tous ces résultats utilisent des outils similaires développés pour étudier les groupes dans les théories stables puis simples.
Le but de mon exposé sera d'exposer certains de ces résultats de structure pour les groupes définissables ainsi que les outils utilisés. Enfin, si le temps le permet, j'expliquerais comment, dans le cas le moins compliqué, on peut s'affranchir, dans une certaines mesure, des hypothèses de stabilité ou de simplicité utilisées dans ces preuves pour pouvoir les appliquer dans des corps valués. |
| |||||
| + | Valuations | 05/12/2016 | 15:10 | Jacques Van de Wiele | ||
| Thème principal : (cours elementaire sur les) anneaux de (pre)valuation p-adique, theorie des modeles, arithmetique, approche finitaire
thèmes abordés : logique intuitionniste, algebre commutative, constructive modules, (co)homologies, categories abeliennes, (logique lineaire) topos de Faltings Biblio principale : Grothendieck [01.8GRO14a] Integration Motivique (Loeser, Nicaise, Sebag) [18MOT1-11a] [18MOT2-11a] Marc Hindry :Arithmetique [30HIN08a] Ahmed Abbes, Michel Gros, Takeshi Tsuji :The p-adique Simpson Correspondence [18ABB16a] Ihsen Yengui : Constructive Commutative Algebra [16.5YEN15a] |
| |||||
| + | A small history of K-triviality | 28/11/2016 | 15:10 | Benoit Monin | ||
| The Kolmogorov complexity of a string is, informally, the length of the smallest program that produces this string. We write C(s) = n to mean that the smallest program producing the string s is of length n.
An infinite binary sequence X is said to be C-trivial if the Kolmogorov complexity of its prefixes is minimal, that is, if there is a constant d such that for any n, we have C(X rest n) < C(n) + d (Here X rest n denotes the n first bits of X). It is clear that any computable (infinite binary) sequence is C-trivial. Chaitin proved that the converse holds: A sequence X is computable iff it is C-trivial (1). Chaitin also successfully used Kolmogorov complexity to provide a formal definition of the intuitive idea we can have of a random sequence. To do so, he needed a variation of the standard Kolmogorov complexity, called "prefix Kolmogorov complexity" and denoted by K. Using this prefix Kolmorogov complexity K, he defined a sequence Z to be random if for any n we have K(Z rest n) > n - d for some constant d. The intuition is that the prefix Kolmogorov complexity should be maximal for prefixes of random sequences. This definition of randomness is still today the most studied, for many reasons that we shall not detail during the talk. Chaitin conjectured (1) to also be true with prefix Kolmorogov complexity K, that is, X is computable iff X is K-trivial (that is, there is d such that for every n we have K(X rest n) < K(n) + d). Solovay later refuted the conjecture by constructing a non-computable K-trivial sequence A. The notion of K-triviality was born, and had yetto reveal many surprises through its numerous different characterizations, and its connections with algorithmic randomness. After introducing the main concepts with more details, we will try during this talk to give some explanations and intuitions on the work that has been done by various people on K-triviality these last 15 years. |
| |||||
| + | Complexité borélienne des relations d'équivalence | 21/11/2016 | 15:10 | Dominique Lecomte | ||
| Nous étudions la complexité topologique des relations d'équivalence boréliennes, et donc la classe de ces dernières munie du quasi-ordre de réduction continue. Nous présenterons les premiers résultats de cette étude entamée il y a moins d'un an, ainsi que certains des théorèmes ayant permis de les obtenir. |
| |||||
| + | Minimal Distance of Propositional Models | 14/11/2016 | 15:10 | Miki Hermann | ||
| We investigate the complexity of three optimization problems in Boolean propositional logic related to information theory: Given a conjunctive formula over a set of relations, find a satisfying assignment with minimal Hamming distance to a given assignment that satisfies the formula (NextOtherSol, NOSOL$) or that does not need to satisfy it (NearestSol, NSOL). The third problem asks for two satisfying assignments with a minimal Hamming distance among all such assignments (MinSolDistance, MSD).
For all three problems we give complete classifications with respect to the relations admitted in the formula. We give polynomial time algorithms for several classes of constraint languages. For all other cases we prove hardness or completeness regarding APX, poly-APX, or equivalence to well-known hard optimization problems. |
| |||||
| + | Belles paires de structures randomisées | 07/11/2016 | 15:10 | Tomás Ibarlucía | ||
| Un problème intriguant en théorie des modèles des structures métriques est celui de généraliser la notion de théorie mono-basée. Dans le cadre d'une théorie oméga-catégorique T, une proposition intéressante vient de considérer la théorie T_P de belles paires de modèles de T : quand est-ce T_P oméga-catégorique ? Cette propriété généralise celle d'être mono-basée dans le cas classique et s'applique à d'autres exemples importants. Malheureusement, on verra qu'elle n'est jamais satisfaite par des théories randomisées non-triviales. On rappellera ce qu'est la randomisation T^R de T, puis on classifiera les modèles séparables de (T^R)_P lorsque T est oméga-catégorique. |
| |||||
| + | Autour des degrés ludiques | 17/10/2016 | 15:10 | Christophe Chalons | ||
|
| ||||||
| + | La propriété de Ramsey approximative des matrices réelles et des espaces vectoriels normés | 26/09/2016 | 15:10 | Jordi Lopez-Abad | ||
| Nous présentons la propriété de Ramsey approximative des espaces vectoriels normés de dimension finie. Nous discuterons aussi le degré de Ramsey métrique des matrices réelles et complexes, comme une version du Théorème de Graham-Leeb-Rothschild sur les Grassmanniennes d'un espace vectoriel sur un corps fini. |
| |||||
| + | A generalization of the Baire property | 20/06/2016 | 15:10 | Philipp Schlicht | Salle 1016 Bâtiment Sophie Germain | |
| Many definable subsets of the Baire space of functions on the natural numbers satisfy the Baire property, for instance all analytic sets. However, it is well known that some simply definable subsets of the space of functions on a regular uncountable cardinal fail to satisfy the analogue to the Baire property. We introduce a more general property that is equal to the Baire property in the countable setting, and show that it is consistent that all definable subsets of the space of functions on an uncountable regular cardinal have this property. We consider applications such as the non-existence of definable well-orders. |
| |||||
| + | Logiques à points fixes et théorie de la preuve (in)finitaire | 30/05/2016 | 15:10 | Alexis Saurin | Salle 1016, bâtiment Sophie Germain | |
| Dans cet exposé, on étudiera la théorie de la démonstration de logiques à points fixes, en se plaçant dans le cadre de la correspondance de Curry-Howard qui met en relation 1) formules logiques et types de données 2) preuves et programmes 3) procédure d'élimination des coupures et exécution d'un programme.
L'exposé conduira à discuter du contenu calculatoire des logiques à points fixes et permettra de présenter des systèmes de preuves finitaires et infinitaires pour ces logiques. En se concentrant sur le cadre infinitaire, on présentera les théorèmes de focalisation et d'élimination des coupures, résultats centraux en théorie de la démonstration, notamment pour la logique linéaire, que l'on introduira, resituera et dont on discutera les conséquences. |
| |||||
| + | What can probability logic describe? | 09/05/2016 | 15:10 | Ehud Hrushovski | Salle 1016 Bâtiment Sophie Germain | |
| Probability quantifiers were studied by Keisler and Hoover in the 1980's,following earlier work of Carnap, Gaifmann, Krauss-Scott. I will survey some basic results on pure probability logic, where only stochastic quantifiers are allowed. The interpretative powers of this logic are drastically more limited than that of first-order logic. If the language consists of binary relations, one can interpret nothing more than spatial location (in a sense that will be explained; essentially on the Kim-Pillay space.) Subtleties increase with higher-order relations.
|
| |||||
| + | La théorie des modules des corps séparablement clos | 04/04/2016 | 15:10 | Esther Elbaz | Salle 1016, bâtiment Sophie Germain | |
|
Dans [1], Pilar Dellunde, Françoise Delon et Françoise Point ont considéré les corps séparablement clos de caractéristique non nulle et de degré d’imperfection fixé comme des modules sur l'anneau des endomorphismes $\mathbbF_p (B) \left \lbrace \alpha \right \lbrace$ où B est une p-base du corps et $\alpha$ est le morphisme de Froebénius. Après avoir axiomatisé cette théorie, les auteurs ont montré qu'elle est complète et admet l'élimination des quantificateurs dans le langage usuel des modules enrichis de symboles de fonctions additives analogues aux fonctions $p$-composantes du corps. Dans cet exposé, nous présenterons ces résultats. [1] The Theory of Modules of Separably Closed Fields 1 Pilar Dellunde; Françoise Delon; Françoise Point The Journal of Symbolic Logic, Vol. 67, No. 3. (Sep., 2002), pp. 997-1015. |
| |||||
| + | Bornes inférieures pour les circuits non-commutatifs : un autre Waterloo de la complexité algébrique ? | 14/03/2016 | 15:10 | Guillaume Lagarde | Salle 1016, bâtiment Sophie Germain | |
| On ne connait toujours pas de polynôme explicite nécessitant des circuits algébriques non-commutatifs (Circuits NC) de taille superpolynomiale.
Le cadre non-commutatif semble pourtant commode pour montrer de telle borne inférieure car la rigidité de la non-commutativité impose de nombreuses contraintes sur la manière de calculer efficacement. C'est dans ce contexte que Nisan, en 1991, fournit une borne exponentielle sur la taille des ABPs non-commutatifs (Algebraic Branching Programs) calculant le permanent. Nous montrons que ce résultat s'inscrit de manière naturelle comme cas particulier d'un théorème sur les circuits non-ambigus (c'est-à-dire ceux qui ne possèdent qu'un seul type de "parse tree") et proposons quelques pistes afin d'étendre ce résultat à des circuits de plus en plus proche de circuits NC généraux. (Travaux en commun avec Guillaume Malod et Sylvain Perifel; Nutan Limaye et Srikanth Srinivasan) |
| |||||
