The Online Logic Seminar meets weekly on Thursdays at 1pm US Central Time (currently UTC-5) on Zoom. You can connect to the live seminar by clicking here, or by joining the Zoom meeting with Meeting ID 122 323 340.

In cases where I have slides, or a link to them, I have a link from the title of the talk.

**March 16:****Speaker:**Jenna Zomback (Williams College)**Title:**Weak mixing for semigroup actions and applications to pointwise ergodic theorems**Abstract:**We provide a sufficient condition for the natural boundary action of free semigroups to be weak mixing. This result yields new pointwise ergodic theorems for free semigroup actions, where the averages are taken along trees. This is joint work with Anush Tserunyan.

**March 23:****Speaker:**Athar Abdul-Quader (Purchase College)**Title:**Arithmetic Saturation and Pathological Satisfaction**Abstract:**A classic result in models of arithmetic states that countable models of PA are recursively saturated if and only if they possess a "full satisfaction class". A satisfaction class is a set of pairs (phi, alpha), where phi is a code for a formula in the sense of the model, and alpha is an assignment for that formula, which extends the "standard" satisfaction relation, and satisfies Tarksi's compositional rules for satisfaction. Recently, there has been work on so-called pathological satisfaction classes: satisfaction classes which exhibit certain pathologies, like, for example, making sentences of the form "(0 = 1) or (0 = 1) or ... or (0 =1)" of nonstandard length true. We study these pathologies, and find a surprising relationship between the question of determining which sets can be defined using certain pathologies, and a stronger notion of saturation, arithmetic saturation. This is joint work with Mateusz Łełyk, based heavily on unpublished work by Jim Schmerl.

**March 30:****Speaker:**Elliot Kaplan (McMaster University)**Title:**Hilbert polynomials for finitary matroids**Abstract:**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). I'll discuss other instances of eventual polynomial growth (like the Betti numbers of a simplicial complex) as well as some applications to bounding model-theoretic ranks. This is joint work with Antongiulio Fornasiero.

**April 6:**Sandra Müller (TU Wien)**April 13:**TBA**April 20:**Rumen Dimitrov (Western Illinois University)**April 27:**Cian Dorr (New York University)**May 4:**Daniel Mourad (University of Connecticut)**May 11:**Una Stojnić (Princeton University)

**August 24:**TBA**August 31:**TBA**September 7:**TBA**September 14:**TBA**September 21:**TBA**September 28:**TBA**October 5:**Thomas Icard (Stanford University)**October 12:**TBA**October 19:**TBA**October 26:**TBA**November 2:**TBA**November 9:**TBA**November 16:**TBA**November 23:**No seminar: Public holiday in USA for Thanksgiving**November 30:**TBA**December 7:**TBA**December 14:**TBA

**April 2:****Speaker:**Noah Schweber**Title:**(Not) Computing linear orders**Abstract:**I'll talk about the general problem of controlling Medvedev (= uniform) reductions between linear orders - specifically, between a linear order and its endpointed intervals.The earliest examples of linear orders not Medvedev above some of their endpointed intervals (due to the speaker) were well-orders - roughly speaking, any two distinct "sufficiently $\omega_1$-like" well-orders are Medvedev-incomparable, and we can always view the smaller as an endpointed initial segment of the larger. Annoyingly, these examples are quite large and the nontrivial relationships between even relatively concrete well-orders (e.g. the $\omega_n^{CK}$s for finite $n$) are still open; later, Julia Knight and Alexandra Soskova gave a much simpler example of a linear order having an endpointed interval which it does not uniformly compute and is low in the arithmetical hierarchy.

I will present two additional examples, intended to flesh out this picture:

- A scattered linear order with infinitely many endpointed intervals it does not Medvedev-compute.
- A (noncomputable) linear order with no nontrivial Medvedev reductions between it and its endpointed intervals at all, in a precise sense.
- Each is low in the arithmetical hierarchy. Moreover, these constructions generalize appropriately to general uniform reducibility notions in a direct way.

If time remains, I will present some separate work motivated by trying to find simpler Medvedev-incomparable well-orders.

**April 9:****Speaker:**Natasha Dobrinen (University of Denver)**Title:**Ramsey properties on infinite structures**Abstract:**Just how far can Ramsey's Theorem on the natural numbers be pushed when, instead of coloring all k-sized subsets of the natural numbers, one is coloring copies of a finite structure inside some infinite structure? There is a host of results extending the finite Ramsey theorem to classes of finite structures, but much less so for the infinite Ramsey Theorem. I will give some overview of results known so far and some current work aimed towards showing that a wider class of known finite Ramsey classes also have infinite Ramsey theorems. It should be noted that the infinite Ramsey theorems on infinite structures rarely yield one color; usually the best possible is to obtain finite bounds called "big Ramsey degrees."

**April 16:****Speaker:**Sam Sanders (TU Darmstadt)**Title:**Plato and Brouwer, sitting in a binary tree.**Abstract:**I will describe recent developments in my joint project with Dag Normann on the Reverse Mathematics and computability theory of the uncountable. Now, Reverse Mathematics classifies theorems of ordinary, i.e. non-set theoretic, mathematics according to which comprehension (or set existence) axioms are needed for a proof. The associated 'Big Five' systems, said to capture most of ordinary mathematics, fit neatly into the larger Gödel hierarchy. In contrast to this received view, we identify a plethora of theorems of ordinary mathematics that live 'in between' the medium and strong levels of the Gödel hierarchy. To make sense of this observation, we propose an alternative to comprehension, namely a hierarchy based on (classically valid) continuity axioms from Brouwer's intuitionistic mathematics. We also show that the Big Five are merely a reflection of this new hierarchy, akin to Plato's allegory of the cave.

**April 23:****Speaker:**Mariya Soskova (University of Wisconsin, Madison)**Title:**Fragments of the theory of the enumeration degrees**Abstract:**I will present recent joint work with Ted Slaman and Steffen Lempp. We consider the problem of finding the quantifier level where the theory of the partial order of the enumeration degrees becomes undecidable. It is well known that the existential theory is decidable. We establish that the 3-quantifier theory is undecidable. We show that a fragment of the 2-quantifier theory, known as the extension of embeddings problem is decidable and discuss possible approaches and obstacles towards a decision procedure for the full 2-quantifier theory.

**April 30:****Speaker:**Margaret Thomas (Purdue)**Title:**Point counting and parameterizations**Abstract:**The theory of o-minimality as a framework for `tame geometry' was first developed within model theory in the 1980s. Among its widespread applications across mathematics has been a highly influential interaction with diophantine geometry, initiated by the seminal `point counting theorem' of Pila and Wilkie and leading to critical developments on `special points' problems such as the Manin--Mumford and André--Oort Conjectures.The pursuit of improvements to the Pila--Wilkie Theorem remains an active area of research, in several different directions. These are motivated by potential diophantine applications, but are centred on the inherent nature of the definable sets involved. Time permitting, we will discuss various aspects of this pursuit, related to geometric smooth parameterization, effectivity, and the importance of certain key systems of differential equations.

**May 7:****Speaker:**Rebecca Coulson (US Military Academy)**Title:**The Bipartite Diameter 3 Metrically Homogeneous Graphs of Generic Type: Their Ages and Their Almost Sure Theories**Abstract:**The class of random graphs famously satisfies a zero-one law: every first-order sentence in the language of graphs is such that the proportion of finite graphs on n vertices which satisfy this sentence goes either to zero or to one as n goes to infinity. The "almost-sure" theory of the class of finite graphs matches the generic theory of its Fraisse limit - the Rado graph. Interestingly, the almost-sure theory of the class of finite triangle-free graphs does not match the theory of the generic triangle free graph. In this talk, we will discuss another class of graphs which are Fraisse limits defined by forbidden configurations, and we examine two such graphs in particular. We show that for one of the them, its generic theory does match the corresponding almost-sure theory, and that for the other, the generic theory does not match the corresponding almost-sure theory.

**May 14:****Speaker:**Chris Porter (Drake University)**Title:**Randomness Extraction from a Computability-Theoretic Perspective**Abstract:**The goal of this talk is to discuss recent work, joint with Doug Cenzer, on a notion of the extraction rate of Turing functionals that translate between notions of randomness with respect to different underlying probability measures. We will analyze several classes of extraction procedures: a first that generalizes von Neumann's trick for extracting unbiased randomness from the tosses of a biased coin, a second based on work of generating biased randomness from unbiased randomness by Knuth and Yao, and a third independently developed by Levin and Kautz that generalizes the data compression technique of arithmetic coding. For each of the above classes of extraction procedures, we will identify a level of algorithmic randomness for an input that guarantees that we attain the corresponding extraction rate in producing an output. I will aim to present this material in a way that is accessible to logicians who are not specialists in computability theory / algorithmic randomness.

**May 21:****Speaker:**Moshe Y. Vardi (Rice)**Title:**The Automated-Reasoning Revolution: From Theory to Practice and Back**Abstract:**For the past 40 years computer scientists generally believed that NP-complete problems are intractable. In particular, Boolean satisfiability (SAT), as a paradigmatic automated-reasoning problem, has been considered to be intractable. Over the past 20 years, however, there has been a quiet, but dramatic, revolution, and very large SAT instances are now being solved routinely as part of software and hardware design. In this talk I will review this amazing development and show how automated reasoning is now an industrial reality.I will then describe how we can leverage SAT solving to accomplish other automated-reasoning tasks. Sampling uniformly at random satisfying truth assignments of a given Boolean formula or counting the number of such assignments are both fundamental computational problems in computer science with applications in software testing, software synthesis, machine learning, personalized learning, and more. While the theory of these problems has been thoroughly investigated since the 1980s, approximation algorithms developed by theoreticians do not scale up to industrial-sized instances. Algorithms used by the industry offer better scalability, but give up certain correctness guarantees to achieve scalability. We describe a novel approach, based on universal hashing and Satisfiability Modulo Theory, that scales to formulas with hundreds of thousands of variables without giving up correctness guarantees.

**May 28:****Speaker:**Wesley Holliday (UC Berkeley)**Title:**Extensions of choice-free Stone duality**Abstract:**In a recent paper, "Choice-free Stone duality" (JSL, March 2020), Nick Bezhanishvili and I developed a choice-free duality theory for Boolean algebras using special spectral spaces, called upper Vietoris spaces (UV-spaces). In this talk, I will cover the basics of this duality and discuss some connections to other areas of logic.

**June 4:****Speaker:**William Brian (UNC Charlotte)**Title:**Limited-information strategies in Banach-Mazur games**Abstract:**The Banach-Mazur game is an infinite-length game played on a topological space X, in which two players take turns choosing members of an infinite decreasing sequence of open sets, the first player trying to ensure that the intersection of this sequence is empty, and the second that it is not. A limited-information strategy for one of the players is a game plan that, on any given move, depends on only a small part of the game's history. In this talk we will discuss Telgársky's conjecture, which asserts roughly that there must be topological spaces where winning strategies for the Banach Mazur game cannot be too limited, but must rely on large parts of the game's history in a significant way. Recently, it was shown that this conjecture fails in models of set theory satisfying GCH + □. In such models it is always possible for one player to code all information concerning a game's history into a small piece of it. We will discuss these so-called coding strategies, why assuming GCH + □ makes them work so well, and what can go wrong in other models of set theory.

**June 11:****Speaker:**Samaria Montenegro Guzmán (U Costa Rica)**Title:**Model Theory of Pseudo Real Closed Fields**Abstract:**The notion of PAC field has been generalized by S. Basarab and by A. Prestel to ordered fields. Prestel calls a field M pseudo real closed (PRC) if M is existentially closed in every regular extension L to which all orderings of M extend. Thus PRC fields are to real closed fields what PAC fields are to algebraically closed fields.In this talk we will study the class of pseudo real closed fields (PRC-fields) from a model theoretical point of view and we will explain some of the main results obtained. We know that the complete theory of a bounded PRC field (i.e., with finitely many algebraic extensions of degree m, for each m > 1) is NTP_2 and we have a good description of forking.

Also, in a joint work with Alf Onshuus and Pierre Simon we describe the definable groups in the case that they have f-generics types.

In the end of the talk we will explain some results obtained with Silvain Rideau. Where we generalize the notion of PRC fields to a more general class of fields. In particular, this class includes fields that have orders and valuations at the same time.

**June 18:****Speaker:**Elaine Pimentel (DMAT/UFRN)**Title:**A Game Model for Proofs with Costs**Abstract:**We look at substructural calculi from a game semantic point of view, guided by certain intuitions about resource conscious and, more specifically, cost conscious reasoning. To this aim, we start with a game, where player I defends a claim corresponding to a (single-conclusion) sequent, while player II tries to refute that claim. Branching rules for additive connectives are modeled by choices of II, while branching for multiplicative connectives leads to splitting the game into parallel subgames, all of which have to be won by player I to succeed. The game comes into full swing by adding cost labels to assumptions, and a corresponding budget. Different proofs of the same end-sequent are interpreted as more or less expensive strategies for \I to defend the corresponding claim. This leads to a new kind of labelled calculus, which can be seen as a fragment of SELL (subexponential linear logic). Finally, we generalize the concept of costs in proofs by using a semiring structure, illustrate our interpretation by examples and investigate some proof-theoretical properties. This is a joint work with Timo Lang, Carlos Olarte and Christian G. Fermüller.

**June 25:****Speaker:**Rodrigo Torres-Avilés (U Bio Bio)**Title:**Topological Mixing and Linear Recurrence on SMART**Abstract:**The goal of this talk is to analize recent work on properties of the subshift derivated of a particular Turing machine, nicknamed SMART, which has a lot of interesting properties (as topological minimality and aperiodicity). First, we review a combinatorial proof of the Topological Mixing property of the subshift derivated from SMART, and later, we deepen to tie general subshift of Turing Machines with more general properties, as linear recurrence.

**July 2:****Speaker:**Ruiyuan Chen (U Illinois at Urbana-Champaign)**Title:**Stone duality and strong conceptual completeness for infinitary logic**Abstract:**The classical Stone duality, applied to the Lindenbaum-Tarski algebra of a propositional theory, allows the syntax of the theory to be canonically recovered from its space of models; this encompasses both the completeness and definability theorems for propositional logic. Many known variants and generalizations of Stone duality have analogous interpretations as completeness-definability theorems for various fragments of finitary propositional and first-order logic. In this talk, I will give an overview of this duality-theoretic approach to completeness, including the key examples of Stone duality as well as Makkai duality for first-order logic. I will then present a duality theorem for the countably infinitary first-order logic $L_{\omega_1\omega}$, proved using tools from invariant descriptive set theory as well as topos theory.

**July 9:****Speaker:**Henry Towsner (U of Pennsylvania)**Title:**Should we believe in nonstandard analysis?**Abstract:**Nonstandard analysis has been the one of the focal points for debate about the role of the axiom of choice in mathematics. I'll argue that this discussion often conflates two distinct issues - the question of whether mathematical arguments are valid, and the question of whether all mathematical objects should be understood to "exist" in the same way. I'll discuss various ways of showing that most uses of nonstandard analysis in mathematics don't actually use the axiom of choice, and how this perspective can be used to obtain new mathematical results (including applications, joint with William Simmons, to finding new bounds for primality testing in polynomial rings). On the other hand, I'll argue (based on joint work with Kenny Easwaran) that the same perspective argues against interpreting nonstandard values too literally when considering applications with real-world interpretations.

**July 16:****Speaker:**Linda Brown Westrick (Penn State)**Title:**Borel combinatorics fail in HYP**Abstract:**We show that the Borel Dual Ramsey Theorem fails in HYP, regardless of the number of partitions k ≥ 2. Therefore, the Borel Dual Ramsey Theorem is not a statement of hyperarithmetic analysis. We also apply similar methods, namely construction of completely determined pseudo-Borel codes via decorating trees, to obtain results concerning some theorems about Borel graph coloring and the prisoner hat problem. Joint work with Henry Towsner and Rose Weisshaar.

**July 23:****Speaker:**Dana Bartošová (U of Florida)**Title:**Dynamics of finite products of groups and of group extensions**Abstract:**We will investigate how universal minimal flows interact with group operations. We show that the universal minimal flow of the product of two copies of integers is far from the product of two copies of the universal minimal flow of integers. On the other hand, when a topological group is a group extension of a compact group by a discrete group, then the universal minimal flow can be computed from the discrete and compact parts.

**July 30:****Speaker:**Manuela Busaniche (CCT CONICET Santa Fe)**Title:**Residuated Lattices: algebraic constructions related to substructural logics**Abstract:**Substructural logics are logics that, when they are formulated in a Gentzen style system, they lack some of the structural rules: contraction, weakening or exchange.The importance of the theory of substructural logics relies on the fact that they provide a common framework where different logical systems can be compared. They include intuitionistic logic, fuzzy logics, relevance logics, linear logic, many-valued logics and others.Their algebraic semantics are based on residuated lattices. The class of these ordered algebraic structures is quite big and hard to study, but it contains some proper subclasses that are well-known such as Boolean algebras, Heyting algebras, MV-algebras. In this talk we will see different constructions of new residuated lattices based on better-known algebras.

**August 6:****Speaker:**James Worrell (U of Oxford)**Title:**Decision problems in program analysis**Abstract:**We consider decision problems for affine programs: a simple model from the field of program analysis. In this talk we focus on deciding the existence of algebraic and semi-algebraic invariants that separate reachable from non-reachable program states, and on deciding termination. We will survey some recently obtained decision procedures for these problems, and highlight some longstanding open questions.

**August 13:****Speaker:**James Hanson (U of Wisconsin)**Title:**Strongly Minimal Sets in Continuous Logic**Abstract:**Continuous logic is a generalization of first-order logic suited to studying structures with a real-valued metric. There is a natural generalization of the notion of strongly minimal sets to continuous logic, and, while they do not play quite the same role in characterizing theories categorical in uncountable cardinalities, they are interesting in their own right. After developing some of the basic machinery of strongly minimal sets in continuous logic, we will characterize the essentially continuous strongly minimal theories, i.e. those which do not interpret an infinite discrete structure, and we will leverage this into a precise characterization of the essentially continuous strongly minimal groups.

**August 20:****Speaker:**Damir Dzhafarov (U Conn)**Title:**Milliken's tree theorem and computability theory**Abstract:**Milliken's tree theorem is a powerful combinatorial result that generalized Ramsey's theorem and many other familiar partition results. I will present recent work on the effective and proof-theoretic strength of this theorem, which was originally motivated by a question of Dobrinen. The main result is a complete characterization of Milliken's tree theorem in terms of reverse mathematics and the usual computability-theoretic hierarchies, along with several applications to other combinatorial problems. Key to this is a new inductive proof of Milliken's tree theorem, employing an effective version of the Halpern-Lauchli theorem. This is joint work with Angles d'Auriac, Cholak, Monin, and Patey.

**August 27:****Speaker:**Dima Sinapova (University of Illinois, Chicago)**Title:**Iteration, reflection, and Prikry forcing**Abstract:**There is an inherent tension between stationary reflection and the failure of the singular cardinal hypothesis (SCH). The former is a compactness type principle that follows from large cardinals. Compactness is the phenomenon where if a certain property holds for every smaller substructure of an object, then it holds for the entire object. In contrast, failure of SCH is an instance of incompactness. It is usually obtained using Prikry forcing. We describe a Prikry style iteration, and use it to force stationary reflection in the presence of not SCH. Then we discuss the situation at smaller cardinals. This is joint work with Alejandro Poveda and Assaf Rinot.

**September 3:****Speaker:**Carl Mummert (Marshall University)**Title:**The strength of König's edge coloring theorem**Abstract:**König's edge coloring theorem says that a bipartite graph with maximal degree n has an edge coloring with no more than n colors. We study the computability theory and Reverse Mathematics of this theorem. Computable bipartite graphs with degree bounded by n have computable edge colorings with 2n-1 colors, but the theorem that there is an edge coloring with n colors is equivalent to WKL_{0}over RCA_{0}. The number of colors permitted affects the computability of the solution. We obtain an additional proof of the following theorem of Paul Shafer: WKL_{0}is equivalent over RCA_{0}to the principle that a countable bipartite n-regular graph is the union of n complete matchings.

**September 10:****Speaker:**Mirna Džamonja (IHPST, CNRS-Université Panthéon-Sorbonne Paris, France)**Title:**On logics that make a bridge from the Discrete to the Continuous**Abstract:**We study logics which model the passage between an infinite sequence of finite models to an uncountable limiting object, such as is the case in the context of graphons. Of particular interest is the connection between the countable and the uncountable object that one obtains as the union versus the combinatorial limit of the same sequence.

**September 17:****Speaker:**Alexander Berenstein (U de los Andes)**Title:**Expansions of geometric theories as measurable structures**Abstract:**We say that a theory T is geometric if for any model $M\models T$ the algebraic closure satisfies the exchange property and T eliminates the quantifier $\exists^{\infty}$. We will explain how to define, inside a geometric theory, a well behaved notion of dimension for definable sets. We will then consider the special case where the underlying theory is measurable (in the sense of Macpherson and Steinhorn) of SU-rk one, where besides a dimension we can also assign a measure to definable sets. We will then introduce an expansion called an H-structures and show that it can be studied as a generalized measurable structure whose dimension has values in $\omega^2$. This is joint work with GarcÃa and Zou.

**September 24:****Speaker:**Arno Pauly (Swansea University)**Title:**How computability-theoretic degree structures and topological spaces are related**Abstract:**We can generalize Turing reducibility to points in a large class of topological spaces. The point degree spectrum of a space is the collection of the degrees of its points. This is always a collection of Medvedev degrees, and it turns out that topological properties of the space are closely related to what degrees occur in it. For example, a Polish space has only Turing degrees iff it is countably dimensional. This connection can be used to bring topological techniques to bear on problems from computability theory and vice versa. The talk is based on joint work with Takayuki Kihara and Keng Meng Ng (https://arxiv.org/abs/1405.6866 and https://arxiv.org/abs/1904.04107).

**October 1:****Speaker:**Victoria Noquez (Indiana University)**Title:**The Sierpinski Carpet as a Final Coalgebra Obtained by Completing an Initial Algebra**Abstract:**The background for this work includes Freyd's Theorem, in which the unit interval is viewed as a final coalgebra of a certain endofunctor in the category of bipointed sets. Leinster generalized this to a broad class of self-similar spaces in categories of sets, also characterizing them as topological spaces. Bhattacharya, Moss, Ratnayake, and Rose went in a different direction, working in categories of metric spaces, obtaining the unit interval and the Sierpinski Gasket as a final colagebras in the categories of bipointed and tripointed metric spaces respectively. To achieve this they used a Cauchy completion of an initial algebra to obtain the required final coalgebra. In their examples, the iterations of the fractals can be viewed as gluing together a finite number of scaled copies of some set at some finite set of points (e.g. corners of triangles). Here we will expand these ideas to apply to a broader class of fractals, in which copies of some set are glued along segments (e.g. sides of a square). We use the method of completing an initial algebra to obtain the Sierpinski Carpet as a final coalgebra in a category of metric spaces, and note the required adaptations to this approach, most notably that we no longer get the initial algebra as the colimit of a countable sequence of metric spaces. We will explore some ways in which these results may be further generalized to a broader class of fractals. Joint work with Larry Moss.

**October 8:****Speaker:**Artem Chernikov (UCLA)**Title:**Idempotent Keisler measures**Abstract:**In model theory, a type is an ultrafilter on the Boolean algebra of definable sets, and is the same thing as a finitely additive {0,1}-valued measure. This is a special kind of a Keisler measure, which is just a finitely additive real-valued probability measure on the Boolean algebra of definable sets. If the structure we are considering expands a group (i.e. the group operations are definable), it often lifts to a natural semigroup operation on the space of its types/measures, and it makes sense to talk about the idempotent ones among them. For instance, idempotent ultrafilters on the integers provide an elegant proof of Hindman's theorem, and fit into this setting taking the structure to be (Z,+) with all of its subsets named by predicates. On the other hand, in the context of locally compact abelian groups, classical work by Wendel, Rudin, Cohen (before inventing forcing) and others classifies idempotent Borel measures, showing that they are precisely the Haar measures of compact subgroups. I will discuss recent joint work with Kyle Gannon aiming to unify these two settings, leading in particular to a classification of idempotent Keisler measures in stable theories.

**October 15:****October 22:****Speaker:**Steffen Lempp (U of Wisconsin)**Title:**The Turing Degrees: On the Order Dimension of and Embeddings into the Turing Degrees**Abstract:**In joint work with Higuchi, Raghavan and Stephan, we show that the order dimension of any locally countable partial ordering (P, <) of size k+, for any k of uncountable cofinality, is at most k. In particular, this implies that it is consistent with ZFC that the dimension of the Turing degrees under partial ordering can be strictly less than the continuum. (Kumar and Raghavan have since shown that it can also be continuum, thus the order dimension of the Turing degrees is independent of ZFC.) This is closely related to an old question of Sacks from 1963 about whether the Turing degrees form a universal locally countable partial order of size continuum.

**October 29:****Speaker:**Adam Přenosil (Vanderbilt University)**Title:**Semisimplicity, Glivenko theorems, and the excluded middle**Abstract:**There are at least three different ways to obtain classical propositional logic from intuitionistic propositional logic. Firstly, it is the extension of intuitionistic logic by the law of the excluded middle (LEM). Secondly, it is related to intuitionistic logic by the double-negation translation of Glivenko. Finally, the algebraic models of classical logic are precisely the semisimple algebraic models of intuitionistic logic (i.e. Boolean algebras are precisely the semisimple Heyting algebras). We show how to formulate the equivalence between the LEM and semisimplicity, and between what we might call the Glivenko companion and the semisimple companion of a logic, at an appropriate level of generality. This equivalence will subsume several existing Glivenko-like theorems, as well as some new ones. It also provides a useful technique for describing the semisimple subvarieties of a given variety of algebras. This is joint work with Tomáš Lávička, building on previous work by James Raftery.

**November 5:****Speaker:**Farzaneh Derakhshan (Carnegie Mellon)**Title:**Strong Progress for Session-Typed Processes in a Linear Metalogic with Circular Proofs**Abstract:**Session types describe the communication behavior of interacting processes. Binary session types are a particular form of session types in which each channel has two endpoints. The strong progress property states that a recursive process either terminates or communicates along one of its external channels after a finite number of steps. In this talk, I show how to prove strong progress for valid session-typed processes defined in an asynchronous computational semantics, working in a fragment of binary session types in which a process can use at most one resource. We formalize a proof of strong progress via a processes-as-formulas interpretation into a metalogic that we have introduced. The metalogic is an infinitary first order linear calculus with least and greatest fixed-points. We build a circular derivation for the strong progress property of processes in this first order calculus. By enforcing a condition on the logical derivations, we ensure their cut elimination property and soundness of the strong progress theorem.

**November 12:****Speaker:**Lynn Scow (Cal State San Bernardino)**Title:**Transfer of the Ramsey property**Abstract:**Ramsey's theorem for finite sequences is a special case of a class of finite structures having the Ramsey property, where that class is the age of $(\mathbb{Q},<)$. Given two classes $\mathcal{K}_1$ and $\mathcal{K}_2$, each with the Ramsey property, there are many lenses through which one might examine how the Ramsey property transfers from $\mathcal{K}_1$ to $\mathcal{K}_2$. We will present some approaches.

**November 19:****Speaker:**Anush Tserunyan (McGill University)**Title:**Containers made easy**Abstract:**A modern trend in extremal combinatorics is extending classical results from the dense setting (e.g. Szemerédi's theorem) to the sparse random setting. More precisely, one shows that a property of a given ``dense'' structure is inherited by a randomly chosen ``sparse'' substructure. A recent breakthrough tool for proving such statements is the Balogh--Morris--Samotij and Saxton--Thomason hypergraph containers method, which bounds the number of independent sets in homogeneously dense finite hypergraphs, thus implying that a random sparse subset is not independent. In a joint work with A. Bernshteyn, M. Delcourt, and H. Towsner, we give a new --- elementary and nonalgorithmic --- proof of the containers theorem for finite hypergraphs. Our proof is inspired by considering hyperfinite hypergraphs in the setting of nonstandard analysis, where there is a notion of dimension capturing the logarithmic rate of growth of finite sets. Applying this intuition in another setting with a notion of dimension, namely, algebraically closed fields, A. Bernshteyn, M. Delcourt, and I prove an analogous theorem for ``dense'' algebraically definable hypergraphs: any Zariski-generic low-dimensional subset of such hypergraphs is itself ``dense'' (in particular, not independent).

**November 26:**No seminar; public holiday in USA for Thanksgiving**December 3:****Speaker:**Johanna Franklin (Hofstra University)**Title:**Limiting densities and finitely presented structures**Abstract:**We address the question of typicality for structures by studying the limiting densities of various properties. We define the limiting density of a property Q to be the limit of the fraction of presentations of a variety with relators of length at most s that have property Q as s goes to infinity. After providing some initial examples, we present a more general approach to our question. This work is joint with Meng-Che "Turbo" Ho and Julia Knight.

**December 10:****Speaker:**Gil Sagi (U of Haifa)**Title:**Formalization, Commitments and Constraints**Abstract:**The topic of this talk is formalization: the assignment of formal language arguments to natural language arguments for the sake of evaluating the latter's validity. It has been recognized in the literature that formalization is far from a trivial process. One must discern the logical from the nonlogical in the sentence, a process that requires theorizing that goes beyond the mere understanding of the sentence formalized (Brun 2014). Moreover, according to some, formalization is a form of explication, and it "involves creative and normative aspects of constructing logical forms" (ibid).In previous work, I proposed a model-theoretic framework of "semantic constraints," where there is no strict distinction between logical and nonlogical vocabulary. The form of sentences in a formal language is determined rather by a set of constraints on models. In the talk, I will show how this framework can also be used in the process of formalization, where the semantic constraints are conceived of as commitments made with respect to the language. I will extend the framework to include "formalization constraints" on functions taking arguments from a source language to a target language, and I will consider various meta-constraints on both the process of formalization and its end result.

**December 17:**No seminar**December 24:**No seminar: Christmas Eve Holiday**December 31:**No seminar

**January 7:**No seminar; ASL Winter / Joint Mathematics Meetings**January 14 (UNESCO World Logic Day):****Speaker:**Aleksandra Kwiatkowska (U of Wrocław)**Title:**Simplicity of the automorphism groups of countable homogeneous structures**Abstract:**The program of understanding the normal subgroup structure of groups that arise as automorphism groups of countable structures dates back at least to the '50s, when Higman described all proper normal subgroups of the automorphism group of rationals (Q,<). In recent several years Tent-Ziegler, following the work of Macpherson-Tent, proved simplicity for many automorphism groups of countable graphs and metric spaces. In the talk, we prove simplicity for the automorphism groups of order and tournament expansions of homogeneous structures such as the bounded Urysohn metric space and the random graph. In particular, we show that the automorphism group of the linearly ordered random graph is a simple group. This is joint work with Filippo Calderoni and Katrin Tent.

**January 21:****Speaker:**Angeliki Koutsoukou-Argyraki (U of Cambridge)**Title:**Aristotle's Assertoric Syllogistic in Isabelle/HOL**Abstract:**I discuss my formalisation of some basic elements of Aristotle's assertoric syllogistic using the proof assistant (interactive theorem prover) Isabelle/HOL. The formal proof development can be found on the Archive of Formal Proofs

**January 28:****Speaker:**Raimundo Briceño (Pontificia Universidad Católica de Chile)**Title:**Dismantlability, connectedness, and mixing in relational structures**Abstract:**The Constraint Satisfaction Problem (CSP) and its counting counterpart appears under different guises in many areas of mathematics, computer science, and elsewhere. Its structural and algorithmic properties have demonstrated to play a crucial role in many of those applications. For instance, in the decision CSPs, structural properties of the relational structures involved --- like, for example, dismantlability --- and their logical characterizations have been instrumental for determining the complexity and other properties of the problem. Topological properties of the solution set such as connectedness are related to the hardness of CSPs over random structures. Additionally, in approximate counting and statistical physics, where CSPs emerge in the form of spin systems, mixing properties and the uniqueness of Gibbs measures have been heavily exploited for approximating partition functions and free energy.In spite of the great diversity of those features, there are some eerie similarities between them. These were observed and made more precise in the case of graph homomorphisms by Brightwell and Winkler, who showed that dismantlability of the target graph, connectedness of the set of homomorphisms, and good mixing properties of the corresponding spin system are all equivalent. In this talk we go a step further and demonstrate similar connections for arbitrary CSPs. This requires a much deeper understanding of dismantling and the structure of the solution space in the case of relational structures, and also new refined concepts of mixing. In addition, we develop properties related to the study of valid extensions of a given partially defined homomorphism, an approach that turns out to be novel even in the graph case. We also add to the mix the combinatorial property of finite duality and its logic counterpart, FO-definability, studied by Larose, Loten, and Tardif. This is joint work with Andrei Bulatov, Víctor Dalmau, and Benoît Larose.

**February 4:****Speaker:**Peter Cholak (Notre Dame)**Title:**Old and new results on the computably enumerable sets**Abstract:**We will survey a number of old results on the computably enumerable sets and finish with a few new results. The computably enumerable sets are interesting since anything which can happen computably happens in computably enumerable sets.

**February 11:****Speaker:**Ludovic Patey (Institut Camille Jordan, Lyon)**Title:**Canonical notions of forcing in computability theory**Abstract:**In reverse mathematics, a proof that a problem P does not imply a problem Q is usually done by constructing a computable instance of Q whose solutions are computationally complex, while proving that every simple instance of P has a simple solution, using a notion of forcing. In its full generality, the notion of forcing could depend on both P and Q, but in most cases, the notion of forcing for building solutions to P does not depend on Q. This suggests the existence of a "canonical" notion of forcing for P, that is, a notion of forcing such that all the relevant separation proofs can be obtained without loss of generality with sufficiently generic sets for this notion. We settle a formal framework for discussing this question, and give preliminary results. This is a joint work with Denis Hirschfeldt.

**February 18:****Speaker:**Marcos Mazari-Armida (Carnegie Mellon University)**Title:**Characterizing noetherian rings via superstability**Abstract:**We will show how superstability of certain classes of modules can be used to characterize noetherian rings. None of the classes of modules that we will consider are axiomatizable by a complete first-order theory and some of them are not even first-order axiomatizable, but they are all Abstract Elementary Classes (AECs). This new way of looking at classes of modules as AECs will be emphasized as I think it can have interesting applications. If time permits we will see how the ideas presented can be used to characterize other classical rings such as pure-semisimple rings and perfect rings.

**February 25:****Speaker:**Sophia Knight (University of Minnesota, Duluth)**Title:**Reasoning about agents who may know other agents' strategies in Strategy Logic**Abstract:**In this talk I will discuss some new developments in Strategy Logic with imperfect information. Strategy Logic is concerned with agents' strategic abilities in multi-agent systems, and unlike ATL, treats strategies as first-class objects in the logic, independent from the agents. Thus, in imperfect information settings, Strategy Logic raises delicate issues, such as what agents know about one another's strategies. I will describe a new version of Strategy Logic that ensures that agents' strategies are uniform, and allows a formal description of their knowledge about each other's strategies.

**March 4:****Speaker:**Dakota Ihli (University of Illinois Urbana-Champaign)**Title:**What generic automorphisms of the random poset look like**Abstract:**The random poset (the Fraïssé limit of the class of finite posets) admits generic automorphisms --- that is, its automorphism group admits a comeagre conjugacy class. This result, due to D. Kuske and J. Truss, was proven without explicitly describing the automorphisms in question. Here we give a new, concrete description of the generic automorphisms, and we discuss the combinatorics and model theory involved.

**March 11:****Speaker:**Matthew Moore (University of Kansas)**Title:**The Hidden Subgroup Problem for Universal Algebras**Abstract:**The Hidden Subgroup Problem (HSP) is a computational problem which includes as special cases integer factorization, the discrete logarithm problem, graph isomorphism, and the shortest vector problem. The celebrated polynomial-time quantum algorithms for factorization and the discrete logarithm are restricted versions of a generic polynomial-time quantum solution to the HSP for*abelian*groups, but despite focused research no polynomial-time solution for general groups has yet been found. We propose a generalization of the HSP to include*arbitrary*algebraic structures and analyze this new problem on powers of 2-element algebras. We prove a complete classification of every such power as quantum tractable (i.e. polynomial-time), classically tractable, quantum intractable, or classically intractable. In particular, we identify a class of algebras for which the generalized HSP exhibits super-polynomial speedup on a quantum computer compared to a classical one.

**March 18:**No Seminar**March 25:****Speaker:**Michael Lieberman (Brno University of Technology)**Title:**Recent developments in categorical model theory**Abstract:**We give an overview of the foundations of the still-emerging field of categorical model theory, which synthesizes ideas and methods drawn from accessible categories, abstract model theory, and set theory. We discuss the fundamental nexus of interaction---a very slight generalization of abstract elementary classes (AECs)---and sketch a few recent results. In particular, we consider:- Connections between compact cardinals, tameness of Galois types, and the closure of images of accessible functors (joint work with Will Boney).
- Stable independence on an abstract category, with surprising connections to homotopy theory (joint work with Jiří Rosický and Sebastien Vasey).

**April 1:****Speaker:**Deirdre Haskell (McMaster University)**Title:**Tameness properties of theories of valued fields with analytic functions**Abstract:**An important motif in model-theoretic algebra over the last thirty years has been the concept of tameness and the impact it has for understanding the definable sets of a structure. In this talk, I will describe some of the ways this motif occurs in the case of valued fields, especially ordered convexly valued fields, when equipped with additional function symbols which, on the standard model, are interpreted by functions defined by convergent power series. All of these notions will be defined in the course of the talk.

**April 8:**No Seminar**April 15:**- Sarah Reitzes (University of Chicago)
**Title:**Reduction games over RCA_{0}**Abstract:**In this talk, I will discuss joint work with Damir D. Dzhafarov and Denis R. Hirschfeldt. Our work centers on the characterization of problems P and Q such that P $\leq_{\omega}$ Q, as well as problems P and Q such that $\textup{RCA}_0 \vdash$ Q $\to$ P, in terms of winning strategies in certain games. These characterizations were originally introduced by Hirschfeldt and Jockusch. I will discuss extensions and generalizations of these characterizations, including a certain notion of compactness that allows us, for strategies satisfying particular conditions, to bound the number of moves it takes to win. This bound is independent of the instance of the problem P being considered. This allows us to develop the idea of Weihrauch and generalized Weihrauch reduction over some base theory. Here, we will focus on the base theory $\textup{RCA}_0$. In this talk, I will explore these notions of reduction among various principles, focusing particularly on bounding and induction principles.

**April 22:****Speaker:**Sylvy Anscombe (Université de Paris)**Title:**Some existential theories of fields**Abstract:**Building on previous work, I will discuss Turing reductions between various fragments of theories of fields. In particular, we exhibit several theories of fields Turing equivalent to the existential theory of the rational numbers. This is joint work with Arno Fehm.

**April 29:****Speaker:**Mariana Vicaria (Berkeley)**Title:**Elimination of imaginaries and stable domination in multivalued fields**Abstract:**The model theory of henselian valued fields has been a major topic of study during the last century. Remarkable work has been achieved by Haskell, Hrushovski and Macpherson to understand the model theory of algebraically closed valued fields (ACVF). In a sequence of seminal papers they proved that this theory eliminates imaginaries once the geometric sorts are added and they developed the notion of stable domination, which describes how types over maximally complete bases are controlled by the stable part of the structure.I will explain how to extend these results to the broader class of henselian valued fields of equicharacteristic zero, residue field algebraically closed and poly- regular value group. This includes many interesting mathematical structures such as the Laurent Series over the Complex numbers, but more importantly extends the results to valued fields with finitely many definable convex subgroups.

**May 6:****Speaker:**Valentina Harizanov (George Washington University)**Title:**Computability theory and automorphisms of lattices of substructures**Abstract**We use computability-theoretic concepts and methods to study automorphisms of lattices of substructures of a canonical computable infinite-dimensional vector space over the rationals. In particular, we establish the equivalence of the embedding relation for certain automorphism groups with the order relation of the corresponding Turing degrees. We further determine the Turing degrees of these automorphism groups. We establish similar results for the interval Boolean algebra over the rationals. This is joint work with Rumen Dimitrov and Andrei Morozov.

**May 13:****Speaker:**Andrés Villaveces (Universidad Nacional de Colombia)**Title:**A partition relation for well-founded trees by Komjáth and Shelah, and two applications to model theory**Abstract:**In 2003, Komjáth and Shelah proved a partition theorem on scattered order types; these in turn could be understood as partition relations for classes of well-founded trees. Recently, two different kinds of applications of the same partition relation have been used in infinitary logic and in model theory: one by Väänänen and Velickovic on games related to Shelah's logic L^{1}_{κ}, another by Shelah and myself on the "canonical tree" of an AEC (a generalization of the Scott sentence for an abstract elementary class). I will describe the Komjáth-Shelah result in the first part and then narrow in the applications (with more details on the second one, from some recent joint work with Shelah). Time permitting, I will also address a third interaction between partition relations and model theoretic issues.

**May 20:****Speaker:**Andrew Moorhead (University of Kansas)**Title:**Higher commutators, hypercubes, and the hierarchy of centralizer conditions**Abstract:**The commutator had historically been studied for specific varieties of algebras until Smith found a general definition for a commutator that worked for any Mal'cev algebra. Since then the commutator has become an essential part of the general algebraist's toolkit. Bulatov discovered at the beginning of the century that the (binary) commutator can be extended to an infinite sequence of higher arity operations, no one of which are term definable from the others. This discovery has most importantly led to the distinction between a nilpotent algebra and a 'supernilpotent' algebra. While this distinction is invisible for groups, supernilpotent Mal'cev algebras share many strong properties with nilpotent groups, while nilpotent algebras need not. We will discuss the extent to which some of the known results of commutator theory can be viewed as a low-dimensional case of a general multidimensional theory.

**May 27:****Speaker:**Alexi Block Gorman (U of Illinois Urbana-Champaign)**Title:**Definability on the Reals from Büchi Automata**Abstract:**Büchi automata are the natural analogue of finite automata in the context of infinite strings (indexed by the natural numbers) on a finite alphabet. We say a subset X of the reals is r-regular if there is a Büchi automaton that accepts (one of) the base-r representations of every element in X, and rejects the base-r representations of each element in its complement. These sets often exhibit fractal-like behavior --- e.g., the Cantor set is 3-regular. There are remarkable connections in logic to Büchi automata, particularly in model theory. In this talk, I will give a characterization of when the expansion of the real ordered additive group by a predicate for a closed r-regular subset of [0,1] is model-theoretically tame (d-minimal, NIP, NTP2). Moreover, I will discuss how this coincides with geometric tameness, namely trivial fractal dimension. This will include a discussion of how the properties of definable sets vary depending on the properties of the Büchi automaton that recognizes the predicate subset.

**June 3:****Speaker:**Tarek Sayed-Ahmed (Cairo University)**Title:**Atom canonicity, complete representations, and omitting types**Abstract:**Click here for abstract

**June 10:****Speaker:**Rachael Alvir (U of Notre Dame}**Title:**Scott Complexity and Finitely α-generated Structures**Abstract:**In this talk, we define the notion of a finitely α-generated structure and generalize results about Scott sentences earlier known only for finitely generated structures. We will show how these results can be used to the connect some of the existing non-equivalent definitions of Scott rank.

**June 17:****Speaker:**Christina Brech (Universidade de São Paulo)**Title:**Isomorphic combinatorial families**Abstract:**We will recall the notion of compact and hereditary families of finite subsets of some cardinal κ and their corresponding combinatorial Banach spaces. We present a combinatorial version of Banach-Stone theorem, which leads naturally to a notion of isomorphism between families. Our main result shows that different families on ω are not isomorphic, if we assume them to be spreading. We also discuss the difference between the countable and the uncountable setting. This is a joint work with Claribet Piña.

**June 24:**No Seminar: ASL North American meeting**July 1:****Speaker:**Daoud Siniora (American University in Cairo)**Title:**Generic automorphisms of homogeneous structures**Abstract:**Automorphism groups of countable first-order structures are Polish groups under the pointwise convergence topology. An automorphism is called generic if its conjugacy class in comeagre. In this talk we focus on generic automorphisms of homogeneous structures, such structures arise as Fraisse limits of amalgamation classes of finite structures. We will present joint work with Itay Kaplan and Tomasz Rzepecki studying generic automorphisms of the countable universal homogeneous meet-tree.

**July 8:****Speaker:**Dimitra Chompitaki (U of Crete)**Title:**Decidability results of subtheories of commonly used domains in Algebra and Number Theory**Abstract:**We will present some known decidability and undecidability results for theories of the ring-structures of commonly used domains (Polynomial Rings, Rational Functions, Formal Power Series). Then we will focus on ongoing research relating to some subtheories such as: (a) Addition and the Frobenius map for subrings of Rational Functions of positive characteristic, and (b) Addition and Divisibility for Formal Power Series. The latter results fall mostly on the "decidability" side: model completeness and elimination of quantifiers.

**July 15:****Speaker:**Cristobal Rojas (Pontificia Universidad Católica de Chile)**Title:**Computability of Harmonic Measure**Abstract:**We will review recent results relating the geometry of a connected domain to the computability of its harmonic measure at a given point x. In particular, we will discuss examples of domains whose harmonic measure at x is always computable relative to x, but not uniformly. This construction gives rise to examples of continuous functions arising as solutions to a Dirichlet problem (so they are even harmonic) which are piecewise computable (i.e. all their values are computable relative to the input point), but not computable.

**July 22:****Speaker:**Noah Schweber (Proof School)**Title:**Ceers higher up**Abstract:**We examine analogues of ceers (computably enumerable equivalence relations) in generalized recursion theory - specifically, in κ-recursion theory for κ an uncountable regular cardinal. Classically, the degrees of ceers with respect to computable embeddability forms a partial order which is maximally complicated, namely one whose theory is computably isomorphic to that of true arithmetic. We extend this result to the κ-ceers. Interestingly, this requires a genuinely new argument, and currently no single approach is known which applies both to ω and to uncountable regular κ. Moreover, the situation for singular cardinals, let alone admissible ordinals which are not cardinals such as ω^{CK}_{1}, is completely open. If time permits, we will discuss a second proof of the above result for the special case of κ=ω_{1}which has the advantage of applying to certain generalized computability theories other than κ-recursion theories. This is joint work with Uri Andrews, Steffen Lempp, and Manat Mustafa.

**July 29:****Speaker:**Hunter Spink (Stanford)**Title:**Probabilistic Littlewood-Offord anti-concentration results via model theory**Abstract:**(Joint with Jacob Fox and Matthew Kwan) The classical Erdos-Littlewood-Offord theorem says that for any n nonzero vectors in R^{d}, a random signed sum concentrates on any point with probability at most O(n^{-1/2}). Combining tools from probability theory, additive combinatorics, and model theory, we obtain an anti-concentration probability of n^{-1/2+o(1)}for any o-minimal set S in R^{d}(such as a hypersurface defined by a polynomial in x_{1},...,x_{n},e^{x1},...,e^{xn}, or a restricted analytic function) not containing a line segment. We do this by showing such o-minimal sets have no higher-order additive structure, complementing work by Pila on lower-order additive structure developed to count rational and algebraic points of bounded height.

**August 5:**No Seminar**August 12:**No Seminar**August 19:****Speaker:**Joel Nagloo (University of Illinois Chicago)**Title:**Geometric triviality in differentially closed fields**Abstract:**In this talk we revisit the problem of describing the 'finer' structure of geometrically trivial strongly minimal sets in DCF_{0}. In particular, I will explain how recent work joint with Guy Casale and James Freitag on Fuchsian groups (discrete subgroup of SL_{2}(R)) and automorphic functions, has lead to intriguing questions around the ω-categoricity conjecture of Daniel Lascar. This conjecture was disproved in its full generality by James Freitag and Tom Scanlon using the modular group SL_{2}(Z) and its automorphic uniformizer (the j-function). I will explain how their counter-example fits into the larger context of arithmetic Fuchsian groups and has allowed us to 'propose' refinements to the original conjecture.

**August 26:****Speaker:**Colin Jahel (Université Claude Bernard Lyon 1)**Title:**Some progress on the unique ergodicity problem**Abstract:**In 2005, Kechris, Pestov and Todorcevic exhibited a correspondence between combinatorial properties of structures and dynamical properties of their automorphism groups. In 2012, Angel, Kechris and Lyons used this correspondence to show the unique ergodicity of all the minimal actions of some subgroups of S_{∞}. In this talk, I will give an overview of the aforementioned results and discuss recent work generalizing results of Angel, Kechris and Lyons in several directions.

**September 2:****Speaker:**Cristina Sernadas (Universidade de Lisbona)**Title:**Decidability via Reduction in Logics and Their Combinations**Abstract:**Decision problems in logic include semantic based problems like the satisfiability and the validity problems and deductive problems like the theoremhood and the consequence problems. Satisfaction systems and reductions between them are presented as an appropriate context for analyzing the satisfiability and the validity problems. The notion of reduction is generalized in order to cope with the meet-combination of logics. Reductions between satisfaction systems induce reductions between the respective satisfiability problems and (under mild conditions) also between their validity problems. Sufficient conditions are provided for relating satisfiability problems to validity problems. Reflection results for decidability in the presence of reductions are established. The validity problem in the meet-combination is proved to be decidable whenever the validity problems for the components are decidable. Some examples are discussed, namely, the meet-combination of modal logic and intuitionistic logic. Some ongoing work related to consequence problems in the context of consequence systems and their combination is pointed out. This talk reports on joint work with João Rasga and Walter Carnielli.

**September 9:****Speaker:**Marcelo Arenas (Pontificia Universidad Católica de Chile)**Title:**Descriptive Complexity for Counting Complexity Classes**Abstract:**Descriptive Complexity has been very successful in characterizing complexity classes of decision problems in terms of the properties definable in some logics. However, descriptive complexity for counting complexity classes, such as FP and #P, has not been systematically studied, and it is not as developed as its decision counterpart. In this talk, we will present a framework based on Weighted Logics to address this issue. Specifically, by focusing on the natural numbers we obtain a logic called Quantitative Second Order Logics (QSO), and show how some of its fragments can be used to capture fundamental counting complexity classes such as FP, #P and FPSPACE, among others. Moreover, we use QSO to define a hierarchy inside #P, identifying counting complexity classes with good closure and approximation properties, and which admit natural complete problems.

**September 16:****Speaker:**Caroline Terry (Ohio State University)**Title:**Speeds of hereditary properties and mutual algebricity**Abstract:**A hereditary graph property is a class of finite graphs closed under isomorphism and induced subgraphs. Given a hereditary graph property H, the speed of H is the function which sends an integer n to the number of distinct elements in H with underlying set {1,...,n}. Not just any function can occur as the speed of hereditary graph property. Specifically, there are discrete "jumps" in the possible speeds. Study of these jumps began with work of Scheinerman and Zito in the 90's, and culminated in a series of papers from the 2000's by Balogh, Bollobás, and Weinreich, in which essentially all possible speeds of a hereditary graph property were characterized. In contrast to this, many aspects of this problem in the hypergraph setting remained unknown. In this talk we present new hypergraph analogues of many of the jumps from the graph setting, specifically those involving the polynomial, exponential, and factorial speeds. The jumps in the factorial range turned out to have surprising connections to the model theoretic notion of mutual algebricity, which we also discuss. This is joint work with Chris Laskowski.

**September 23:**No Seminar**September 30:****Speaker:**Gihanee Senadheera (Southern Illinois University)**Title:**Effective Concept Classes of PACi/PAC Incomparable Degrees and Jump Structure**Abstract:**The Probably Approximately Correct (PAC) learning is a machine learning model introduced by Leslie Valiant in 1984. The PACi reducibility refers to the PAC reducibility independent of size and computation time. This reducibility in PAC learning resembles the reducibility in Turing computability. In 1957 Friedberg and Muchnik independently solved the Post problem by constructing computably enumerable sets A and B of incomparable degrees using the priority construction method. We adapt this idea to PACi/PAC reducibilities and construct two the effective concept classes C_{0}and C_{1}such that C_{0}is not reducible to C_{1}and vice versa. When considering PAC reducibility it was necessary to work on the size of an effective concept class, thus we use Kolmogorov complexity to obtain the size. Analogous to Turing jump, we give a jump structure on effective concept classes. As the future work, we begin to explore an embedding of structures from PAC degrees to 1-1 degrees or Turing degrees.

**October 7:****Speaker:**Françoise Point (Université de Mons-Hainaut)**Title:**Definable groups in topological fields with a generic derivation**Abstract:**We study a class of tame L-theories T of topological fields and their extensions by a generic derivation δ. The topological fields under consideration include henselian valued fields of characteristic 0 and real closed fields. We axiomatize the class of the existentially closed L_{δ}-expansions. We show that T_{δ}^{*}has L-open core (i.e., every L_{δ}-definable open set is L-definable) and derive both a cell decomposition theorem and a transfer result of elimination of imaginaries. Other tame properties of T such as relative elimination of field sort quantifiers, NIP and distality also transfer to T_{δ}^{*}.Then letting K be a model of T

_{δ}^{*}and M a |K|^{+}-saturated elementary extension of K, we first associate with an L_{δ}(K)-definable group G in M, a pro-L-definable set G^{**}_{∞}in which the differential prolongations G^{∇_∞}of elements of G are dense, using the L-open core property of T_{δ}^{*}. Following the same ideas as in the group configuration theorem in o-minimal structures as developed by K. Peterzil, we construct a type L-definable topological group H_{∞}⊂ G^{**}_{∞}, acting on a K-infinitesimal neighbourhood of a generic element of G^{**}_{∞}in a faithful, continuous and transitive way. Further H_{∞}∩ G^{∇_∞}is dense in H_{∞}and the action of H_{∞}∩ G^{∇_∞}coincides with the one induced by the initial L_{δ}-group action.The first part of this work is joint with Pablo Cubidès Kovacsics.

**October 14:****Speaker:**Franziska Jahnke (University of Münster)**Title:**Decidability and definability in unramified henselian valued fields**Abstract:**Unramified and finitely ramified henselian valued fields are central to studying model-theoretic phenomena in mixed characteristic. Decidability and definability in unramified henselian valued fields with perfect residue field are well understood, starting with the seminal work of Ax, Kochen, and Ershov. In this talk, we present recent developments in unramified henselian valued fields with imperfect residue field, and also comment on what changes in the case of finite ramification. This is joint work with Sylvy Anscombe.

**October 21:****Speaker:**Gregory Cherlin (Rutgers University)**Title:**Homogeneity and generalized metric spaces**Abstract:**Generalized metric spaces of various sorts have come up in connection with the study of homogeneous structures (classification, Ramsey theoretic properties). I'll discuss examples studied by Sauer, Conant, Braunfeld, Hubička, Konečný, Nešetřil, and others. See, notably, Konečný's master's thesis (arXiv).

**October 28:****Speaker:**Alexandra Shlapentokh (East Carolina University)**Title:**A mysterious ring**Abstract:**Let ℚ^{ab}be the largest abelian extension of ℚ, or in other words the compositum of all cyclotomic extensions. Let O_{ ℚ^ab}be the ring of integers of ℚ^{ab}or the ring of elements of ℚ^{ab}satisfying monic irreducible polynomials over ℤ. It is not known whether the first-order theory of O_{ ℚ^ab}is decidable. ℚ^{ab}is also a degree two extension of a totally real field. Much more is known about the first-order theory of rings of integers of totally real fields and in some cases one is able to deduce undecidability of the first-order theory of the ring of integers of a degree 2 extension of a totally real field from an analogous result for the ring of integers of the totally real field. However this method does not seem to work for ℚ^{ab}. We discuss a possible way of resolving this problem and some related questions.

**November 4:****Speaker:**Natalia García Fritz (Pontificia Universidad Católica de Chile)**Title:**Hilbert's tenth problem for rings of exponential polynomials**Abstract:**After being negatively solved by Davis, Putnam, Robinson, and Matijasevich in 1970, Hilbert's tenth problem has been extended to a number of other rings. One of the main natural open cases is that of the ring of complex entire functions in one variable. After reviewing some literature around this problem, in this talk I will outline a negative solution of the analogue of Hilbert's tenth problem for the ring of exponential polynomials, approaching the case of entire functions. This is joint work with D. Chompitaki, H. Pasten, T. Pheidas, and X. Vidaux.

**November 11:****Speaker:**Jana Mařiková (Universität Wien)**Title:**Definable matchings in o-minimal bipartite graphs**Abstract:**This talk will revolve around the question, under what conditions an o-minimally definable bipartite graph admits a definable matching. We discuss some context, a partial result, and touch on possible applications. This is work in progress.

**November 18:****Speaker:**Sara Uckelman (Durham University)**Title:**John Eliot's*Logick Primer*: A bilingual English-Algonquian logic textbook**Abstract:**In 1672 John Eliot, English Puritan educator and missionary, published*The Logick Primer: Some Logical Notions to initiate the INDIANS in the knowledge of the Rule of Reason; and to know how to make use thereof*[1]. This roughly 80 page pamphlet focuses on introducing basic syllogistic vocabulary and reasoning so that syllogisms can be created from texts in the Psalms, the gospels, and other New Testament books. The use of logic for proselytizing purposes is not distinctive: What is distinctive about Eliot's book is that it is bilingual, written in both English and Massachusett, an Algonquian language spoken in eastern coastal and southeastern Massachusetts. It is one of the earliest bilingual logic textbooks, it is the only textbook that I know of in an indigenous American language, and it is one of the earliest printed attestations of the Massachusett language.In this talk, I will:

- Introduce John Eliot and the linguistic context he was working in. Introduce the contents of the
- Discuss notions of ``Puritan'' logic that inform this primer.
- Talk about the importance of his work in documenting and expanding the Massachusett language and the problems that accompany his colonial approach to this work.

*Logick Primer*---vocabulary, inference patterns, and applications.*The Logick Primer: Some Logical Notions to initiate the INDIANS in the knowledge of the Rule of Reason; and to know how to make use thereof*. Printed by M. J., 1672

**November 25:**No seminar: public holiday in the US for Thanksgiving**December 2:****Speaker:**Vasco Brattka (Universität der Bundeswehr München)**Title:**A Galois connection between Turing jumps and limits**Abstract:**We discuss a Galois connection between Turing jumps and limits that offers a fresh view on the class of limit computable functions and its properties. This view does not only offer simplified proofs of many known classical results in computable analysis, but also new insights. With this approach we also propagate a more uniform view on computability theory in general.

**December 9:****Speaker:**Mostafa Mirabi (Wesleyan University)**Title:**MS-Measurability via Coordinatization**Abstract:**In this talk, we first discuss the concept of MS-measurable structures, introduced by Macpherson and Steinhorn in 2007. Then we will define a strong notion of Coordinatization for ℵ_{0}-categorical structures and show that a structure which is coordinatized by ℵ_{0}-categorical MS-measurable structures itself is MS-measurable. This approach provides a way to build new MS-measurable structures.

**December 16:****Speaker:**Todor Tsankov (Institut Camille Jordan)**Title:**Continuous logic and Borel equivalence relations**Abstract:**The theory of Borel reducibility of definable equivalence relations was initiated by Friedman and Stanley who were specifically interested in the equivalence relation of isomorphism of countable structures. Since then, the scope of the theory has considerably expanded but isomorphism of countable structures remains one of the situations where the most detailed results are available and where both methods of infinitary model theory and descriptive set theory can be applied. In this talk, I will explain how infinitary continuous logic can be used to extend parts of this theory to metric structures. Our main result is about isomorphism of locally compact metric structures and it is a common generalization of theorems of Hjorth (for locally compact metric spaces) and Hjorth and Kechris (for countable structures). This is joint work with Andreas Hallbäck and Maciej Malicki.

**December 23:**No Seminar**December 30:**No Seminar**January 6:**No Seminar, due to (previously planned) ASL Winter Meeting**January 13:****Speaker:**Caleb Camrud (Iowa State University)**Title:**Continuous Logic, Diagrams, and Truth Values for Computable Presentations**Abstract:**Goldbring,McNicholl, and I investigated the arithmetic and hyperarithmetic degrees of the finitary and computable infinitary diagrams of continuous logic for computably presented metric structures. As the truth value of a sentence of continuous logic may be any real in [0,1], we introduced two kinds of diagrams at each level: the closed diagram, which encapsulates weak inequalities of truth values, and the open diagram, which encapsulates strict inequalities. We showed that, for any computably presented metric structure and any computable ordinal α, the closed and open Σ^{c}_{α}diagrams are Π^{c}_{α+1}and Σ^{c}_{α}, respectively, and that the closed and open Π^{c}_{α}diagrams are Π^{c}_{α}and Σ^{c}_{α+1}.Proving the optimality of these bounds, however, was non-trivial. Since the standard presentation of [0,1] with the Euclidean metric is computably compact, we were forced to work on the natural numbers with the discrete metric (in some sense, the "simplest" non-compact metric space). Along the way, we also proved some surprising combinatorial results. McNicholl and I then continued our study of computable infinitary continuous logic and found that for any nonzero computable ordinal α and any right Π

^{c}_{α}(or Σ^{c}_{α}) real number, there is a Π^{c}_{α}(or Σ^{c}_{α}) sentence which is universally interpreted as that value.

**January 20:****Speaker:**Daniel Turetsky (Victoria University of Wellington)**Title:**True Stages -- From Priority Arguments to Descriptive Set Theory**Abstract:**The true stages machinery was conceived as a technique for organizing complex priority constructions in computability theory, much like Ash's metatheorem. With a little modification, however, it can prove remarkably useful in descriptive set theory. Using this machinery, we can obtain nice proofs of results of Wadge, Hausdorff and Kuratowski, and Louveau, sometimes strengthening the result in the process. Without getting too deep into the details, I will give the ideas of the machinery and how it applies to descriptive set theory.

**January 27:****Speaker:**Lauren Wickman (University of Florida)**Title:**Knaster Continua and Projective Fraïssé Theory**Abstract:**The Knaster continuum, also known as the buckethandle, or the Brouwer-Janiszewski-Knaster continuum can be viewed as an inverse limit of 2-tent maps on the interval. However, there is a whole class (with continuum many non-homeomorphic members) of Knaster continua, each viewed as an inverse limit of p-tent maps, where p is a sequence of primes. In this talk, for each Knaster continuum K, we will give a projective Fraïssé class of finite objects that approximate K (up to homeomorphism) and examine the combinatorial properties of that the class (namely whether the class is Ramsey or if it has a Ramsey extension). We will give an extremely amenable subgroup of the homeomorphism group of the universal Knaster continuum.

**February 3:**No seminar**February 10:****Speaker:**Antonina Kolokolova (Memorial University of Newfoundland)**Title:**Learning from Bounded Arithmetic**Abstract:**The central question of complexity theory -- what can (and cannot) be feasibly computed -- has a corresponding logical meta-question: what can (and cannot) be feasibly proven. While complexity theory studies the former, bounded arithmetic is one of the main approaches to the meta-question. There is a tight relation between theories of bounded arithmetic and corresponding complexity classes, allowing one to study what can be proven in, for example, "polynomial-time reasoning" and what power is needed to resolve complexity questions, with a number of both positive and negative provability results.Here, we focus on the complexity of another meta-problem: learning to solve problems such as Boolean satisfiability. There is a range of ways to define "solving problems", with one extreme, the uniform setting, being an existence of a fast algorithm (potentially randomized), and another of a potentially non-computable family of small Boolean circuits, one for each problem size. The complexity of learning can be recast as the complexity of finding a procedure to generate Boolean circuits solving the problem of a given size, if it (and such a family of circuits) exists.

First, inspired by the KPT witnessing theorem, a special case of Herbrand's theorem in bounded arithmetic, we develop an intermediate notion of uniformity that we call LEARN-uniformity. While non-uniform lower bounds are notoriously difficult, we can prove several unconditional lower bounds for this weaker notion of uniformity. Then, returning to the world of bounded arithmetic and using that notion of uniformity as a tool, we show unprovability of several complexity upper bounds for both deterministic and randomized complexity classes, in particular giving simpler proofs that the theory of polynomial-time reasoning PV does not prove that all of P is computable by circuits of a specific polynomial size, and the theory V

^{1}, a second-order counterpart to the classic Buss' theory S^{1}_{2}, does not prove the same statement with NP instead of P.Finally, we leverage these ideas to show that bounded arithmetic "has trouble differentiating" between uniform and non-uniform frameworks: more specifically, we show that theories for polynomial-time and randomized polynomial-time reasoning cannot prove both a uniform lower bound and a non-uniform upper bound for NP. In particular, while it is possible that NP != P yet all of NP is computable by families of polynomial-size circuits, this cannot be proven feasibly.

**February 17:**No seminar**February 24:****Speaker:**Roman Kossak (The Graduate Center, City University of New York)**Title:**Undefinability and absolute undefinability in models of arithmetic.**Abstract:**I will survey some well-known and some more recent undefinability results about models of Peano Arithmetic. I want to contrast first-order undefinability in the standard model with a much stronger notion of undefinability which is suitable for resplendent models, and use the results to motivate some more general questions about the nature of undefinability.

**March 3:****Speaker:**Adam Case (Drake University)**Title:**Finite-State Mutual Dimension**Abstract:**In this talk, I will discuss recent work with Jack H. Lutz on a notion of finite-state mutual dimension. Intuitively, the finite-state dimension of a sequence S represents the density of finite-state information contained within S, while the finite-state mutual dimension between two sequences S and T represents the density of finite-state information shared by S and T. Thus "finite-state mutual dimension" can be viewed as a "finite-state" version of mutual dimension and as a "mutual" version of finite-state dimension. The main results that will be discussed are as follows. First, we show that finite-state mutual dimension, defined using information-lossless finite-state compressors, has all of the properties expected of a measure of mutual information. Next, we prove that finite-state mutual dimension may be characterized in terms of block mutual information rates. Finally, we provide necessary and sufficient conditions for two normal sequences to achieve finite-state mutual dimension zero.

**March 10:**No Seminar**March 17:****Speaker:**John Baldwin (University of Illinois Chicago)**Title:**Category Theory and Model Theory: Symbiotic Scaffolds**Abstract:**A*scaffold*for mathematics includes both*local*foundations for various areas of mathematics and productive guidance in how to unify them. In a scaffold the unification does not take place by a common axiomatic basis but consists of a systematic ways of connecting results and proofs in various areas of mathematics. Two scaffolds, model theory and category theory, provide local foundations for many areas of mathematic including two flavors (material and structural) of set theory and different approaches to unification. We will discuss salient features of the two scaffolds including their contrasting but bi-interpretable set theories. We focus on the contrasting treatments of `size' in each scaffold and the advantages/disadvantages of each for different problems.

**March 24:****Speaker:**Riley Thornton (UCLA)**Title:**An algebraic approach to Borel CSPs**Abstract:**I will explain how some of the algebraic tools behind the CSP dichotomy theorem in computer science can be adapted to answer questions in Borel combinatorics.

**March 31:****Speaker:**Manlio Valenti (University of Udine)**Title:**The first-order part of Weihrauch degrees**Abstract:**Given an order (P,≤), a natural strategy to prove that a ≰ b is to present an example of some c ≤ a such that c ≰ b. Of course, choosing such a c can be very challenging. In the context of TTE and Weihrauch reducibility, (Dzhafarov, Solomon, Yokoyama) introduced the notion of ``first-order part" of a computational problem f, capturing the ``strongest computational problem that is Weihrauch-below f". Characterizing the first-order part of a given problem can be challenging as well, but it proved to be a very useful tool, especially when comparing principles that are (relatively) high in the Weihrauch hierarchy. In this talk, we will study the first-order part from a more algebraic perspective, and study its relation with several other operators already defined in the literature. We will then show how the obtained results can be used to easily characterize the first-order part of many known problems.

**April 7:**No Seminar: ASL North American Annual Meeting**April 14:****Speaker:**Forte Shinko (Cal Tech)**Title:**Realizations of equivalence relations and subshifts**Abstract:**Every continuous action of a countable group on a Polish space induces a Borel equivalence relation. We are interested in the problem of realizing (i.e. finding a Borel isomorphic copy of) these equivalence relations as continuous actions on compact spaces. We provide a number of positive results for variants of this problem, and we investigate the connection to subshifts.

**April 21:**TBA**April 28:****Speaker:**George Metcalfe (University of Bern)**Title:**From ordered groups to ordered monoids and back again**Abstract:**(Joint work with Almudena Colacito, Nikolaos Galatos, and Simon Santschi)Removing the inverse operation from any lattice-ordered group (l-group), such as the ordered additive group of integers, produces a distributive lattice-ordered monoid (l-monoid), but it is not the case that every distributive l-monoid admits a group structure. In particular, every l-group embeds into an l-group of automorphisms of some chain and is either trivial or infinite, whereas every distributive l-monoid embeds into a possibly finite l-monoid of endomorphisms of some chain.

In this talk, we will see that inverse-free abelian l-groups generate only a proper (infinitely based) subvariety of the variety of commutative distributive l-monoids, but inverse-free l-groups generate the whole variety of distributive l-monoids. We will also see that the validity of an l-group equation can be reduced to the validity of a (constructible) finite set of l-monoid equations, yielding --- since the variety of distributive l-monoids has the finite model property — an alternative proof of the decidability of the equational theory of l-groups.

**May 5:****August 18:****Speaker:**Ramyaa (New Mexico Tech)**Title:**Advances in Differentiable Program Learning**Abstract**Inductive Logic Programming (ILP) is a subfield of Artificial Intelligence that learns Logic Programs for a concept from positive and negative examples of the concept. Learning Logic Programs allow for interpretability, can benefit from background knowledge, and require small training set. However, traditional ILP techniques are not noise-tolerant, and do not scale well to large/high-dimensional domains. In recent years, there have been several attempts to use differentiable representations of logic programs and learn them using gradient descent based techniques. This talk introduces these attempts, and our efforts at extending them to learn logic programs with negations and higher-order logic programs.In both cases, considerable care is needed from a theoretical standpoint. Negation should be restricted to avoid paradoxical scenarios. We learned logic programs with stratified negation (in the style of Datalog). Anti-unification (i.e., generalization) of arbitrary higher-order terms is not unique. We learned second order logic programs that are generalizations of first order programs.

**August 25:****Speaker:**Xavier Vidaux (Universidad de Concepción)**Title:**Towers of totally real nested square roots: undecidability, the lattice of subfields, and the quartic extensions within the tower.**Abstract:**After recalling some first order undecidability results in infinite algebraic extensions of the field of rational numbers, I will talk about a concrete family of 2-towers of totally real number fields, namely, ℚ(x_{n})_{ n ≥ 0}where x_{n+1}=√ν + x_{n}for some given positive integers ν and x_{0}. Let K be the union of the ℚ(x_{n}). Though these fields K are somewhat the simplest subfields of an algebraic closure of ℚ that one may construct, they hide a rich variety of natural problems of topological, algebraic, dynamical and logical nature. The results that I will present about these fields are due to M. Castillo, C. Videla, and who writes.

**September 1:****Speaker:**Karen Lange (Wellesley College)**Title:**Classification via effective lists**Abstract:**"Classifying" a natural class of structures is a common goal in mathematics. Providing a classification can mean different things, e.g., determining a set of invariants that settle the isomorphism problem or instead creating a list of all structures of a given kind without repetition of isomorphism type. Here we discuss recent work on classifications of the latter kind from the perspective of computable structure theory. We'll consider natural classes of computable structures such as vector spaces, equivalence relations, algebraic fields, and trees to better understand the nuances of classification via effective lists and its relationship to other forms of classification.

**September 8:****Speaker:**Patricia Blanchette (University of Notre Dame)**Title:**Formalism in Logic**Abstract:**Logic became 'formal' at the end of the 19th century primarily in pursuit of deductive rigor within mathematics. But by the early 20th century, a formal treatment of logic had become essential to two new streams in the current of logic: the collection of crucial 'semantic' notions surrounding the idea of categoricity, and the project of examining the tools of logic themselves, in the way that's crucial for the treatment of completeness (in its various guises). This lecture discusses the variety of different tasks that have been assigned the notion of formalization in the recent history of logic, with an emphasis on some of the ways in which the distinct purposes of formalization are not always in harmony with one another.

**September 15:****Speaker:**Neer Bhardwaj (Weizmann Institute)**Title:**An analytic AKE program with induced structure results on coefficient field and monomial group**Abstract:**We develop an extension theory for analytic valuation rings in order to establish Ax-Kochen-Ersov type results for these structures. New is that we can add in salient cases lifts of the residue field and the value group and show that the induced structure on the lifted residue field is just its field structure, and on the lifted value group is just its ordered abelian group structure. This restores an analogy with the non-analytic AKE-setting that was missing in earlier treatments of analytic AKE-theory. Joint work with Lou van den Dries.

**September 22:****Speaker:**Hunter Spink (Stanford University)**Title:**Random walks and combinatorial dimensions in o-minimal groups**Abstract:**I will discuss some ideas that go into showing that n-independent-step random walks in o-minimally definable group over the real numbers (like a semi-algebraic group) has at most an n^{-C}probability of finishing on a lower-dimensional target set unless the target set contains an ``exponential arc'', where C only depends on the dimension of the target set.

**September 29:**No Seminar**October 6:**No Seminar**October 13:****Speaker:**Jonathan Protzenko (Microsoft Research)**Title:**Computational Law: Programming Languages meet the Law**Abstract:**Many parts of the law, such as tax code, pension computations, etc. encode a clear and unambiguous algorithm: they are called computational law. But ordinary citizens without legal counsel are oftentimes powerless, because layers of legalese and opaque implementations obscure the underlying algorithm.The Correct Computational Law project tackles this inequity by formalizing and capturing computational law using formal methods. Whether it is the French Tax Code, French family benefits or Washington State's Legal Financial Obligations, we formalize, re-implement and find bugs in the law. Doing so, we make it possible for ordinary citizens to prevail over the complexity of the law, rather than falling prey to it.

We will first describe our research agenda and ongoing efforts spanning France and the US. Then, we will focus on a case study: the complexity of federal civil procedure in the US, and how the Lean proof assistant can always find, with mathematical certainty, a path through the pleading phase that fulfills all major procedural requirements.

**October 20:****Speaker:**Kirsten Eisenträger (Penn State University)**Title:**A topological approach to undefinability in algebraic extensions of the rationals**Abstract:**In 1970 Matiyasevich proved that Hilbert's Tenth Problem over the integers is undecidable, building on work by Davis-Putnam-Robinson. Hilbert's Tenth Problem over the rationals is still open, but it could be resolved by giving an existential definition of the integers inside the rationals.Proving whether such a definition exists is still out of reach. However, we will show that only "very few" algebraic extensions of the rationals have the property that their ring of integers are existentially or universally definable. Equipping the set of all algebraic extensions of the rationals with a natural topology, we show that only a meager subset has this property. An important tool is a new normal form theorem for existential definitions in such extensions. As a corollary, we construct countably many distinct computable algebraic extensions whose rings of integers are neither existentially nor universally definable. Joint work with Russell Miller, Caleb Springer, and Linda Westrick.

**October 27:****Speaker:**Gabriel Conant (The Ohio State University)**Title:**Separation for isometric group actions and hyperimaginary independence**Abstract:**In the theory of (finite) permutation groups, P. M. Neumann's Lemma says that if a group G acts on a set X, and P is a finite subset of X such that all points of P have an infinite orbit, then for any other finite set in Q there is a group element g such that gP is disjoint from Q. When applied to the automorphism group of a first-order structure, this lemma can be used to prove a number of useful results in model theory. In this talk, I will present a metric space version of P. M. Neumman's Lemma, along with several applications in the model theory of metric structures. For example, we show that algebraic independence in continuous logic satisfies the "full existence axiom," answering a question of Andrews, Goldbring, and Keisler. Time permitting, I will also discuss some consequences for hyperimaginaries, which are new even in classical discrete logic. Joint work with J. Hanson.

**November 3:****Speaker:**Philip White (George Washington University)**Title:**A Two-Cardinal Ramsey Operator on Ideals**Abstract:**Let I be a κ-complete ideal on κ. Similar to the one-cardinal ineffability operator of Baumgartner, Feng defined a one-cardinal Ramsey operator on I. A basic result of Feng is applying the one cardinal Ramsey operator to I yields a normal ideal. Feng also showed under what conditions the ideal given by applying the Ramsey operator is equivalently generated by a "pre-Ramsey" ideal as well as the Π_{n+1}indescribability ideal. Finally Feng showed iterated use of the one-cardinal Ramsey operator forms a proper hierarchy. Feng was able to show these results for <κ+ iterations of the one-cardinal Ramsey operator by utilizing canonical functions. Similar to other results of Brent Cody and the presenter, these results in the one-cardinal setting can be generalized to a two-cardinal setting. The theorems of Feng will be discussed in detail as well as the analogous two-cardinal versions of Brent Cody and the presenter.

**November 10:****Speaker:**Vincent Bagayoko (Université de Mons)**Title:**Some ordered groups of generalized series**Abstract:**I will talk about some problems relating linearly ordered groups to logic and real geometry. I will show how to certain generalized series, similar to transseries, in order to answer an open question regarding orderable groups.

**November 17:****Speaker:**Barbara Csima (University of Waterloo)**Title:**Degrees of Categoricity**Abstract:**A degree of categoricity is a Turing degree that exactly captures the complexity of computing isomorphisms between computable copies of some computable structure. In this talk I will start by giving some easy examples of degrees of categoricity. I will then give a review of what is known about degrees of categoricity, culminating in new results (joint work with Dino Rossegger).

**November 24:**No Seminar; public holiday in USA for Thanksgiving**December 1:****Speaker:**David Schrittesser (University of Toronto)**Title:**Nonstandard analysis and statistical decision theory**Abstract:**Statistical decision theory takes inspiration from game theory to provide a basic framework in which one can reason about optimality (or lack thereof) of statistical procedures, such as estimators and tests.One property of a statistical procedure is "admissibility": Roughly, a procedure is admissible if there is no other procedure which does better under all circumstances ("better" in a sense specified by the decision theoretical framework, i.e., with respect to a fixed loss function). This is certainly a necessary condition for optimality.

Admissibility is notoriously hard to characterize. In particular, establishing a characterization in Bayesian terms has been an ongoing pursuit for decades in statistical decision theory. Recently we have found a characterization of admissibility in Bayesian terms, by using prior probability distributions which can take on infinitesimal values. We are also able to draw connections to classical methods establishing admissibility, such as Blyth's method and Stein's characterization of admissibility (which does partially characterize admissibility, but only under additional, technical hypotheses). Finally, our method has applications in concrete problems such as the problem of establishing the admissibility of the Graybill-Deal estimator.

The talk will not presuppose any knowledge on statistics or nonstandard analysis. Everything is joint work with D. Roy and H. Duanmu.

**December 8:**No Seminar**December 15:****Speaker:**Francesca Zaffora Blando (Carnegie Mellon University)**Title:**Randomness and Invariance**Abstract:**The first (semi-)formal definition of randomness for infinite binary sequences dates back to von Mises’ work in the foundations of probability and statistics. According to von Mises, a sequence is random if, within it, the relative frequencies of 0 and 1 converge to a limit and these limiting relative frequencies are invariant under a class of transformations called selection rules. The randomness notion introduced by von Mises is nowadays widely regarded as being too weak and his account has been supplanted by the theory of algorithmic randomness, which characterizes randomness using the tools of computability theory and measure theory. The goal of this talk is two-fold. First, I will discuss a lesser-known characterization of Schnorr randomness due to Schnorr, which demonstrates that it is possible to obtain a satisfactory randomness notion by defining randomness, analogously to how von Mises did it, in terms of the invariance of limiting relative frequencies. Then, I will discuss how other canonical algorithmic randomness notions are similarly characterizable in terms of the preservation of natural properties under the class of computable measure-preserving transformations. This talk is based on joint work with Floris Persiau.

**December 22:**No Seminar**December 29:**No Seminar**January 5:**No Seminar: ASL / Joint Mathematics Meetings**January 12:**No Seminar**January 19:****Speaker:**Patrick Lutz (UCLA)**Title:**The Solecki dichotomy and the Posner Robinson theorem**Abstract:**The Solecki dichotomy in descriptive set theory, roughly stated, says that every Borel function on the real numbers is either a countable union of partial continuous functions or at least as complicated as the Turing jump. The Posner-Robinson theorem in computability theory, again roughly stated, says that every non-computable real looks like 0' relative to some oracle. Superficially, these theorems look similar: both roughly say that some object is either simple or as complicated as the jump. However, it is not immediately apparent whether this similarity is more than superficial. If nothing else, the Solecki dichotomy is about third order objects --- functions on the real numbers --- while the Posner-Robinson theorem is about second order objects --- individual real numbers. We will show that there is a genuine mathematical connection between the two theorems by showing that the Posner-Robinson theorem plus determinacy can be used to give a short proof of a slightly weakened version of the Solecki dichotomy, and vice-versa.

**January 26:****Speaker:**Adele Padgett (McMaster University)**Title:**Regular solutions of systems of transexponential polynomials**Abstract:**I will explain an open problem in the model theory of ordered fields and outline a possible strategy for resolving it. The problem is whether there are o-minimal fields that are "transexponential," i.e., which define functions that eventually grow faster than any tower of exponentials. In recent work, I gave evidence indicating that a particular transexponential expansion of the real field might be o-minimal. A possible next step would be to apply a criterion of Lion which grew out of Wilkie's proof that the real exponential field is o-minimal.

**February 2:****Speaker:**Maribel Fernandez (Kings College London)**Title:**Nominal Techniques for the Specification of Languages with Binders**Abstract:**The nominal approach to the specification of languages with binding operators, introduced by Gabbay and Pitts, has its roots in nominal set theory. Nominal logic is a theory of first-order logic that axiomatizes the notions of fresh name, name swapping and abstraction from nominal sets, making it an ideal tool for the specification of the semantics of programming languages. In this talk, we will start by recalling the main concepts of nominal logic, and then we will show how to apply these ideas to specify calculi with binders. More precisely, we will introduce nominal syntax (including the notions of fresh atoms and alpha-equivalence), present matching and unification algorithms that take into account the alpha-equivalence relation, define nominal rewriting (a generalisation of first-order rewriting that provides in-built support for alpha-equivalence following the nominal approach) and give examples of application.

**February 9:****Speaker:**Liling Ko (Ohio State University)**Title:**Computable smallness is not intrinsic smallness**Abstract:**We construct a set A that is computably small but not intrinsically small. To understand these terms, we liken A to a game show host playing against a class of computable contestants, analogous to an infinite variant of the Monty Hall problem. The host has infinitely many doors arranged in a line, and each door hides either a goat or a car. A contestant selects infinitely many doors to open and wins if a non-zero density of the selected doors hides a car. Contestants that are disorderly can select doors out of order, opening door i after door j>i. Are disorderly contestants more difficult to beat than orderly ones? This is known to be true if contestants are allowed to be adaptive, where they may choose a different door depending on the outcomes of the previously opened ones [1] (via the theorem that MWC-stochasticity 0 does not imply Kolmogorov-Loveland-stochasticity 0). We give a constructive proof to show that the statement also holds in the non-adaptive setting, shedding light on a disorderly structure that outperforms orderly ones. This is joint work with Justin Miller.[1] Merkle, Wolfgang and Miller, Joseph S and Nies, Andre and Reimann, Jan and Stephan, Frank. Kolmogorov--Loveland randomness and stochasticity. Annals of Pure and Applied Logic, vol.138 (2006), no.1-3, pp.183--210.

**February 16:****Speaker:**Michael Hrušák (Universidad Nacional Autónoma de México)**Title:**Model theory and topological groups**Abstract:**We shall discuss some recent applications of model-theoretic methods to the study of topological groups. In particular, we shall discuss solutions to old problems of Comfort and van Douwen and the use of Fraissé theory to the study of groups of homeomorphisms.

**February 23:****March 2:****Speaker:**Konstantin Slutsky (Iowa State University)**Title:**Partial actions and orbit equivalence relations**Abstract:**In this talk, we will discuss the framework of partial actions for constructing orbit equivalent actions of Polish groups. While related ideas have been employed in ergodic theory and Borel dynamics for many years, the particular viewpoint of partial actions simplifies construction of orbit equivalent actions of distinct groups.As an application, we will present a Borel version of Katok's representation theorem for multidimensional Borel flows. One-dimensional flows are closely connected to actions of ℤ via the so-called "flow under a function" construction. This appealing geometric picture does not generalize to higher dimensions. Within the ergodic theoretical framework, Katok introduced the concept of a special flow as a way to connect multidimensional ℝ

^{d}and ℤ^{d}actions. We will show that similar connections continue to hold in Borel dynamics.Another illustration of the partial actions techniques that we intend to touch is the following result: a Borel equivalence relation generated by a free R-flow can also be generated by a free action of any non-discrete and non-compact Polish group. This is in contrast with the situation for discrete groups, where amenability distinguishes groups that can and cannot generate free finite measure-preserving hyperfinite actions.

**March 9:**No Seminar

Send correspondence to

School of Mathematical and Statistical Sciences Mail Code 4408 Southern Illinois University 1245 Lincoln Drive Carbondale, Illinois 62901 Office: (618) 453-6582 Fax: (618) 453-5300 Home: (618) 985-3429Wesley Calvert's Web Page