Online Logic Seminar

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.

After the seminar, we will meet for coffee, cookies, and informal conversation (bring your own coffee and cookies) at https://spatial.chat/s/Online-Logic-Seminar.

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

Upcoming Talks

• 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: Damir Dzhafarov (U Conn)

• August 27: TBA

• September 3: TBA

• September 10: Mirna Džamonja (U of East Anglia and Paris 1)

• September 17: TBA

• September 24: TBA

Past Talks in This Series

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

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-3429