Logo IMJ-PRG
Paris Diderot Sorbonne Université CNRS

Séminaire Général de Logique


2016 2017 2018 2019

Année 2018- 2019

Responsables : O. Finkel, T. Ibarlucía, A. Khélif, S. Rideau, C. Sureson
Lundi de 15h10 à 16h10, salle 2015 (Attention changement de salle).
Page web et programme
Archives
Abonnement à la liste de diffusion


David Evans - Imperial College London

Higher amalgamation in measurable structures

lundi 20 mai 2019 à 15:10 :

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.


Raphaël Carroy - Université de Vienne, Autriche

Le plongement topologique et la réduction continue sur la première classe de Baire

lundi 13 mai 2019 à 15:10 :

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.


Alexis Saurin - IRIF, CNRS et Université Paris Diderot

De la descente infinie à la programmation avec des types (co)inductifs

lundi 15 avril 2019 à 15:10 :

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.


Anton Freund - TU Darmstadt

Collapsing large ordinals

lundi 8 avril 2019 à 15:10 :

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).


Françoise Point - FNRS-FRS

Expansions de corps dp-minimaux avec une derivee et applications aux theories de paires denses de corps

lundi 25 mars 2019 à 15:10 :

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).


Thomas Seiller - Laboratoire d'Informatique de Paris-Nord

Des preuves aux programmes, aux systèmes dynamiques. Perspectives géométriques en complexité algorithmique

lundi 18 mars 2019 à 15:10 :

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.


Martin Bays - Universität Münster

Isolation, compression schemes, and density of compressibility

lundi 11 mars 2019 à 15:10 :

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.


Joan Bagaria - ICREA

Symmetry and Self-Similarity in the Higher Infinite

lundi 4 mars 2019 à 15:10 :

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.


Hector Pasten - PUC Chile

Diophantine sets of number fields and their rings of integers --- à 16h en salle 1016

lundi 25 février 2019 à 16:00 :

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.


Benjamin Siskind - UC Berkeley

Meta-iteration trees and mouse pairs

lundi 18 février 2019 à 15:10 :

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.


Paul-André Melliès - IRIF, Université Paris Diderot

Jeux de gabarit : un modèle homotopique et interactif de la logique linéaire différentielle

lundi 4 février 2019 à 15:10 :

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.


Esther Elbaz - Equipe de Logique Mathématique, IMJ-PRG

Structures dont l’anneau de Grothendieck est $\mathbb{Z}/N\mathbb{Z}$

lundi 28 janvier 2019 à 15:10 :

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.


Paola d'Aquino - Università della Campania

Roots of exponential polynomials

lundi 21 janvier 2019 à 15:10 :

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


Alessandro Vignati - KU Leuven

Logic and Cech-Stone remainders

lundi 14 janvier 2019 à 15:10 :

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.


Juliette Kennedy - University of Helsinki, Finlande

On Extended Constructibility

lundi 10 décembre 2018 à 15:10 :

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.


Hugo Herbelin - IRIF, Université Paris Diderot

Calculer avec le théorème de complétude de Gödel

lundi 3 décembre 2018 à 15:10 :

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 !


Hadrien Batmalle - IRIF, Université Paris Diderot

Forcing, réalisabilité classique et propriétés de préservation

lundi 26 novembre 2018 à 15:10 :

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.


Guillaume Malod - Equipe de Logique Mathématique, IMJ-PRG

Les séries d’arbres et la complexité algébrique

lundi 19 novembre 2018 à 15:10 :

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.


Frank Wagner - Université Lyon I

Anneaux et groupes dimensionnels

lundi 12 novembre 2018 à 15:10 :

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.


Thomas Ehrhard - IRIF, Université Paris Diderot

Sur la sémantique des langages de programmation probabilistes

lundi 5 novembre 2018 à 15:10 :

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).


Frank Benoist - Université Paris-Sud

Ingrédients modèle-théoriques dans la preuve de la conjecture de Mordell-Lang

lundi 29 octobre 2018 à 15:10 :

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.


David Aspero - University of East Anglia

The special $\aleph_2$-Aronszajn tree property and GCH

lundi 15 octobre 2018 à 15:10 :

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.


Jouko Vaananen - University of Helsinki, Finlande

An invitation to dependence logic

lundi 8 octobre 2018 à 15:10 :

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.


Alessandro Vignati - Equipe de Logique Mathématique, IMJ-PRG

L’exposé est reporté à une date ultérieure - Uniform Roe algebras and rigidity, part II

lundi 24 septembre 2018 à 15:10 :

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.


Andrew Zucker - Equipe de Logique Mathématique, IMJ-PRG

Bernoulli disjointness

lundi 17 septembre 2018 à 15:10 :

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.


Ilijas Farah - York University

Uniform Roe algebras and rigidity

lundi 3 septembre 2018 à 15:10 :

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.)