Refreshments will be served in the 9th floor lounge at 3:30PM before talks, subject the evolving pandemic conditions.

We will live stream the local logic seminar with the following login information:

Zoom link to local UW logic seminar

Meeting ID: 986 3594 0882

Passcode: 003073

The joint Midwest Computability/Model Theory Seminar will be live streamed
with the following login information:

Zoom link

Meeting ID: 997 5433 2165

Passcode: midwest

- 1/30/2024 4PM,
Steffen Lempp,
UW

Title: The Borel complexity of the class of models of first-order theories (video and slides and related paper)Abstract: We investigate the descriptive complexity of the set of models of first-order theories. Using classical results of Solovay and Knight, we give a sharp condition for complete theories to have a Π^{0}_{ω}-complete set of models. We also calibrate the complexity of sets of models of some other complete theories. (This is joint work with Andrews, Gonzalez, Rossegger and Zhu, and related to recent work of Enayat and Visser.) - 2/6/2024 4PM,
Hongyu
Zhu, UW

Title: The Borel complexity of the class of models of first-order theories: the finite case (video and slides and related paper)Abstract: This is a follow-up to the previous week's talk where we mainly consider boundedly axiomatizable theories. We relate the quantifier complexity of the axiomatization to the Wadge degree of the set of models and present several examples demonstrating the relationship. We then consider the effectiveness of the reductions. At last, we discuss some open questions of interest to us. (Based on joint work with Andrews, Gonzalez, Lempp, Rossegger and related to recent work of Enayat and Visser.) - 2/7/2024 (
**analysis seminar in VV B223, 3:30PM**), Don Stull, University of Chicago, Illinois

Title: Dimensions of pinned distance sets in the plane (slides)Abstract: In this talk, we discuss recent work on the Hausdorff and packing dimension of pinned distance sets in the plane. Given a point x in the plane, and a subset E, the pinned distance set of E with respect to x is the set of all distances between x and the points of E. An important open problem is understanding the Hausdorff, and packing, dimensions of pinned distance sets. We will discuss ongoing progress on this problem, and present improved lower bounds for both the Hausdorff and packing dimensions of pinned distance sets. We also discuss the computability-theoretic methods used to achieve these bounds. - 2/13/2024 4PM,
Uri Andrews,
UW

Title: Degree spectra of theories (related papers: Andrews/Miller, Andrews/Knight, Andrews/Cai/Diamondstone/Lempp/Miller)Abstract: The degree spectrum of a theory T captures the difficulty of the problem of computing some model of the theory T. Explored previously in several different contexts, e.g., Solovay characterized the degree spectra of completions of PA, theory spectra were introduced as a topic of focus in their own right by myself and Joseph S. Miller in the early 2010s. I hope to give a sampling of results and an overview of what we know about this topic. I believe there are yet many interesting and accessible questions in this topic. - 2/16/2024
(
**department colloquium in VV B239, 4PM**), Jack Lutz, Iowa State University, Ames

Title: Algorithmic fractal dimensions (slides)Abstract: Algorithmic fractal dimensions are computability-theoretic versions of Hausdorff dimension and other fractal dimensions. This talk will introduce algorithmic fractal dimensions with particular focus on the Point-to-Set Principle. This principle has enabled several recent proofs of new theorems in geometric measure theory. These theorems, some solving long-standing open problems, are classical (meaning that their statements do not involve computability or logic), even though computability has played a central in their proofs. - 2/20/2024 4PM,
Josiah
Jacobsen-Grocott, UW

Title: The theory of degree structures with jump (video)Abstract: It in this talk we look at work done in understanding the complexity of the structure the Turning degrees D_{T}with different languages using ≤, ∨, and jump. For instance, it is known that all of these are definable from ≤, and that the full theory is equivalent to second-order arithmetic. We also consider what happens when we limit the number of quantifiers. For instance. the ∀∃-theory of (D_{T},≤) is decidable, but the ∀∃-theory of (D_{T},≤,∨,') is undecidable. We will also look how some of these results can be translated to results about the theory of the enumeration degrees. - 2/29/2024
**Midwest Model Computability Seminar (joint with Midwest Model Theory Seminar), John Crerar Library Building 390, 5730 S. Ellis Ave., University of Chicago**

Brown Bag Lunch: noon

Speakers:- 1PM, Ronnie Nagloo, University of Illinois-Chicago

Title: Model theory and differential equationsThis talk provides a survey of recent work around applications of model theory to the study differential equations. In particular, we will focus on the work over the past decade centered around using geometric stability to study concrete definable sets in Differentially Closed Fields (DCF).

- 1:55PM, Isabella Scott, University of Chicago, Illinois

Title: Effective constructions of existentially closed groups (video)Existentially closed groups were introduced in 1951 as a group-theoretic analogue to algebraically closed fields. Since then, they have been further studied by Neumann, Macintyre, and Ziegler, who elucidated deep connections with model theory and computability theory. We review some of the literature on existentially closed groups and present new results that further refine these connections. In particular, we are able to pinpoint more precisely how complexity arises in existentially closed groups, and quantify how much is visible to the "local" structure. We will also discuss constructions giving two existentially closed groups that are "as different as possible".

- 3:10PM, Adam Topaz,
University of Alberta, Edmonton, Canada

Title: Formalizing Lawvere theories in dependent type theory (video)Lawvere theories provide a categorical approach to doing Universal Algebra, and their algebras have the benefit of being easily interpreted in any category with the correct limits. This talk will discuss some work in progress toward encoding (multi-sorted) Lawvere theories in dependent type theory, using the Lean4 interactive proof assistant (ITP). Specifically, after an introduction to the mathematical theory itself, I'll talk about why one might be interested in formalizing these objects in an ITP, as well as some of the challenges around making this formalization useful in relation to preexisting algebraic hierarchies.

- 4:05PM, Steffen
Lempp, UW

Title: Minimal covers in the Weihrauch degrees (video and slides)We study the existence of minimal covers and strong minimal covers in the Weihrauch degrees. We characterize when a problem f is a minimal cover or strong minimal cover of a problem h. We show that strong minimal covers only exist in the cone below id and that the Weihrauch lattice above id is dense. From this, we conclude that the degree of id is first-order definable in the Weihrauch degrees and that the first-order theory of the Weihrauch degrees is computably isomorphic to third-order arithmetic.This is joint work with J. Miller, Pauly, M. Soskova and Valenti.

- 1PM, Ronnie Nagloo, University of Illinois-Chicago
- 3/12/2024 4PM,
Vittorio
Cipriani (remote talk), Technical University of Vienna, Austria

Title: Classifying isomorphism problems and learning of algebraic structures (video and slides)Abstract: We study the classification of isomorphism problems with countably many isomorphism types, combining ideas from computable structure theory and algorithmic learning theory. The framework we use was defined in a series of papers by Bazhenov, Fokina, Kötzing, and San Mauro. Here, given a countable family K of structures, a*learner*receives larger and larger pieces of an isomorphic copy of a structure in K and, at each stage, is required to output a conjecture about the isomorphism type of such a structure. The learning is*successful*if the conjectures eventually stabilize to a correct guess.Together with Bazhenov and San Mauro, we showed that a countable family of countable structures is learnable if and only if the corresponding isomorphism problem reduces to the equivalence relation E

_{0}. Replacing E_{0}with other Borel equivalence relations, one obtains a hierarchy to rank such isomorphism problems.Bazhenov, Fokina, and San Mauro gave a model-theoretic characterization of learnability; here we provide similar characterizations about other classical learning criteria and the learning power of several equivalence relations (with a focus on Friedman-Stanley jumps of the identity on 2

^{N}and N^{N}). This talk collects joint work with Bazhenov, Jain, Marcone, San Mauro, and Stephan. - 3/19/2024 4PM,
Steffen Lempp,
UW

Title: A jump for the Weihrauch degrees (video and slides)Abstract: I will present the definition of a version of a jump function on the Weihrauch degrees which is degree-theoretic, strictly increasing on each degree, and monotonic. The jump can in fact be defined in two different ways, each of which has the flavor of a total continuation of a multi-valued function given by the original problem.This new version of a jump has a number of surprising properties, in particular, it is indeed injective on the Weihrauch degrees (and thus induces an embedding of these degrees into themselves).

We have determined the specific jump of some problems: E.g., the jump of the least degree is the degree of id; and the jump of choice on Baire space is the total continuation of this problem.

I will discuss other recent results on this jump notion in my talk. This is joint with Andrews, Marcone, J. Miller and Valenti.

- 4/2/2024 4PM,
Alice Vidrine, UW

Title: Some results on enumeration Weihrauch reduction (video and slides)Abstract: Enumeration Weihrauch (eW) reduction is a variant of Weihrauch reduction that replaces Turing functionals by enumeration operators, using a notion of "positive information" computation. In this setting, several of the benchmark choice problems in the Weihrauch setting become separated. We discuss some of the more striking examples and their proofs, and describe the progress in the search for a first-order difference between the eW degrees and Weihrauch degrees. - 4/9/2024 4PM,
Tim McNicholl,
Iowa State University, Ames

Title: Computability theory of operator algebras (video and related papers: Burton/Eagle/Fox/Goldbring/Harrison-Trainor/McNicholl/Melnikov/Thewmorakot and McNicholl)Abstract: Over the past decade, a program to adopt computable structure theory to metric structures has emerged. This program, called effective metric structure theory, blends the fundamental ideas of computable analysis and computable structure theory. Many results about computable presentations of metric spaces and Banach spaces have been obtained. I will discuss recent discoveries about computable presentability and computable categoricty of C^{*}-algebras.

Dinner: Fugu Asian Fusion (411 W. Gilman St.) around 6PM - 4/16/2024 4PM,
Isabella Scott, University of Chicago, Illinois

Title: Computability-theoretic investigations into existentially closed groups (video and related paper)Abstract: Existentially closed groups were introduced by WR Scott in 1951 in analogue with algebraically closed fields. Since then, they have been further studied by Neumann, Macintyre, and Ziegler, who elucidated deep connections with model theory and computability theory. We undertake an investigation into the complexity of existentially closed groups, which uncovers surprising stratifications and connections not visible without computability-theoretic tools.(For those who have seen me give similarly titled and abstracted talks, I plan to dive deeper into the proofs of my results than in earlier versions of the talk.)

Dinner:A La Brasa Mexican Grill (15 N. Broom St.) around 6PM - 4/30/2024 4PM,
Josiah
Jacobsen-Grocott, UW

Title: TBA (thesis defense)Abstract: TBA - 5/2/2024 4PM (
**room B115 Van Vleck**) Yayi Fu, University of Notre Dame, Indiana

Title: The Erdős-Hajnal property in NIP theoriesAbstract: We show a proof using model-theoretic techniques and substitution that the Erdős-Hajnal property holds for graphs with VC-dimension ≤ 2.We also show that the family of graphs with bounded VC-minimal complexity, a notion that arises from VC-minimal theory, has the strong Erdős-Hajnal property.

And we show a lemma about combs and pure pairs that I found when attempting to prove the Erdős-Hajnal property for dp-minimal graphs.

Dinner: Himal Chuli Restaurant (318 State St.) around 6PM - 5/7/2024 4PM,
Meng-Che ("Turbo")
Ho, California State University, Northridge

Title: TBAAbstract: TBA

Dinner: TBA around 6PM - 5/21/2024
**3PM**, Keng Meng ("Selwyn") Ng, Nanyang Technological University, Singapore

Title: TBAAbstract: TBA

**same day**: 4PM, Luca San Mauro, University of Bari, Italy and Technical University of Vienna, Austria

Title: TBAAbstract: TBA

Dinner: TBA around 6PM

- 10/24/2023 4PM,
Wim Ruitenburg,
Marquette University, Milwaukee, Wisconsin

Title: Predicate logic for transitive Kripke models (video and slides)Abstract: We consider a predicate logic for transitive Kripke models similar to intuitionistic predicate logic for reflexive transitive Kripke models. This logic and its model theory can be studied as a generalization of classical and model theory without any philosophical concern. - 11/2/2023 4PM,
David Gonzalez,
University of California-Berkeley

Title: Scott sentence complexities of linear orderingsAbstract: The concept of Scott sentence complexity was introduced by Alvir, Greenberg, Harrison-Trainor and Turetsky and gives a way of assigning countable structures to elements of the Borel hierarchy. By calculating the Scott sentence complexities occurring in a class of structures, we obtain a detailed picture of the descriptive complexity of its isomorphism relation. We study possible Scott sentence complexities of linear orderings using two approaches. First, we investigate the effect of the Friedman-Stanley embedding on Scott sentence complexity and show that it only preserves complexities. We then take a more direct approach and exhibit linear orderings of all Scott sentence complexities except for a limit ordinal. We show that the former cannot be the Scott sentence complexity of a linear ordering. In the process, we develop new techniques which appear to be helpful to calculate the Scott sentence complexities of structures in general.This talk is based on joint work with Dino Rossegger.

- 11/7/2023
**Midwest Computability Seminar, University of Chicago, John Crerar Library Building 390**

(live streamed on Zoom, Meeting ID: 997 5433 2165, Passcode: midwest)

Brown bag lunch: in John Crerar Library Building 390 at noon

Speakers:- 1PM, Peter Cholak,
University of Notre Dame, Indiana

Title: Some computability-theoretic aspects of Dobrinen’s result that the universal triangle free graph has finite big Ramsey degree (video)Abstract: We will discuss recent work of Cholak, Dobrinen, and McCoy. Mostly, we will focus on colorings within the universal triangle free graph of nodes, edges, and non-edges. The result that the universal triangle free graph has finite big Ramsey degree implies for colorings of nodes, edges, or non-edges that there is a copy of the universal triangle free graph with a minimal number of colors. The minimum depends on the objects we are coloring, not the coloring itself. We will discuss this number for our three cases. A copy of the universal triangle free graph with a minimal number of colors is called a minimal heterogeneous copy. We will also discuss what is known about the computability-theoretic complexity of these minimal heterogeneous copies.

- 2:30PM, David
Gonzalez, University of California-Berkeley

Title: The omega-Vaught's Conjecture (video and slides)Abstract: Robert Vaught conjectured that the number of countable models of any given list of axioms must be either countable or continuum, but never in between. Despite all the work that has gone into this conjecture over the past sixty years, it remains open. It is one of the best-known, long-standing open questions in mathematical logic. We introduce the omega-Vaught's conjecture, a strengthening of Vaught's conjecture for infinitary logic. We have shown this conjecture holds for linear orderings, a strengthening of Vaught's conjecture for linear orderings originally proved by Steel. The approach notably differs from Steel's proof (and any other previously known proof of Vaught's conjecture for linear orderings) in that it makes no appeal to lemmas from higher computability theory or descriptive set theory. This talk is based on joint work with Antonio Montalbán.

- 4PM, Tiago Royer, University of Chicago, Illinois

Title: Asymptotic notions of computability (video 1, video 2 and slides)Abstract: In the classical setting, we consider that a Turing machine solves a problem if, for all inputs, the machine halts with the correct output for this problem. We can relax this notion by requiring the machine to halt and be correct only on asymptotically all inputs. If we still require the machine to always halt, we have coarse computability; if we allow the machine to not halt sometimes but require it to always be correct when it does, we have generic computability. I will talk about these notions and their degree structures, and I will present a proof that there are minimal degrees for coarse reducibility.

- 1PM, Peter Cholak,
University of Notre Dame, Indiana
- 11/21/2023 4PM,
Meng-Che
"Turbo" Ho, UW

Title: Word problems of groups as ceers (video)Abstract: Since Dehn proposed the word problem in 1912, it has been an important topic of study in both group theory and computability theory. Most naturally occurring groups are recursively enumerable (r.e.). Their word problem can be defined to be the r.e. set of words equal to the identity of the group, which is analyzed using Turing reductions. By the Higman Embedding Theorem, any r.e. degree is realized as a word problem of an r.e. group.In this talk, we consider the word problem of a group as a computably enumerable equivalence relation (ceer), namely, two words are equivalent if and only if they are equal in the group. We compare ceers using the notion of computable reductions. We see that, while the Higman embedding theorem preserves Turing degrees, it does not preserve ceer degrees in general. Contrasting the classical context, we show that not every ceer degree is realized as the word problem of some group. This shows that the landscape of word problems as ceers is very different from the classical theory.

This is a joint work with Uri Andrews and Luca San Mauro.

- 11/29/2023
(
**department colloquium**), 4PM in**room B239 Van Vleck**,

Caroline Terry, Ohio State University, Columbus

Title: Measuring combinatorial complexity via regularity lemmasAbstract: Many tools have been developed in combinatorics to study global structure in finite graphs. One such tool is called Szemerédi’s regularity lemma, which gives a structural decomposition for any large finite graph. Beginning with work of Alon-Fischer-Newman, Lovász-Szegedy, and Malliaris-Shelah, it has been shown over the last 15 years that regularity lemmas can be used to detect structural dichotomies in graphs, and that these dichotomies have deep connections to model theory. In this talk, I present extensions of this type of result to arithmetic regularity lemmas, which are analogues of graph regularity lemmas, tailored to the study of combinatorial problems in finite groups. This work uncovered tight connections between tools from additive combinatorics, and ideas from the model theoretic study of infinite groups. - 12/12/2023 4PM,
Ang Li, UW

Title: Genericity and depth (video and slides)Abstract: An infinite binary sequence is Bennett deep if the difference between time-bounded prefix-free Kolmogorov complexity and prefix-free Kolmogorov complexity of its initial segments is eventually unbounded for any computable time bound. In this talk, we show that there is a deep 1-generic set.