Past Logic Seminar

In his pioneering and celebrated 1968 paper on the elementary theory of finite fields Ax asked if the theory of the class of all the finite rings $\mathbb{Z}/m\mathbb{Z}$, for all $m>1$, is decidable. In that paper, Ax proved that the existential theory of this class is decidable via his result that the theory of the class of all the rings $\mathbb{Z}/p^n\mathbb{Z}$ (with $p$ and $n$ varying) is decidable. This used Chebotarev’s Density Theorem and model theory of pseudo-finite fields.

I will talk about a recent solution jointly with Angus Macintyre of Ax’s Problem using model theory of the ring of adeles of the rational numbers.

We will construct several algebras of functions definable in R_{an,\exp} which are stable under parametric integration. 

Given one such algebra A, we will study the parametric Mellin and Fourier transforms of the functions in A. These are complex-valued oscillatory functions, thus we leave the realm of o-minimality. However, we will show that some of the geometric tameness of the functions in A passes on to their integral transforms.

I will explain how the model-theoretic algebraic closure in Zilber’s pseudo-exponential field can be described in terms of the self-sufficient closure. I will sketch a proof and show how the Mordell-Lang conjecture for algebraic tori comes into play. If time permits, I’ll also talk about the characterisation of strongly minimal sets and their geometries. This is joint work (still in progress) with Jonathan Kirby.

Zarankiewicz's problem for hypergraphs asks for upper bounds on the number of edges of a hypergraph that has no complete sub-hypergraphs of a given size. Let M be an o-minimal structure. Basit-Chernikov-Starchenko-Tao-Tran (2021) proved that the following are equivalent:

(1) "linear Zarankiewicz's bounds" hold for hypergraphs whose edge relation is induced by a fixed relation definable in M

(2) M does not define an infinite field.

We prove that the following are equivalent:

(1') linear Zarankiewicz bounds hold for sufficiently "distant" hypergraphs whose edge relation is induced by a fixed relation definable in M

(2') M does not define a full field (that is, one whose domain is the whole universe of M).

This is joint work (in progress) with Aris Papadopoulos.

I will discuss the following statement, a definable version of the (p,q) theorem of Jiří Matoušek from combinatorics, conjectured by Chernikov and Simon:

Suppose that T is NIP and that phi(x,b) does not fork over a model M. Then there is some formula psi(y) in tp(b/M) such that the partial type {phi(x,b’) : psi(b’)} is consistent.

Given a cover U of a family of smooth complex algebraic varieties, we associate with it a class C of structures locally definable in an o-minimal expansion of the reals, containing the cover U.  We prove that the class is ℵ0-homogeneous over submodels and stable. It follows that C is categorical in cardinality ℵ1. In the one-dimensional case we prove that a slight modification of C is an abstract elementary class categorical in all uncountable cardinals.
 

We call affine logic the fragment of continuous logic in which the connectives are limited to linear combinations and the constants (but quantification is allowed, in the usual continuous form). This fragment has been introduced and studied by S.M. Bagheri, the first to observe that this is the appropriate framework to consider convex combinations of metric structures and, more generally, ultrameans, i.e., ultraproducts in which the ultrafilter is replaced by a finitely additive probability measure. Bagheri has shown that many fundamental results of continuous logic hold in affine logic in an appropriate form, including Łoś's theorem, the compactness theorem, and the Keisler--Shelah isomorphism theorem.

In affine logic, type spaces are compact convex sets. In this talk I will report on an ongoing work with I. Ben Yaacov and T. Tsankov, in which we initiate the study of extremal models in affine logic, i.e., those that only realize extreme types.

From a model theoretic point of view, local fields of positive characteristic, i.e. fields of Laurent series over finite fields, are much less well understood than their characteristic zero counterparts - the fields of real, complex and p-adic numbers. I will discuss different approaches to axiomatize and decide at least their existential theory in various languages and under various forms of resolution of singularities. This includes new joint work with Sylvy Anscombe and Philip Dittmann.

A theorem of Chatzidakis, van den Dries and Macintyre, stemming ultimately from the Lang-Weil estimates, asserts, roughly, that if $\phi(x,y)$ is a formula in the language of rings (where $x,y$ are tuples) then the size of the solution set of $\phi(x,a)$ in any finite field $F_q $(where $a$ is a parameter tuple from $F_q$) takes one of finitely many dimension-measure pairs as $F_q$ and $a$ vary: for a finite set $E$ of pairs $(\mu,d)$ ($\mu$ rational, $d$ integer) dependent on $\phi$, any set $\phi(F_q,a)$ has size roughly $\mu q^d$ for some $(\mu,d) \in E$.

This led in work of Elwes, Steinhorn and myself to the notion of 'asymptotic class’ of finite structures (a class satisfying essentially the conclusion of Chatzidakis-van den Dries-Macintyre). As an example, by a theorem of Ryten, any family of finite simple groups of fixed Lie type forms an asymptotic class. There is a corresponding notion for infinite structures of  'measurable structure’ (e.g. a pseudofinite field, by the Chatzidakis-van den Dries-Macintyre theorem, or certain pseudofinite difference fields).

I will discuss a body of work with Sylvy Anscombe, Charles Steinhorn and Daniel Wolf which generalises this, incorporating a richer range of examples with fewer model-theoretic constraints; for example, the corresponding infinite 'generalised measurable’ structures, for which the definable sets are assigned values in some ordered semiring, need no longer have simple theory. I will also discuss a variant in which sizes of definable sets in finite structures are given exactly rather than asymptotically.

The Skolem Problem asks to decide whether a linearly recurrent sequence (LRS) over the rationals has a zero term.  It is sometimes considered as the halting problem for linear loops.   In this talk we will give an overview of two current approaches to establishing decidability of this problem.  First, we observe that the Skolem Problem for LRS with simple characteristic roots is decidable subject to the $p$-adic Schanuel conjecture and the exponential-local-global principle.  Next, we define a set $S$ of positive integers such that (i) $S$ has positive lower density and (ii) The Skolem Problem is decidable relative to $S$, i.e., one can effectively determine the set of all zeros of a given LRS that lie in $S$.

The talk is based on joint work with Y. Bilu, F. Luca, J. Ouaknine, D. Pursar, and J. Nieuwveld.  

We study the definability of valuation rings in ordered fields (in the language of ordered rings). We show that any henselian valuation ring that is definable in the language of ordered rings is already definable in the language of rings. However, this does not hold when we drop the assumption of henselianity.

This is joint work with Philip Dittmann, Sebastian Krapp and Salma Kuhlmann.

In this talk, we discuss existentially closed measure preserving actions of countable groups.  A classical result of Berenstein and Henson shows that the model companion for this class exists for the group of integers and their analysis readily extends to cover all amenable groups.  Outside of the class of amenable groups, relatively little was known until recently, when Berenstein, Henson, and Ibarlucía proved the existence of the model companion for the case of finitely generated free groups.  Their proof relies on techniques from stability theory and is particular to the case of free groups.  In this talk, we will discuss the existence of model companions for measure preserving actions for the much larger class of universally free groups (also known as fully residually free groups), that is, groups which model the universal theory of the free group.  We also give concrete axioms for the subclass of elementarily free groups, that is, those groups with the same first-order theory as the free group.  Our techniques are ergodic-theoretic and rely on the notion of a definable cocycle.  This talk represents ongoing work with Brandon Seward and Robin Tucker-Drob.

MSO can be used not only to accept/reject words, but also to transform words into other words, e.g. the doubling function w $\mapsto$ ww. The traditional model for this is called MSO transductions; the idea is that each position of the output word is interpreted in some position of the input word, and MSO is used to define the order on output positions and their labels. I will explain that an extension, where output positions are interpreted using $k$-tuples of input positions, is (a) is also well behaved; and (b) this is surprising.

We introduce a classification tool for mathematical theories based on Robinson's notion of model companionship; roughly the idea is to attach to a mathematical theory $T$ those signatures $L$ such that $T$ as axiomatized in $L$ admits a model companion. We also introduce a slight strengthening of model companionship (absolute model companionship - AMC) which characterize those model companionable $L$-theories $T$ whose model companion is axiomatized by the $\Pi_2$-sentences for $L$ which are consistent with the universal theory of any $L$-model of $T$.

We use the above to analyze set theory, and we show that the above classification tools can be used to extract (surprising?) information on the continuum problem.

Previous joint work with Caroline Terry had identified model-theoretic stability as a sufficient condition for the existence of strong arithmetic regularity decompositions in finite abelian groups, pioneered by Ben Green around 2003. 
Higher-order arithmetic regularity decompositions, based on Tim Gowers’s groundbreaking work on Szemerédi’s theorem in the late 90s, are an essential part of today's arithmetic combinatorics toolkit.
In this talk, I will describe recent joint work with Caroline Terry in which we define a natural higher-order generalisation of stability and prove that it implies the existence of particularly efficient higher-order arithmetic regularity decompositions in the setting of finite elementary abelian groups. If time permits, I will briefly outline some analogous results we obtain in the context of hypergraph regularity decompositions.

Several natural measures of complexity can be attached to an
existentially definable ("diophantine") subset of a field. One of these
is the minimal number of existential quantifiers required to define it,
while others are of a more geometric nature. I shall define these
measures and discuss interesting interactions and behaviours, some of
which depend on properties of the field (e.g. imperfection and
ampleness). We shall see for instance that the set of n-tuples of field
elements consisting of n squares is usually definable with a single
quantifier, but not always. I will also discuss connections with
Hilbert's 10th Problem and a number of open questions.
This is joint work with Nicolas Daans and Arno Fehm.

In this talk, we describe some recent work on applying tools from category theory in finite model theory, descriptive complexity, constraint satisfaction, and combinatorics.

The motivations for this work come from Computer Science, but there may be something of interest for model theorists and other logicians.

The basic setting involves studying the category of relational structures via a resource-indexed family of adjunctions with some process category - which unfolds relational structures into treelike forms, allowing natural resource parameters to be assigned to these unfoldings.

One basic instance of this scheme allows us to recover, in a purely structural, syntax-free way:

- the Ehrenfeucht-Fraisse game

- the quantifier rank fragments of first-order logic

- the equivalences on structures induced by (i) the quantifier rank fragments, (ii) the restriction to the existential-positive part, and (iii) the extension with counting quantifiers

- the combinatorial parameter of tree-depth (Nesetril and Ossona de Mendez).

Another instance recovers the k-pebble game, the finite-variable fragments, the corresponding equivalences, and the combinatorial parameter of treewidth.

Other instances cover modal, guarded and hybrid fragments, generalized quantifiers, and a wide range of combinatorial parameters.

This whole scheme has been axiomatized in a very general setting, of arboreal categories and arboreal covers.

Beyond this basic level, a landscape is beginning to emerge, in which structural features of the resource categories, adjunctions and comonads are reflected in degrees of logical and computational tractability of the corresponding languages.

Examples include semantic characterisation and preservation theorems, Lovasz-type results on  isomorphisms, and classification of constraint satisfaction problems.

The curve graph of a surface of finite type is a fundamental object in the study of its mapping class group both from the metric and the combinatorial point of view. I will discuss joint work with Valentina Disarlo and Thomas Koberda where we conduct a thorough study of curve graphs from the model theoretic point of view, with particular emphasis in the problem of interpretability between different curve graphs and other geometric complexes.   

(This is Part II of a two-part talk.)

Forcing axioms spell out the dictum that if a statement can be forced, then it is already true. The P_max axiom (*) goes beyond that by claiming that if a statement is consistent, then it is already true. Here, the statement in question needs to come from a resticted class of statements, and "consistent" needs to mean "consistent in a strong sense". It turns out that (*) is actually equivalent to a forcing axiom, and the proof is by showing that the (strong) consistency of certain theories gives rise to a corresponding notion of forcing producing a model of that theory. Our result builds upon earlier work of R. Jensen and (ultimately) Keisler's "consistency properties".

Forcing axioms spell out the dictum that if a statement can be forced, then it is already true. The P_max axiom (*) goes beyond that by claiming that if a statement is consistent, then it is already true. Here, the statement in question needs to come from a resticted class of statements, and "consistent" needs to mean "consistent in a strong sense". It turns out that (*) is actually equivalent to a forcing axiom, and the proof is by showing that the (strong) consistency of certain theories gives rise to a corresponding notion of forcing producing a model of that theory. Our result builds upon earlier work of R. Jensen and (ultimately) Keisler's "consistency properties".

(This is Part I of a two-part talk.)

This talk will be about the stable boundary seen from different recent points of view.

Sela proved in 2006 that the (non abelian) free groups are stable. This implies the existence of a well-behaved forking independence relation, and raises the natural question of giving an algebraic description in the free group of this model-theoretic notion. In a joint work with Rizos Sklinos we give such a description (in a standard fg model F, over any set A of parameters) in terms of the JSJ decomposition of F over A, a geometric group theoretic tool giving a group presentation of F in terms of a graph of groups which encodes much information about its automorphism group relative to A. The main result states that two tuples of elements of F are forking independent over A if and only if they live in essentially disjoint parts of such a JSJ decomposition.