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.

**May 5:**

**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.

Send correspondence to

Department of Mathematics Mail Code 4408 Southern Illinois University 1245 Lincoln Drive Carbondale, Illinois 62901 Office: (618) 453-6573 Fax: (618) 453-5300 Home: (618) 985-3429Wesley Calvert's Web Page