**DaLFI : Duality and Logic in the passage from the Finite to the Infinite**
**17 November 2022, Paris, France**
This workshop brings together two related lines of research, spanning from *set theory* and *model theory* on the one side, to the *duality theory* and its applications to *theoretical computer science* on the other side. The former looks for various combinatorial properties of limits of classes of finite structures, be it ultraproducts, graphons and related limits, or Fraïssé limits. The latter extends correspondences such as that between finite Boolean algebras and finite sets, to the infinite case- through the seminal Stone duality, extended in more recent work combining algebra and topology to provide a mathematical foundation for the syntax-semantics interface. There is much in common between these lines of research, but to our knowledge this will be the first time that a workshop specifically addressing this communality has been organised.
This workshop was originally affiliated to the [FLoC-LICS 2022](https://www.floc2022.org/) conference in Haifa in July 2022, and has been moved to an autonomous format due to organizational matters.
# Schedule
(###) Morning
- 10h00. [Mai Gehrke](https://math.unice.fr/~mgehrke/) (CNRS, LJAD, Université Côte d'Azur): [A duality theoretic view on limits of finite structures](#abstracts/maigehrke:adualitytheoreticviewonlimitsoffinitestructures)
- 10h50 - 11h10. Break.
- 11h10. [Patrice Ossona de Mendez](http://madezhi.free.fr/) (École des Hautes Études en Sciences Sociales): [Structural Limits](#abstracts/patriceossonademendez:structurallimits)
(###) Lunch: 12h-14h
(###) Afternoon
- 14h00. [Sylvy Anscombe](http://www.sylvyanscombe.com/) (IMJ-PRG, Université Paris Cité): [Asymptotic classes of finite structures and their ultralimits](#abstracts/sylvyanscombe:asymptoticclassesoffinitestructuresandtheirultralimits)
- 14h50. [Jérémie Marquès](https://math.unice.fr/laboratoire/fiche%26id%3D964.html) (LJAD, Université Côte d'Azur): [A correspondence between theories of linear orders and profinite semigroups](#abstracts/j%C3%A9r%C3%A9miemarqu%C3%A8s:acorrespondencebetweentheoriesoflinearordersandprofinitesemigroups)
- 15h40 - 16h00. Break.
- 16h00. [Thomas Colcombet](https://www.irif.fr/~colcombe/) (CNRS, IRIF, Université Paris Cité): [Composition and algebra: Uniformisation of MSO over countable ordinals chains](#abstracts/thomascolcombet:compositionandalgebra:uniformisationofmsoovercountableordinalschains)
# Location
Room 1007 of **Bâtiment Sophie Germain**, located at **Pl. Aurélie Nemours, 75013 Paris, France**
([map](https://goo.gl/maps/GNZ7y45a9uqDWzea9)).
# Registration
Registration is free and may be done by sending an e-mail to the organizers, [Mirna Džamonja](mailto:mdzamonja@irif.fr) and [Sam van Gool](mailto:vangool@irif.fr), but walk-ins without registration are very welcome too.
# Abstracts
## Mai Gehrke: A duality theoretic view on limits of finite structures
In this talk I will report on joint work with Tomas Jakl and Luca Reggio (in a paper with the same title as my talk). We analyse the notion of structural limits for finite models developed by Jaroslav Nesetril and Patrice Ossona de Mendez from the point of view of Stone duality. They embed the collection of finite structures in a space of measures, where the desired limits can be computed. We show that a closely related but finer grained space of measures arises via Stone-Priestley duality and the notion of types from model theory by enriching the expressive power of first-order logic with certain probabilistic operators.
This provides a view of their structures as models obtained by duality (or types of a logic) and makes a link to recent work on semiring quantifiers in logic on words.
## Patrice Ossona de Mendez: Structural Limits
Structural convergence consists in the convergence, for each formula in a fixed fragment of first-order logic (FO), of the satisfaction probability of the formula when checked on a tuple of independently and uniformly chosen random elements (or, more generally, on iid elements). Bridges with classical notions of convergence, impacts of the selected fragment of FO driving the convergence as well as the essential importance of the chosen representation of the structures are exemplified through a number of examples, including permutations (represented either as a bijection or as two linear orders).
Three general representation theorems are given. The first one represents structural limits as (Borel) probability distributions on the Stone space dual to the convergence driving fragment of FO, which are invariant under a special action group, generalizing in particular Aldous' exchangeable graph approach. In this setting, structural convergence is equivalent to the weak convergence of associated probability measures. In the second theorem, the limits are represented using Loeb measures on the ultraproduct of the structures in the sequence. Though as is this result may seem highly theoretical, it finds a practical application by ensuring the consistency of some theory in Friedman's extension of first-order logic, thus opening the way to the third representation theorem. This last representation is twofold: in a general setting, it ensures the existence of a measured Borel limit object (modeling) when the convergence is driven by (a bit more than) the fragment of single-variable formulas. From this general version is deduced that a similar limit object exists for full structural convergence (i.e. FO-driven convergence) when the structures in the sequence are bound to a nowhere dense class of structures.
## Sylvy Anscombe: Asymptotic classes of finite structures and their ultralimits
I will discuss several notions — ‘one dimensional asymptotic
classes’ and ‘multidimensional asymptotic classes’ — that are defined
for classes of finite structures, and describe when the sizes of the
definable sets in these structures satisfy certain asymptotic
formulas. There is an infinite counterpart to these definitions: the
‘measurable’ and ‘generalised measurable’ structures. More precisely,
an infinite structure MM is generalised measurable if there is a ‘measuring function’ from
the family of definable sets in MM into a ‘measuring semiring’ (which
are certain ordered semirings) satisfying axioms that are intended to
capture aspects of the intuitive notions of measure and dimension.
The motivating examples for measurable structures as pseudofinite
fields, and in this talk I will give examples of generalised
measurable structures and describe what is known regarding the
stability-theoretic properties of generalised measurable structures.
This is joint work with Macpherson, Steinhorn, and Wolf, and it
generalises the work on one-dimensional asymptotic classes and
measurable structures introduced by Macpherson and Steinhorn in their
2008 paper.
## Jérémie Marquès: A correspondence between theories of linear orders and profinite semigroups
I will talk about a construction associating a first-order theory to each profinite semigroup satisfying a condition called equidivisibility. The semigroup is recovered as the space of 0-types of the corresponding theory. The theories occuring in this way can be characterized as those extending the theory of linear orders and equipped with a "concatenation structure" telling us how models should be concatenated. Examples include monadic second order logic on words (corresponding to the free profinite semigroup), first order logic on words (the free pro-aperiodic monoid), the theory of dense linear orders (the semigroup with one element) and the theory of ordinals.
There is also a variation of this construction for commutative semigroups (the corresponding theories extend the theory of Boolean algebras instead of linear orders) and for ordered semigroups (for intuitionistic or coherent logic instead of Boolean logic).
## Thomas Colcombet: Composition and algebra: Uniformisation of MSO over countable ordinals chains
(based on joint work with Alexander Rabinovich)
The guiding problem of this talk is the uniformisation of monadic second-order logic, which means, given a formula of MSO phi(X), to construct another formula psi(X) which selects, if there is one, a unique X solution of phi(X). In our case, we expect this property to hold over all countable ordinal chains. It is known by Lifsches and Shelah that some MSO-formulae phi(X) do not admit uniformisers on countable ordinal chains. New results states that a uniformiser can always be constructed if we extend MSO with a suitable construct (a built-in uniformiser for a specific formula), and also that one can decide if an MSO formula admits an MSO-uniformiser (and construct it in this case).
The tools involved here are at the junction of logic, in particular involving the composition method of Shelah over infinite chains, and algebra, as inspired by works in language theory initiated by Schützenberger over finite words. This interplay between areas has a long history, but recent works, such as the one presented here, underline its importance.