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

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.