Séminaire Général de Logique

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

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.

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.

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.

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.

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

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.

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.

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 !

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.

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.

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.

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

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.

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.

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.

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.

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.

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