The Online Logic Seminar meets weekly on Thursdays at 1pm US Central Daylight Time 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.

**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:**Artem Chernikov (UCLA)**October 15:**John Baldwin (University of Illinois Chicago)**October 22:**Steffen Lempp (U of Wisconsin)**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:**Farzaneh Derakhshan (Carnegie Mellon)**November 12:**Lynn Scow (Cal State San Bernardino)**November 19:**Anush Tserunyan (McGill University)**November 26:**No seminar; public holiday in USA for Thanksgiving**December 3:**Johanna Franklin (Hofstra University)**December 10:**TBA**December 17:**TBA**December 24:**No seminar: Christmas Eve Holiday**December 31:**TBA**January 7:**No seminar; ASL Winter / Joint Mathematics Meetings**January 14:**Aleksandra Kwiatkowska (U of Wrocław)**January 21:**Angeliki Koutsoukou-Argyraki (U of Cambridge)**January 28:**TBA**February 4:**Peter Cholak (Notre Dame)

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

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