Logic Seminar

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.