Séminaires : Séminaire Général de Logique

Several notions of computability can be defined for compact subsets of Euclidean spaces. Some of them turn out to be equivalent for certain sets - we then say that the set has ``computable type''. Miller (2002) proved that n-dimensional spheres have computable type, and Iljazovic (2013) proved that closed manifolds have computable type. We study the case of finite simplicial complexes and obtain several topological characterizations of the complexes having computable type. We also relate the notion of computable type to the descriptive complexity of topological invariants, and investigate the expressiveness of low complexity invariants. This work was done in collaboration with Djamel Eddine Amir.

We discuss a number of uniform dichotomies for problems in the Weihrauch lattice. Such dichotomies have the common form that a problem is either quite well-behaved (continuous, measurable of some form, etc.) or already relatively badly behaved. We show that often such dichotomies also have non-uniform versions and we indicate how computability concepts such as Turing jumps, Weak König's Lemma, diagonal non-computability, etc. occur naturally in these non-uniform versions. We also discuss how some known dichotomies from descriptive set theory, such as Solecki's dichotomy, can be seen in this context.

Cardinal characteristics of the continuum are (definitions for) cardinals that are provably uncountable and at most the cardinality of the reals, but which may be strictly less than the cardinality of the continuum in universes where the Continuum Hypothesis fails.  Many of the standard cardinal characteristics of the continuum are defined in terms of a relation holding almost everywhere, where "almost everywhere" means on all but a finite set.  A very natural generalisation is to take "almost everywhere" to mean on all but a member of a given ideal.  I will talk about what happens when we do this, with the density 0 ideal on the naturals as a focal example.

Considerations on the asymptotic behavior and the growth at infinity of functions are often used to solve ODEs. The field of transseries was first defined by Dahn and Göring and by Ecalle and Il'yashenko independently in the 80s and 90s. It is a generalization of the germs at infinity of exp-log functions. Transseries formalize the so called exp-log growth class in a setting with more algebraic operations than germs enabling more computational power. Work from J van der Hoeven (1997) has shown that one can solve polynomial differential equations in the field of grid based transseries using setting-specific techniques. In 2008, M. Aschenbrenner, L. van der Dries and J. van der Hoeven have proved that the theory of transseries is recursively axiomatisable and admits QE in a finite language containing the field operations and the derivation. Therefore since differential polynomials over the transseries are definable in that langage there exists an algorithm solving polynomial ODE over any model of the theory. Our aim is to present a Preparation theorem in the style of Weierstrass' such that given any differential polynomial P we construct a cell decomposition of the space such that P rewrites on each cell as a simple product of factors from which the roots of P are easily readable : this is equivalent to eliminating quantifiers from a certain type of formula.

In this talk I will describe and illustrate the field of transseries without going into the details of its technical construction, before presenting a preparation theorem for polynomials, our conjecture and various examples from our work.

There are many natural set-theoretic structures which satisfy every axiom of ZFC except for Power Set, for example the collection of hereditarily countable sets. Therefore, it is worth investigating what this theory is. If one simply deletes the Power Set axiom but uses the standard formulation of the other axioms (in particular with only the Replacement Scheme) then this theory may have unexpected consequences, for example it is possible that omega_1 exists but is singular. On the other hand, most natural structures satisfy the stronger scheme of Collection, which prevents many of these undesired possibilities from occurring. Therefore, the standard definition of this theory is "ZFC without Power Set but with the Collection Scheme".

In this talk we are going to investigate some limits of this stronger theory by considering the notion of a big proper class, which is a proper class that surjects onto every non-zero ordinal. We shall see that, even with Collection, there are models of ZFC without Power Set in which the reals form a proper class that is not big. However, if one additionally assumes the schemes of Dependent Choices for arbitrary lengths, then every proper class is indeed big. Building on work of Zarach, we will provide a general framework for separating Dependent Choice schemes of various lengths. Finally, using a similar idea, we will produce a new model of ZFC without Power Set but with Collection in which there are unboundedly many cardinals, but the Reflection Principle (and therefore the scheme of Dependent Choice of length omega) fails. This is joint work with Victoria Gitman.

I will discuss some results on existential theories of fields, with a focus on decidability questions. This is motivated partly by Hilbert's Tenth Problem (on the solvability of diophantine equations) and partly by general model-theoretic concerns. Questions covered will include the (non-)transfer of existential decidability up and down finite field extensions, and consequences for complete discretely valued fields in mixed characteristic.

The pseudo-algebraically closed (PAC), pseudo real closed (PRC), and pseudo p-adically closed fields (PpC) are examples of unstable fields that have similarities, but have often been studied separately. In this talk, we propose a unified framework for studying these fields - the class of pseudo-T-closed fields, where T is an enriched theory of field. These fields verify a "local-global" principle for the existence of points on varieties based on models of T. This approach also enables a good description of some fields equipped with multiple V-topologies, particularly pseudo-algebraically closed fields with a finite number of V-topologies. 

One important result is a (model theoretic) classification result for bounded pseudo-T-closed fields, in particular we can show that under specific hypotheses in T, these fields are NTP2.

This is joint work with Silvain Rideau-Kikuchi

Using the projective Fraisse limit construction introduced by Irwin and Solecki we obtain a new compact connected one-dimensional metric space. This continuum (compact connected space) is approximated by finite connected graphs with confluent epimorphisms. We show that the obtained continuum is indecomposable, but not hereditarily indecomposable, as arc-components are dense. It is pointwise self-homeomorphic, but not homogeneous, and each point is the top of the Cantor fan. Moreover, it is hereditarily unicoherent, in particular, it does not embed a circle; however, it embeds the universal solenoid and the pseudo-arc. This is joint work with W. J. Charatonik and R. P. Roe.

Both ultrapowers and reduced powers are used as a `magnifying glass’ to study countable structures. (This applies to separable metric structures in continuous logic, and so does most of what I will say in the talk, but I will stick to classical, discrete, model theory.) I will discuss some similarities and differences between these two constructions.

The Ax-Kochen/Ersov theorem is  a classic result in the model theory of valued fields. It can be paraphrased as saying that the elementary theory of a valued field is determined by the theory of the value group and the theory of the residue field. At the level of types, the intuition is that a type should be controlled by its trace in each of the residue field and value group. In this talk, I will explore some ways in which this intuition can be made precise, and also some limitations to that preliminary intuition. I will try to give lots of examples to keep the discussion concrete.

Joint work with Manuel Bodirsky. Given a class of finite structures, one can consider $\mu_n$ the uniform measure on graphs in said class of size n. We study the asymptotic behavior, when n goes to infinity, of the family $(\mu_n)_n$. In particular, one can ask: which first order sentences have converging probability, and when is this limit non-zero? I will present our results for classes of graphs and digraphs, in particular classes not containing any homorphic copies of certain sets of finite structures.

Many mathematical theorems can be viewed as problems: a statement of the form forall x in X (phi(x) implies exists y in Y psi(x,y)) is the problem of finding a suitable y starting from x.
Weihrauch reducibility allows to compare these (and many other) problems in a way that refines the analysis carried out in the framework of reverse mathematics. In the last 15 years this approach has been very fruitful, but until now it has almost exclusively dealt with theorems that reverse mathematics classifies at or below the level of ATR0.
We start the investigation of theorems at the level of Pi^1_1-comprehension by dealing with a classic result of descriptive set theory: the Cantor-Bendixson theorem, stating that every closed subset of a Polish space can be uniquely written as the disjoint union of a perfect set (the perfect kernel) and a countable set (the scattered part).
The talk will start with an introduction to Weihrauch reducibility and the Weihrauch lattice.

This is joint work with Vittorio Cipriani and Manlio Valenti

When a subset of a field is existentially definable in the language of rings, one can ask what the smallest number of quantifiers is needed for an existential formula defining this set. Especially in a number-theoretic context, this question is motivated by links to Hilbert's 10th Problem and other decidability problems. However, this question also turns out to be quite hard in general, since answering it requires a thorough understanding of the arithmetic of the field in question.
On the other hand, if one asks how many quantifiers are needed to existentially define a definable class of subsets (e.g. the set of sums of 4 squares) uniformly across fields, then the problem gets a much more geometric flavour, can be tackled via a model-theoretic approach, and is connected with the notions of essential and canonical dimension, as introduced by Merkurjev. In this talk, I will discuss some techniques, results, and open questions.
Based on joint work with Arno Fehm and Philip Dittmann. Preprint available as arXiv:2102.06941.

We survey recent results in reverse mathematics, highlighting theorems from the general mathematics literature whose logical strength is unusual in some way.  The Rival-Sands theorem for partial orders is a Ramsey-theoretic result concerning chains in partial orders of finite width.  We show that the Rival-Sands theorem is equivalent to the ascending/descending sequence principle, which is a weak consequence of Ramsey's theorem for pairs (joint with Fiori Carones, Marcone, and Soldà).  This gives the first example of a theorem from the modern literature that is characterized by the ascending/descending sequence principle.  Ekeland's variational principle concerns approximate minima of lower semi-continuous functions that are bounded below.  We show that the localized version of Ekeland's variational principle is equivalent to Pi^1_1-CA_0, even when restricted to continuous functions (joint with Fernández-Duque and Yokoyama).  This is unusual because the much weaker system ACA_0 typically suffices to prove theorems about continuous functions.  Caristi's fixed point theorem is a consequence of Ekeland's variational principle that concerns fixed points of arbitrary functions that are controlled by lower semi-continuous functions.  We show that Caristi's theorem for Borel functions is equivalent to Towsner's transfinite leftmost path principle and therefore has the unusual position of being strictly between ATR_0 and Pi^1_1-CA_0 (joint with Fernández-Duque, Towsner, and Yokoyama).

In this talk we will see some recent results regarding the spectra, i.e. the set of possible sizes of, of combinatorial sets of reals, sets traditionally associated to the combinatorial cardinal characteristics of the continuum  and the projective complexity to witnesses of different cardinalities.

I will give a gentle introduction to Fraïssé theory formulated in the language of category theory and explain how it encompasses both the classical Fraïssé theory of countable first-order structures and the projective Fraïssé theory of topological structures, introduced by Irwin and Solecki. Then I will sketch our extension of the framework to the metric-enriched context and its application: characterizing the pseudo-arc and pseudo-solenoids directly as Fraïssé limits. If time permits, to show the big picture I will briefly mention other closely connected topics that benefit from using the abstract setting: the Banach–Mazur game, weak amalgamation property, Ramsey theory, KPT correspondence, rewriting systems, ... .

In the spirit of the set-theoretic multiverse philosophy put forward by Joel David Hamkins, we explore a related modal multiverse populated by Kripke models and more general worlds. In this multiverse—as the talk will explain—the law of excluded middle can be switched on and off like a light bulb and countability is a button (for every set X of every world, there is a larger world containing a surjection ℕ → X). Our interest in this multiverse is because of concrete applications in commutative algebra and combinatorics, including the endeavor of extracting algorithms from proofs utilizing transfinite techniques. The talk will be framed by several examples of this kind.

To any model of computation, such as lambda calculus or Turing machines, there is an associated "effective topos". This is an alternate mathematical universe in which—for reasons related to computability not the usual laws of logic hold.

For instance, for some models, anti-classical dream axioms like "any function ℝ → ℝ is continuous" and "any function ℕ → ℕ is computable" hold. The law of excluded middle however, "any proposition is either true or not true", is falsified in those toposes.

The effective topos has especially wondrous properties in case we employ models of hypercomputation, where computers can perform infinitely many calculational steps in finite time: Andrej Bauer proved that then the effective topos contains an injection ℝ → ℕ.

We can also employ physical models about the real world. In this case, statements which are in classical mathematics simply true become non-trivial statements about the nature of the physical world when interpreted in the effective topos.

Topos theory therefore provides an apt vehicle to study computation and alternative axioms of logic. Other applications include mechanical extraction of programs from proofs and a reconciliationcof platonism with formalism.

The talk strives to give an accessible introduction to this circle of ideas, also resolving any apparent paradoxes in this abstract. No prerequisites in topos theory or the theory of computation are needed.

In 1914, A. Thue (the PhD supervisor of T. Skolem) posed an innocent-looking problem about transforming some words into others, subject to a fixed set of rules. This problem -- the word problem for finitely presented semigroups -- would come to have a remarkable effect on the development of mathematical logic, group theory, and semigroup theory in the half century to come. Indeed, it can be seen as one of the key links ensuring that mathematical logic became a firm part of mathematics in the 1930s and 1940s. In this talk, I'll give an overview of the problem, its history, and how it developed. I will present a special case of it -- the word problem for one-relation semigroups -- which despite an inordinate amount of effort to crack, remains an unsolved problem. Finally, I will present some of my own efforts to approach and understand this wonderful problem.

Two-cardinal tree properties have been a central topic of study in combinatorial set theory over the last fifteen years. Such principles can be used to characterize strongly compact and supercompact cardinals among inaccessible cardinals but can also consistently hold at smaller cardinals. Of particular interest has been their effect on cardinal arithmetic. Notably, a pair of results due to Viale and Krueger, respectively, shows that the strongest of these principles, $\mathsf{ISP}(\kappa)$, implies that the singular cardinals hypothesis holds above $\kappa$. This raises the natural question of whether the same conclusion follows from weaker principles. Motivated by this question, we introduce some combinatorial principles that hold in all known models of two-cardinal tree properties and prove that they imply a strong form of the singular cardinals hypothesis. We also show that these principles can consistently hold globally. This is in contrast with tree properties, where the possibility of a global consistency result for even the classical tree property remains a major open question. The talk will focus on the broader picture and will be accessible to a general logic audience.

We discuss some general model theoretic criteria to show that the automorphism group of a homogeneous structure (such as metric spaces, incidence geometries, graphs and hypergraphs) are  simple groups or have simple quotients.

We establish certain connections between perfectoid geometry and model theory of henselian fields. On one hand, we prove an Ax-Kochen/Ershov principle for perfectoid fields (and generalizations thereof). As an application, we show that the perfect hull of Fp(t)^h is an elementary substructure of the perfect hull of Fp((t)). On the other hand, we prove a model theoretic generalization of the Fontaine-Wintenberger theorem. This reveals that the relation between a perfectoid field and its tilt is analogous to that of well-understood valued fields (viz., henselian defectless with divisible value group) and their residue fields. As a new arithmetic application, we provide some of the first few examples in mixed characteristic verifying the Lang-Manin conjecture on the existence of rational points on nearly rational varieties over C1 fields. Joint work with Franziska Jahnke.

Consider a topological group  $G$ and its unitary representation $\rho$. Consider the closure of $\rho(G)$ in the weak operator topology. Then we get a compact semigroup with separately continuous multiplication. For semisimple Lie groups with finite center this semigroup is simply the one-point compactification (R.Howe  and C.Moore).
However, for Abelian  groups (for instance for $\mathbb Z$) and for infinite-dimensional groups this leads to highely nontrivial (but handable) objects. The purpose of talk is an introduction to problems of this type (we do not suppose any preliminary knowledge of representation theory).

Ce projet a démarré par une question sur la complexité des expansions des entiers par un ensemble unaire: tous les exemples stables connus sont superstables de U rang omega (ou 1) et les expansions proprement simples utilisent des résultats non triviaux de théorie des nombres. Il se trouve que tout cela n’était que pur coincidence puisque tout graphe peut être interprété dans une expansions unaires de (Z,+) qui n’est pas plus compliquée que le graphe.

Le principal outil pour construire ces exemples est que rajouter de la la structure à un ensemble stablement plongé ne le rend pas plus compliqué (pour ce qui est de la classification) que la structure initiale ou la structure additionnelle. Ces phénomènes « resplendissants » sont déjà implicites dans des travaux de Chernikov et Hils sur NTP_2 et de Jahnke et Simon sur NIP.

Dans cet exposé, j’expliquerais comment ces résultats s’étendent à d’autres classes (stabilité, superstabilité, simplicité, NSOP_1) et j’expliquerais comment cette question est liée à la première question, à première vue sans rapport!

Ceci est un travaux un commun avec G. Conant, C. D’Élbée, Y. Halevi and L. Jimenez

We analyze C*-algebras, particularly approximately finite ones, in the context of the infinitary logic L_{\omega_1,\omega}. We show that, level by level, the L_{\omega_1,\omega} theory of a separable AF algebra can be covered from that of its K_0 group, a classifying group in this setting. We then use this to build a very concrete family of separable simple unital AF-algebras of arbitrarily high Scott rank. All preliminary notions will be discussed. This is joint work with De Bondt, Vaccaro, and Velickovic.

Une question était de savoir si tout groupe dont la théorie est simple est moyennable. Chernikov, Hrushovski, Kruckman, Krupinski, Pillay et Ramsey ont répondu à cette question par la négative.

Il est bien connu que la mesure de comptage sur les corps fini donne une mesure de comptage non-standard sur les corps pseudo-finis (qui sont les modèles infinis de la théorie des corps finis), et que donc les groupes définissables dans un corps pseudo-fini sont moyennables. Les corps pseudo-finis ont une théorie simple, de même que les corps parfaits PAC bornés, et la question se pose de savoir si les corps parfaits PAC bornés ont une mesure avec des propriétés raisonnables.

Avec Nick Ramsey, nous définissons une mesure sur certains de ces corps (ceux dont le groupe de Galois absolu est e-libre - les corps PAC parfaits e-libres), et montrons en particulier que les groupes définissables dans ces corps sont moyennables. Un argument de limite montre que ce résultat s'étend aux corps parfaits PAC dont le groupe de Galois absolu est libre (et donc éventuellement avec une théorie non simple). Le résultat s'étend aussi aux corps parfaits PAC dont le groupe de Galois absolu est pro-p libre. 

Toutes les définitions nécessaires seront introduites. Je discuterai certains des problèmes rencontrés.

NIP -- "not having the independence property" -- is a constraint on the combinatorial behaviour of the definable sets in a given theory. Roughly: NIP means that there is no family of definable sets that induces on an infinite set X the family of all subsets of X. Shelah's Conjecture proposes that any complete NIP theory of fields is the theory of a separably closed, real closed, "henselian", or finite field. I will explain how we can refine this conjecture by specifying the complete theories that may appear in the "henselian" case. This is joint work with Franziska Jahnke.

 Nous considérons diverses classes de graphes, des plus arbitraires jusqu'à ceux induits par une fonction. La question fondamentale de ce travail est de déterminer quand un graphe a un coloriage continu à deux couleurs. Nous comparons les graphes à l'aide du quasi-ordre associé soit aux homéomorphismes injectifs continus, soit aux homomorphismes continus. Nous présenterons des propriétés structurelles de ces quasi-ordres. Nous verrons que la dynamique topologique est très utile pour cela. Cette analyse apporte également des informations sur le quasi-ordre de réduction borelienne sur la classe des relations d'équivalence analytiques, en particulier celle de conjugaison des homéomorphismes minimaux de l'espace de Cantor.

Les espasces topométriques apparaissent naturellement en logique continue (espaces de types, groupes d'automorphismes de structures métriques...). Fréquemment, un groupe polonais agit sur l'espace topométrique qui nous intéresse (par exemple, un groupe polonais agisssant sur lui-même par conjugaison), et on souhaite déterminer s'il existe des éléments "métriquement génériques", i.e. tels que l'adhérence (pour la distance) de leur orbite soit comaigre (pour la topologie). Dans le cas classique, i.e. purement topologique, un théorème d'Effros permet de caractériser ces éléments, ainsi que de donner une condition nécessaire et sufisante pour leur existence. Dans cet exposé je présenterai  une extension de ce théorème et de ce critère au contexte des espaces topométriques adéquats, et essaierai d'expliquer pourquoi cette hypothèse supplémentaire (satisfaite pour les exemples mentionnés plus haut) limite actuellement les possibilités d'application de ce résultat.

Il s'agit d'un travail en commun avec I. Ben Yaacov (Lyon)

 A result obtained by A. Macintyre and J. Derakhshan states that the theory of a Henselian valued field of mixed characteristic, finite ramification, perfect residue field and whose value group is a Z-group, is model complete in the language of rings if the theory of the residue field is model complete in the language of rings. In this talk we will see how this result can be generalized to henselian valued fields with the same properties but with different value groups. We will address the case of value groups with finite spines and value groups elementarily equivalent to the lexicografical product of Z with minimal positive element. We will see in which languages these groups are model complete and we will define a one sorted language in which the theory of the respective valued field is model complete, assuming that the residue field is model complete in the language of rings. It follows that the theories of some infinite non-algebraic extensions of the field of p-adic numbers are model complete in the respective language.

We introduce piecewise interpretable Hilbert spaces and show their relevance to model theory and representation theory. Piecewise interpretable Hilbert spaces are direct limits of imaginary sorts of a continuous logic structure which carry definable Hilbert space operations.   We will show that they offer an interesting unified framework for studying definable measures and Shelah-Galois groups, and that they offer an interesting point of contact between model theory and the theory of unitary group representations. We will briefly discuss a structure theorem for scattered piecewise interpretable Hilbert spaces and we will explain various applications of this theorem. This is joint work with Ehud Hrushovski.

In this talk we will focus on giving an overview of results and on discussing examples. More detailed results will be discussed on Tuesday in the Théorie des Modèles et Groupes seminar.

Milliken's tree theorem states that for every countable, finitely
branching tree T with no leaves, and every finite coloring f of the
strong subtrees of height n, there is an infinite strong subtree over
which the strong subtrees of height n are monochromatic. This theorem
has several applications, among which Devlin's theorem about finite
coloring of the rationals, and a theorem about the Rado graph. In this
talk, we give a survey of the computability-theoretic aspects of these
statements seen as mathematical problems, in terms of instances and
solutions. Our main motivation is reverse mathematics. This is a joint
work with Paul-Elliot Anglès d'Auriac, Peter Cholak and Damir Dzhafarov.
 

Monadic Second-order (MSO) logic is a well-studied formalism featuring many decision procedures and effective transformations. It is the fundamental logic considered in automata theory, equivalent to various other ways of defining sets of objects. In this talk, I will speak about the expressive power of MSO over infinite binary trees (i.e. free structures of two successors) - the theory from the famous Rabin's decidability result.

The goal of the talk is to survey recent results about measure properties of MSO-definable sets of infinite trees. First, I will argue that these sets are indeed measurable (which is not obvious, as there exist non-Borel sets definable in MSO). Then I will move to the question of our ability to compute the measure of the set defined by a given formula. Although the general question is still open (and seems to be demanding), I will speak about decidability results for fragments of MSO, focusing on the so-called weak-MSO.

We study the existence of transformations of the transfinite
plane that allow to reduce Ramsey-theoretic statements concerning
uncountable Abelian groups into classic partition relations for
uncountable cardinals.

This is joint work with Jing Zhang.

In 2005, Kechris, Pestov and Todorcevic exhibited a correspondence
between combinatorial properties of structures and dynamical properties
of their automorphism groups. In 2012, Angel, Kechris and Lyons used
this correspondence to show the unique ergodicity of all the actions of
some groups. In this talk, I will give an overview of the aforementioned
results and discuss recent work generalizing results of Angel, Kechris
and Lyons.

 I will discuss the expansion of the differential field of logarithmic-exponential transseries by its natural exponential function. This expansion is model complete and locally o-minimal. I give an axiomatization of the theory of this expansion that is effective relative to the theory of the real exponential field. These results build on Aschenbrenner, van den Dries, and van der Hoeven's model completeness result for the differential field of transseries. My method can be adapted to show that the differential field of transseries with its restricted sine and cosine and its unrestricted exponential is also model complete and locally o-minimal.

We study the extent to which the Galvin-Mycielski-Solovay
characterization of strong measure zero subsets of the real line
extends to arbitrary Polish group. In particular, we show that
an abelian Polish group satisfies the GMS characterization if and only
if it is locally compact. We shall also consider the non-abelian case,
and discuss the use and existence of invariant submeasures on Polish groups.

(joint with W. Wohofsky, J. Zapletal and/or O. Zindulka)
 

A hereditary graph property is a class of finite graphs closed under isomorphism and induced subgraphs.  Given a hereditary graph property H, the speed of H is the function which sends an integer n to the number of distinct elements in H with underlying set {1,...,n}.  Not just any function can occur as the speed of hereditary graph property.  Specifically, there are discrete ``jumps" in the possible speeds.  Study of these jumps began with work of Scheinerman and Zito in the 90's, and culminated in a series of papers from the 2000's by Balogh, Bollob\'{a}s, and Weinreich, in which essentially all possible speeds of a hereditary graph property were characterized.  In contrast to this, many aspects of this problem in the hypergraph setting remained unknown.  In this talk we present new hypergraph analogues of many of the jumps from the graph setting, specifically those involving the polynomial, exponential, and factorial speeds.  The jumps in the factorial range turned out to have surprising connections to the model theoretic notion of mutual algebricity, which we also discuss. 

This is joint work with Chris Laskowski.

Ultrapowers and reduced powers are two popular tools for studying countable (and separable metric) structures. Once an ultrafilter on N is fixed, these constructions are functors into the category of countably saturated structures of the language of the original structure. The question of the exact 
relation between these two functors has been raised only recently by Schafhauser and Tikuisis, in the 
context of Elliott’s classification programme. Is there an ultrafilter on N such that the quotient map 
from the reduced product associated with the Fréchet filter onto the ultrapower has the right inverse? 
The answer to this question involves both model theory and set theory. 
Although these results were motivated by the study of C*-algebras, all of the results and proofs will 
be given in the context of classical (discrete) model theory.

We show that a universally measurable homomorphism between Polish
groups is automatically continuous. Using our general analysis of
continuity of group homomorphisms, this result is used to calibrate the
strength of the existence of a discontinuous homomorphism between Polish
groups. In particular, it is shown that, modulo ZF+DC, the existence of
a discontinuous homomorphism between Polish groups implies that the
Hamming graph on {0, 1}N has finite chromatic number. This solves a
classical problem originating in JPR Christensen's work on Haar null sets.

Generalizing work of Krasner and Fontaine-Wintenberger on the isomorphism of absolute Galois groups between a mixed characteristic perfectoid field K and its charactersitic p tilt K^flat = prolim_{x -> x^p} K, Scholze introduced a notion of perfectoid adic space and proved an equivalence of category between perfectoid adic spaces over K and over K^flat. The goal of this talk will be to give a model theoretic translation of these results. We will show that, in a well chosen continuous structure, K and K^flat are bi-interpretable and that this immediately yields an equivalence of categories between type spaces over K and K^flat. We will then explain how these result relate to Scholze's results in adic geometry.

This is joint work with Tom Scanlon and Pierre Simon

Soit G un groupe, fixé une fois pour toutes. On s'intéresse aux
sous-décalages sur G de type fini: ce sont les sous-ensembles fermés
G-invariants de {1,...,d}^G définis par un ensemble fini de mots
interdits. Dualement, ce sont aussi les G-algèbres booléennes de
présentation finie.

Plus précisément, on s'intéresse aux problèmes de décision suivants:
est-il décidable, à partir d'une liste de mots interdits, si le
sous-décalage associé est non-vide? ou même mieux s'il contient un
ouvert donné (spécifié par des valeurs sur un ensemble fini de
coordonnées)? Dualement, l'algèbre associée est-elle triviale? ou
a-t-elle problème du mot résoluble?

Ces problèmes ont été surtout considérés pour G=ℤ^2, auquel cas on parle
de «pavages de Wang»; ces deux problèmes sont indécidables.

Selon une conjecture de Jeandel, ces problèmes sont algorithmiquement
résolubles seulement si G a un sous-groupe libre d'indice fini. Je
décrirai l'état du problème, et ajouterai une contribution, obtenue en
collaboration avec Ville Salo: pour le groupe de
l'«allumeur de réverbères» G=ℤ/2≀ℤ.

Ce groupe est important car il apparaît à la frontière entre "arbre"
(groupes libres) et "plan" (Z^2). Nous montrons que son problème de
domino est indécidable.

A finite subset A of a group G is said to have doubling K if the set A\cdot A consisting of products a\cdot b, with a and b in A, has size at most K|A|. Extreme examples of sets with small doubling are cosets of (finite) subgroups.

Theorems of Freiman-Ruzsa type assert that sets with small doubling are "not too far" from being subgroups. Freiman's original theorem asserts that a finite subset of the integers with small doubling is efficiently contained in a generalized arithmetic progression.  A version of this result for abelian groups of bounded exponent was given by Ruzsa:  a finite subset with small doubling K of an abelian group G of exponent r is contained in a subgroupH of G of size bounded by K, r and |A| (but the bound he exhibited is exponential). A natural reformulation of the problem is the polynomial Freiman-Ruzsa conjecture, one of the central open problems in additive combinatorics, which aims to find polynomial bounds (in K) so that any subset A of small doubling K in an infinite-dimensional vector space over F_2 can be covered by finitely many translates of some subspace, whose size is commensurable to the size of A. Improvements of this result have been subsequently obtained by many authors for arbitrary (possibly infinite and non-abelian) groups.

Motivated by work of  E. Hrushovski, we will present on-going work with D. Palacin (Freiburg) and J. Wolf (Cambridge) of Freiman-Ruzsa type under stability, an assumption of model-theoretic nature.

We show that (assuming large cardinals) set theory is a tractable (and we dare to say tame) 
first order theory when formalized in a first order signature with natural predicate symbols for the basic 
definable concepts of second and third order arithmetic, and appealing
to the model-theoretic notions of model completeness and model companionship. 

Specifically we develop a general framework linking 
generic absoluteness results to model companionship and
show that (with the required care in details) 
a $\Pi_2$-property formalized in an appropriate language for second or third order number theory 
is forcible from some 
$T\supseteq\ZFC+$\emph{large cardinals}
if and only if it is consistent with the universal fragment of $T$
if and only if it is realized in the model companion of $T$.

Suppose that a set is definable in the expansion of the real
field by restricted analytic functions, and is also definable in the
expansion of the real field by the restricted exponential function
together with all real power functions. Then the set is definable
using just the restricted exponential function. So additional
exponents can be avoided. I will discuss the general result behind
this, and how it can be seen as a polynomially bounded version of an
old conjecture of van den Dries and Miller. This is joint work with
Olivier Le Gal.

I plan to give an overview of some of the work on descriptive set theory related to the Lebesgue density theorem.
Part of this work is joint with R. Camerlo and C. Costantini, part of it is still unpublished.

Le graphe aléatoire est l'unique graphe dénombrable infini universel (contenant tous les graphes finis comme sous-graphes) et tel que l'action de son groupe d'automorphisme soit ultrahomogène : tout isomorphisme partiel entre des sous-graphes finis s'étend en un automorphisme global du graphe. Il est naturel de se demander quels sont les groupes dénombrables admettant eux-même une action ultrahomogène sur le graphe aléatoire, autrement dit : quels sont les sous-groupes dénombrables denses du groupe d'automorphisme du graphe aléatoire ? Dans cet exposé, on donnera de nouveaux exemples de tels groupes (notamment les groupes de surface), obtenus dans un travail en commun avec Pierre Fima, Julien Melleray et Soyoung Moon.
 

The topic of this talk lies at the intersection of continuous logic and Polish group theory. Inspired by a result of Ben-Yaacov, Rosendal and Tsankov characterising the Roelcke precompact Polish groups as automorphism groups of separably categorical metric structures, we give a characterisation of the locally Roelcke precompact Polish groups, using concepts from continuous model theory. If time permits, we will see how this result applies to the so-called Urysohn diversity - a hypergraph version of metric spaces introduced recently by Bryant, Nies and Tupper. We will give brief introductions to all subjects involved, but hope the audience is somewhat familiar with continuous logic.

Probabilistic Logics are formal languages designed to express properties of probabilistic programs. For most probabilistic logics several key problems are still open. One of such problems is to design convenient analytical proof systems in the style
 of Gentzen sequent calculus. This is practically important in order to simplify the task of proof search: the CUT-elimination theorem greatly reduces the search space. In this talk I will present some recent developments in this direction.

The union of countably many countable sets is countable, assuming the axiom of choice, and its power set is finite or the same size as the real numbers. But what happens without the axiom of choice? We will go over the basic results and slowly builds towards the theorem of D.B. Morris: There is no bound on how many subsets a countable union of countable sets can have.

(Only rudimentary knowledge in set theory is needed.)
 

Fraisse classes are those classes F of finite structures satisfying the Hereditary Property (HP), the Joint Embedding Property (JEP), and the Amalgamation Property (AP). The JEP allows one to build some countably infinite structure K whose age (the collection of finite structures which embed into K) is the class F that we started with. If AP also holds, then there is a canonical such K which we denote K_F, the Fraisse limit of the class. One can interpret this fact dynamically by considering the action of the group S_\infty on the space X_F of countable structures whose age is contained in F. One can give X_F a natural Polish topology, and the theorem of Fraisse is precisely the fact that this action has a comeager orbit. However, Ivanov, and later Kechris-Rosendal, isolated a strictly weaker property, the Weak Amalgamation Property (WAP), which also guarantees that the space X_F has a comeager orbit. This gives rise to a natural question: can we detect the difference between AP and WAP from the dynamical point of view? This talk will discuss an affirmative answer, linking these amalgamation properties to the dynamical notion of a highly proximal extension.

The real/p-adic closures of an ordered/p-valued field need not be complete. Conversely, one may wonder when an ordered/p-valued field is dense in its real/p-adic closures.

We study the property of a field that it is dense in all its real/p-adic closures. We examine when this property is elementary in the language of rings. It is not always elementary, but for fields with finite Pythagoras/p Pythagoras numbers, it is so. In particular we show that this property holds for models of the theory of algebraic fields of characteristic zero. This essentially includes all previously known examples. This is joint work with Philip Dittmann and Arno Fehm.

{\em Cardinal invariants of the continuum} are cardinal numbers describing the combinatorial structure of the  real numbers (the Cantor space $2^\omega$ or the Baire space $\omega^\omega$) and typically taking values between the first uncountable cardinal $\aleph_1$ and the cardinality of the continuum $\mathfrak c$. An example is the unbounding number $\mathfrak b$, the smallest size of a family of functions in $\omega^\omega$unbounded in the eventual dominating ordering. Such cardinal invariants have many applications in areas like general topology, group theory, real analysis, etc. 

While cardinal invariants of the continuum have been investigated intensively for decades, more recently people have started to look at the higher Cantor space $2^\kappa$ and the higher Baire space $\kappa^\kappa$, where $\kappa$ is an uncountable regular cardinal, and redefined analogous cardinals, called {\em higher cardinal invariants},in this context. Many results known for $\omega$ carry over to $\kappa$, in particular in the case when $\kappa$ is a large cardinal. However, there are also several interesting differences between the classical case and higher cardinalinvariants.

I will give a survey on cardinal invariants, starting with the classical case, and then moving to higher invariants.