Logic Seminar

The logic $L_{\omega_1 \omega}$ admits sentences that are infinitely long by allowing countably many conjunctions and disjunctions. In this logic, we can describe countable structures - such as the natural numbers - up to isomorphism (among countable structures) via a single sentence known as the Scott sentence of that structure. The syntactic complexity of a Scott sentence for a structure tells us a host of information about the structure. We consider a finer notion of this complexity than that historically considered in the literature known as the Scott complexity. Next, we discuss computing the Scott complexity for torsion groups. In particular, we will focus on computing the Scott complexity for reduced abelian groups. To do this, we give a characterization of the back-and-forth relations on such groups. This gives a new proof of the fact that reduced abelian groups attain arbitrarily high Scott complexity. Moreover, we can give an explicit example of a sequence of groups which exhibit this behavior, with the Scott complexity strictly increasing with the length of the group.

We study H-fields (certain ordered differential fields generalizing Hardy fields and Transseries) equipped with “constant power maps”. We show that this class has a model companion, the models of which include the field of LE-transseries and any maximal Hardy field. We study the induced structure on the constant field, prove a relative decidability result, and give some applications to certain systems of differential equations.

The k-automatic sets are those subsets of N^d whose base-k representations form a regular language. Building on theorems of Büchi and Bès, we aim to characterize the partial preorder among k-automatic sets of definability over (N, +). We give a conjecture—that this preorder contains exactly three equivalence classes—and discuss our progress toward proving this conjecture. This talk is based on joint work with Alexi Block Gorman (OSU) and Jason Bell (Waterloo).

An ordinary algebraic differential equation is said to be internal to the constants if its general solution is obtained as a rational function of finitely many of its solutions and finitely many constant terms. Such equations give rise to algebraic groups behaving as Galois groups. In this talk I give a characterization of when the pullback of the differential logarithm of an equation is internal to the constants when the Galois group is nilpotent. This is joint work in progress with Leo Jimenez.

Given an abelian group G, a corner is a a subset of pairs of the form $(x,y), (x+d, y), (x, y+d)$ with $d\ne 0$ non trivial. Ajtai and Szemerédi proved that, asymptotically for finite abelian groups, every dense subset S of $G\times G$ contains a corner. Shkredov gave a quantitative lower bound on the density of the subset S. In this talk, we will explain how model-theoretic conditions on the subset S, such as local stability, will imply the existence of corners and of other configurations for (pseudo)-finite abelian groups. This is joint work with D. Palacin (Madrid) and J. Wolf (Cambridge).

Loosely, the Pila-Wilkie Theorem is that if a subset of some finite cartesian power of the real numbers has a lot of rational points, then it either contains an infinite set definable in the real field or defines over the real field a set having infinitely many connected components. But what constitutes "a lot", and why does the proof work? I will attempt a plausible explanation via a much more classical result about paucity of rational points that requires only undergraduate linear algebra and complex analysis.

We will explain how to show that there exist continuum many indecomposable infinite-dimensional representations of the Lie algebra sl(2,k) that satisfy the axioms for a finite-dimensional representation. However, no examples are known.

A structure is omega-categorical if its theory has a unique countable model (up to isomorphism). We will survey some results concerning the Apps-Wilson structure theory for omega-categorical groups and state Wilson’s conjecture on omega-categorical characteristically simple groups. We will also present how the analogous of Wilson’s conjecture for Lie algebras can be disproved using the results of d’Elbée, Muller, Ramsey and Siniora on generic nilpotent Lie algebras.

It is a well-known stability theory result that if p and q are stationary non-orthogonal types over the same set of parameters, then for some n,m, the n-th Morley power of p and the m-th Morley power of q are non-weakly orthogonal. Is there a bound on the smallest such n and m? In this talk, I will present such a bound for differentially closed fields of characteristic zero and give a differential-algebraic interpretation of the result. The proof uses geometric stability machinery to reduce the problem to a question about algebraic group actions. This is part of a joint work with James Freitag and Rahim Moosa.

Transseries emerged in connection with Ecalle's work on Dulac's problem and Dahn and Goering's work on nonstandard models of real exponentiation, and they can often be viewed as asymptotic expansions of solutions to differential equations. A few years ago, decisive results on the model theory and algebra of the differential field of logarithmic-exponential transseries were achieved by Aschenbrenner, van den Dries, and van der Hoeven. Since then, this differential field has been extended to much larger structures encompassing far more rates of growth, for example including solutions to more functional equations. In this talk, I will consider pairs of transseries-like fields, more precisely, two models of the theory of transseries with one a proper extension of the other. My aim is to describe work in progress on the model theory of such pairs, including a model completeness result for them. This follows a long line of model-theoretic work on pairs in different contexts, going back to tame pairs of real closed fields, which our context generalizes.

We apply techniques in computability theory to compare strategies of infinite variants of games. Within a variant of Monty Hall, we showed that a disorderly door-opening strategy is independently strong from a weakly-adaptive door-opening strategy. This result separates two notions of stochasticities. Within the game of chip-firing, we show that there are computable game instances that are winnable, but that do not have a computable winning strategy. We also characterize the index set of computable chip-firing instances as $\Pi_3$-complete. These are joint works with Justin Miller and David Belanger.

A field is said to be bounded if it has finitely many Galois extensions of each finite degree. In an attempt to find a suitable analogue of this notion for differential fields, my advisor and I have obtained some arithmetic results for differential algebraic groups. I will discuss the model theoretic definable Galois cohomology which is used and the motivations for studying boundedness, which come in part from differential Galois theory.

For countable structures, the Scott analysis uses back-and-forth games to assign to each countable structure an ordinal rank which determines how hard it is to determine if some other structure is isomorphic to it. In particular, the collection of isomorphic copies of the structure is Borel, and we can ask for particular structures what the Borel complexity is. I will talk about the start of an attempt to build such an analysis for compact or locally compact topological spaces; the idea is to measure the complexity of classifying a topological space up to homeomorphism.

I will give a survey of recent work on the structure of stable sets in groups, touching on connections to additive combinatorics and number theory. The talk will begin with a very brief elementary introduction to the notion of stability in model theory. I will only assume familiarity with basic definitions in first-order logic.

If U is an open connected subset of R^n and f is a real-valued harmonic function on U, then what can be said about the structure on the real field generated by f? In this generality, the question is only heuristic; indeed, it is rather hopeless without at least some reasonable tameness conditions on the boundary of U (e.g., U=R^n). I will give a brief survey of what I know, including some recent results about exponential terms.

There are compelling and long-established connections between automata theory and model theory, particularly regarding expansions of Presburger arithmetic by sets whose base-k representations are recognized by an automaton. We call such sets "k-regular". In this talk, we will characterize the expansions of (N,<,+) by a unary k-regular set. We can characterize such expansions both in terms of model-theoretic properties, and via notions of "density" coming from arithmetic geometry. This is joint work with Jason Bell and Chris Schulz.

Informally, a real number is normal in base $b$ if in its $b$-ary expansion, all digits and blocks of digits occur as often as one would expect them to, uniformly at random. We will denote the set of numbers normal in base $b$ by $\mathcal{N}(b)$. Kechris asked several questions involving descriptive complexity of sets of normal numbers. The first of these was resolved in 1994 when Ki and Linton proved that $\mathcal{N}(b)$ is $\boldsymbol{\Pi}_3^0$-complete. Further questions were resolved by Becher, Heiber, and Slaman who showed that $\bigcap_{b=2}^\infty \mathcal{N}(b)$ is $\boldsymbol{\Pi}_3^0$-complete and that $\bigcup_{b=2}^\infty \mathcal{N}(b)$ is $\boldsymbol{\Sigma}_4^0$-complete. Many of the techniques used in these proofs can be used elsewhere. We will discuss recent results where similar techniques were applied to solve a problem of Sharkovsky and Sivak and a question of Kolyada, Misiurewicz, and Snoha. Furthermore, we will discuss a recent result where the set of numbers that are continued fraction normal, but not normal in any base $b$, was shown to be complete at the expected level of $D_2(\boldsymbol{\Pi}_3^0)$. An immediate corollary is that this set is uncountable, a result (due to Vandehey) only known previously assuming the generalized Riemann hypothesis.

This talk will survey some connections between model theory and combinatorics.

Dp-minimality is a kind of abstract model-theoretic "one-dimensionality" condition, satisfied for example by superstable theories of U-rank 1 and o-minimal theories. In this talk we will introduce dp-minimality, and then discuss some results on dp-minimal groups: namely, every torsion-free dp-minimal group is abelian, and every dp-minimal group that is "generically unstable", in a sense we will discuss, is nilpotent-by-finite.

The free amalgamation theories introduced by Conant (2017) axiomatize certain independence relations in homogeneous structures, such as the random graphs and the generic K_n-free graphs. Conant shows that all modular free amalgamation theories are simple or SOP₃, and this result turns out to be connected to some central open problems in the classification of unstable structures. Answering a question of Conant, we have shown that the generic constructions of Kruckman and Ramsey (2018) give examples of non-modular free amalgamation theories; we have also shown that all free amalgamation theories, even non-modular ones, are either NSOP₁ or SOP₃. By generalizing a version of Conant’s free amalgamation axioms, we isolate two structural properties with no known NSOP₄ counterexamples which, together, imply that a theory is NSOP₁ or SOP₃. We explain how these generalized free amalgamation axioms relate these two properties, by relativizing Chernikov and Ramsey (2016) and Kaplan and Ramsey (2020)’s theory of Kim-independence in NSOP₁. When this relative version of NSOP₁ holds, we obtain symmetry for a recently introduced absolute independence relation, Conant-independence, which as in the strong Kim-dividing of Kaplan, Ramsey and Shelah (2017) represents forking-independence at a maximally generic scale (rather than at the “generic scale” of Kaplan and Ramsey (2020)). Symmetry for Conant-independence reveals not only the surprising significance of the class NSOP₄, but also new connections between two of the core problems of classification theory: on one hand, extending the theory of independence beyond NSOP₁, and on the other hand, whether NSOP₂ = NSOP₃ and whether the higher NSOP_n hierarchy is strict within NTP₂.

Existentially closed groups were introduced by WR Scott in 1951 in analogue with algebraically closed fields. Since then, they have been further studied by Neumann, Macintyre, and Ziegler, who elucidated deep connections with model theory and computability theory. We review some of the literature on existentially closed groups and present new results that further refine these connections.

There are compelling and long-established connections between automata theory and model theory, particularly regarding expansions of Presburger arithmetic by sets that are "recognized" by a DFA in a certain well-defined sense. Büchi automata are the natural extension of DFAs and NFAs to a model of computation that accepts infinite-length inputs. We say a subset X of the reals is Büchi-automatic if there some natural number r and some Büchi automaton that accepts (one of) the base-r representations of every element of X, and rejects the base-r representations of each element in its complement. We can analogously define Büchi-automatic subsets of higher arities, and these sets exhibit intriguing behavior from the perspectives of both fractal geometry and tame geometry. In this talk, we will have the opportunity to discuss standard or Büchi automata, how each of these fit into the framework of tameness in their respective settings, and what work has been done to characterize structures in which every definable set is recognized by an automaton either of the standard or Büchi variety.

The Lazard Correspondence is a characteristic p analogue of the correspondence between nilpotent Lie groups and Lie algebras, associating to every nilpotent group of exponent p and nilpotence class c a Lie algebra over F_p with the same nilpotence class (assuming c < p). We will describe the role that this translation between nilpotent group theory and linear algebra has played in an emerging program to understand the first order properties of random nilpotent groups. In this talk, we will focus on connections to neostability theory, highlighting the way that nilpotent groups furnish natural algebraic structures in surprising parts of the SOP_n and n-dependence hierarchies. This is joint work with Christian d'Elbée, Isabel Müller, and Daoud Siniora.

One of the most important technical steps in the development of simplicity theory in the 1990s was a result now known as Kim's Lemma: In a simple theory, if a formula phi(x;b) divides over a model M, then phi(x;b) divides along every Morley sequence in tp(b/M). More recently, variants of Kim's Lemma have been shown by Chernikov, Kaplan, and Ramsey to follow from, and in fact characterize, two generalizations of simplicity in different directions: the combinatorial dividing lines NTP1 (which is now known to be equivalent to NSOP1 and NSOP2) and NTP2. After surveying the Kim's Lemmas of the past, I will suggest a new variant of Kim's Lemma, as well as a new model-theoretic tree property, BTP, which implies this new Kim’s Lemma and generalizes both TP1 and TP2. I will also compare this new tree property with the Antichain Tree Property (ATP), another tree property generalizing both TP1 and TP2, which was introduced recently by Ahn and Kim. This is joint work with Nick Ramsey.

Olivier's construction of the universal commutative (von Neumann) regular ring over a commutative ring is generalized to obtain the universal *-regular ring over a noncommutative ring (R, *) with involution. The construction of a universal *-regular ring proceeds similarly with the Moore–Penrose inverse replacing the role of the group inverse in the construction of universal abelian regular rings.

The involution of (R, *) induces an involution on the modular lattice L(R, 1) of positive primitive formulae in the language of left R-modules. It is shown that *-regular ring coordinatizes the quotient lattice of L(R, 1) modulo the least congruence for which the involution designates an orthogonal complement.

Some explicit examples will be given in the context of some algebras, as the Jacobson algebra. This is joint work with Ivo Herzog.

In this talk we will introduce a precursor to techniques that will be used in the logic seminar talk (3/21) by Sonia L'Innocente. There is a proper way, rooted in the work of von Neumann, to formally adjoin idempotent elements to a ring so as to eliminate the existential quantifier in positive primitive formulae that express divisibility conditions. The result of iterating this procedure to a ring R yields its abelian regularization, a noncommutative generalization of a construction due to Olivier from the 60's. It allows us to describe the ring of definable scalars of the direct sum of all division R-rings as an étale bundle over the Cohn spectrum of R. If time permits, we hope to mention the role of Hua's identity in this context. This is joint work with Sonia L'Innocente.

Eventual polynomial growth is a common theme in combinatorics and commutative algebra. The quintessential example of this phenomenon is the Hilbert polynomial, which eventually coincides with the linear dimension of the graded pieces of a finitely generated module over a polynomial ring. A later result of Kolchin shows that the transcendence degree of certain field extensions of a differential field is eventually polynomial. More recently, Khovanskii showed that for finite subsets A and B of a commutative semigroup, the size of the sumset A+tB is eventually polynomial in t. I will present a common generalization of these three results in terms of finitary matroids (also called pregeometries). Time permitting, I’ll discuss other instances of eventual polynomial growth (like the Betti numbers of a simplicial complex) and how these polynomials can be used to bound model-theoretic ranks (like thorn-rank). This is joint work with Antongiulio Fornasiero.

It is unknown whether there are o-minimal fields that are "transexponential", i.e., which define functions that eventually grow faster than any tower of exponential functions. In recent work, I constructed a Hardy field closed under a transexponential function which satisfies E(x+1) = exp E(x). Since the unary definable functions in an o-minimal structure form a Hardy field, this can be seen as evidence that the real field expanded by E could be o-minimal. To actually prove o-minimality, a better understanding of definable functions in several variable is likely needed. I will discuss one approach arising from Wilkie’s proof that the real exponential field is o-minimal. This ongoing work is joint with Vincent Bagayoko and Elliot Kaplan.

In the second of two talks, I will use the work discussed in the first talk to prove a nonabelian analogue of the Bogolyubov–Ruzsa Lemma, which is a fundamental result in additive combinatorics about large subsets of abelian groups. This will include some slight simplifications to the original proof using the language of continuous logic. (The first talk will be treated as a black box, and thus is not required for understanding the second talk.)

In the first of two talks, I will discuss pseudofinite structures and groups, as well as the notion of a "definable" compactification. Then I will present a new proof of a result of Pillay that any definable compactification of a pseudofinite group has an abelian connected component. Pillay's original proof used a powerhouse theorem of Breuillard, Green, and Tao on the structure of approximate groups. The new proof is much simpler, and uses only classical tools from harmonic analysis and representation theory of compact groups (along with work from one surprise name).

(Joint Geometric Group Theory–Logic Seminar) Classical theorems of Novikov, Boone, and Higman establish important connections between recursive and recursively enumerable sets on the one hand and the theory of finitely presented groups on the other hand. Despite the groundbreaking nature of these results, not much is known about possible extensions of those results to the realm of higher Turing degrees. My talk will be a contribution in this direction.

In my talk, I will discuss how one can view Turing degrees through invariants coming from geometric group theory. In particular, I will introduce a new quasi-isometric invariant, called (λ, μ)-taut filling spectra, and will show how this invariant can grasp Turing degrees of arbitrary degrees. Through these means, we will also introduce an interesting special class of functions, called Turing saturated maps, which will be useful for our applications.

As a main application, we will discuss a purely geometric group theoretical result that establishes quasi-isometric diversity of f.g. left-orderable simple groups, which is an important class of groups discovered by Hyde and Lodha. Previous attempts to obtain this result through more usual geometric/algebraic tools have not succeeded, which emphasizes the importance of the idea of Turing degrees in this context.

The talk is aimed to have an expository component on concepts from geometric group theory.

We explain how the model-invariant rules of inference of Core Logic (in natural deduction: introduction and elimination rules; in sequent calculus: Right and Left rules) arise naturally from the model-relative rules of evaluation (verification and falsification) by simple 'morphing'. We then explain how two important features of the rules for core proof provide constraints on 'bottom-up' proof search, without loss of completeness. Relevance of premises to conclusions is always preserved. So too are any epistemic gains made when pursuing solutions to the deductive sub-problems posed in the course of search.

We will show that if $T$ is a VC minimal theory (e.g. ACVF) and $M\models T$, then for any $d$ and any definable relation $E(x,y)\subseteq M^2$ of complexity $\leq d$ in Swiss Cheese decomposition, there is $k_d>0$ such that for any disjoint finite $A,B\subseteq M$, there exist $A'\subseteq A$, $B'\subseteq B$ with $|A'|\geq k_d |A|$, $|B'|\geq k_d |B|$ such that $A'\times B' \subseteq E$ or $A'\times B'\subseteq\neg E$.

We show positive primitive elimination for abelian structures with a homomorphism to a compact group, in analogy to the classical result for modules, as in [Ziegler, 1984]. To do this, we first develop an appropriate logic to handle these "enriched" structures and define the correct analogues of positive primitive-formulas. We finish by showing that this elimination result implies stability of the structure. This is joint work with Anand Pillay.

In a game of casino versus gamblers, a casino has infinitely many pennies, each hidden under a cup. The cups are arranged in a line, and some are empty. A gambler picks infinitely many cups, selecting the next cup after checking the contents of the previously selected ones. A gambler wins if the density of the selected cups with pennies is non-zero. Gamblers are allowed to be disorderly, selecting cup i after selecting cup j>i. Are disorderly gamblers more difficult to beat than orderly ones? The statement is true if gamblers are also adaptive, where they may select a different cup depending on the outcomes of the uncovered ones. We show that the claim also holds in the non-adaptive setting. The proof involves infinitary combinatorial arguments. This is joint work with Justin Miller.

The countable abelian p-groups that have no divisible summands are determined, up to isomorphism, by their Ulm invariants. This classification can be used to determine the homogeneous countable abelian p-groups. One such abelian p-group turns out to be a universal countable abelian p-group for purity, i.e., every countable abelian p-group admits a pure embedding into it. It is the last step needed to complete the solution to Fuchs' Problem 5.1 below ℵ_ω.

We will start off with some background, including how Ulm's Theorem is used to obtain a Scott sentence as well as some motivating examples. This is joint work with Marcos Mazari Armida.

Let T be a suitably nice o-minimal theory extending the theory of real closed fields. A T-convex T-differential field is an expansion of a model of T by a valuation and a derivation, each of which is compatible with the o-minimal structure, the former in the T-convex sense of van den Dries–Lewenberg and the latter in the sense of Fornasiero–Kaplan. When T is the theory of the real field with restricted analytic functions, we can expand an ordered differential Hahn field (a kind of generalized power series field) to a T-convex T-differential field, in which case the derivation is monotone, i.e., weakly contractive with respect to the valuation (monotone differential Hahn fields were studied earlier by Scanlon and Hakobyan). I will describe joint ongoing work with Kaplan on monotone T-convex T-differential fields, achieving among other results an Ax–Kochen/Ershov type theorem for such structures. A key step is isolating an appropriate analogue of henselianity in this setting. I will explain these terms.

Motivated by the theory of domination for types, we introduce a notion of domination for Keisler measures called extension domination. We argue that this variant of domination behaves similarly to its type setting counterpart. We prove that extension domination extends domination for types and that it forms a preorder on the space of global Keisler measures. We then explore some basic properties related to this notion. This is joint work with Jinhe Ye.

In this talk, I will outline a technique for showing that nonlinear algebraic differential equations are strongly minimal. This is used to prove the strong minimality of generic differential equations with sufficiently large degree, answering a question of Poizat (1980). I will also discuss ongoing work in applying this method to differential equations of interest whose coefficients are not generic. This is joint work with James Freitag.