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

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.