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

- 1/26/2023 4PM,
Ronnie
Nagloo, University of Illinois-Chicago

Title: Geometric triviality in differentially closed fields (video and slides)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 David Blázquez-Sanz, Guy Casale and James Freitag on Fuchsian groups (discrete subgroups 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.

Dinner: Great Dane Pub (123 E. Doty St.) around 6:30PM (**Wednesday, Jan. 25th**) - 1/31/2023 4PM,
Alberto
Marcone, University of Udine, Italy

Title: Some (extra)ordinary equivalences in reverse mathematics (video and slides and related paper)Abstract: In 1980 Rival and Sands proved the following theorem: (RSpo) Every infinite partial order P of finite width contains an infinite chain C such that every element of P is either comparable with no element of C or with infinitely many elements of C.We study this statement and its variants from the viewpoint of reverse mathematics. It turns out that various forms of (RSpo) are equivalent to different forms of the principle ADS that had been studied in reverse mathematics as a consequence of Ramsey's Theorem for pairs: ADS states that every infinite linear order has either an infinite ascending chain or an infinite descending chain.

These equivalences are (extra)ordinary because previously no theorem of ordinary mathematics was known to be equivalent to principles such as ADS which form the so-called zoo of reverse mathematics: a large collection of statements that are inequivalent to each other and to the classic big five of reverse mathematics.

To obtain our results we give a proof of (RSpo) which is very different from the one given by Rival and Sands: the latter in fact iterates the use of a lemma equivalent to Π

^{1}_{1}-comprehension. Ideas from the new proof allow to strengthen (RSpo) by replacing finite width with no infinite antichains in the hypothesis.Joint work with Marta Fiori Carones, Giovanni Soldà and Paul Shafer.

Dinner: Diamond's Cafe (260 W. Gilman St.) around 6PM - 2/7/2023
**3:45PM**, Liling Ko, Ohio State University, Columbus

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

Dinner: Morris Ramen (106 King St.) around 6PM (**Monday, Feb. 6th**) - 2/21/2023 4PM,
Giovanni Soldà, University of Ghent, Belgium

Title: On the Weihrauch degrees of the additive Ramsey theorems (video and slides)Abstract: The additive Ramsey theorem for a linear order X is the principle saying that if c is a coloring of the 2-element subsets of X into a finite monoid such that c satisfies certain structural conditions (which intuitively relate the order on X with the monoidal structure of the set of colors), then there exists an infinite c-homogeneous set order-isomorphic to X.In this talk, we will be interested in the study of the cases where X=N and X=Q: after a brief introduction regarding their reverse mathematical strength, we will proceed to determine the Weirauch degrees of the problems corresponding to these principles, and of several other related to them.

This is joint work with Arno Pauly and Pierre Pradic.

- 2/28/2023 4PM,
Mike
Titelbaum,
UW philosophy department

Title: The Logical Firmament (video and slides)Abstract: This will be a talk in the epistemology of logic and mathematics.Most knowledge comes to us through causal interaction with its subject matter. Yet we clearly can't causally interact with abstract logical and mathematical entities. This generates Benacerraf's (1973) challenge of how we come to know about such entities at all. After sketching the outlines of the problem, I will provide a new (partial) answer focusing on what I call catenary truths — truths about combinations of operations that are general enough to apply both to the logical entities we investigate and to the processes employed in that investigation.

- 3/7/2023 4PM,
Peter Gerdes, Indiana
University, Bloomington

Title: A non-trivial 3-REA set not computing a 3-generic (video and slides)Abstract: It's well known that every function not dominated by a computable function computes a weak 1-generic and that every non-computable r.e. set computes a 1-generic. In previous work with Andrews and Miller, we demonstrated that every function not dominated by a 0'' computable function computes a weak 2-generic but that this result doesn't extend to n=3. In this talk, I review these results and discuss a new result that there is a 3-REA set not computable from 0'' that doesn't compute a weak 3-generic.

Dinner: Taste of Sichuan (515 State St.) around 6PM - 4/4/2023 4PM,
Joel Hamkins,
University of Notre Dame, Indiana

Title: TBAAbstract: TBA - 4/7/2023 4PM (room TBA),
Liang Yu,
Nanjing University, China

Title: TBAAbstract: TBA

Dinner: TBA around 5:30PM - 4/13/2023 (tentative date) 4PM,
Arno
Pauly, University of Swansea, Wales

Title: TBAAbstract: TBA

Dinner: TBA around 5:30PM - 4/18/2023 4PM,
Dino Rossegger,
University of California-Berkeley

Title: TBAAbstract: TBA

Dinner: TBA at 5:30PM - 4/25/2023 4PM,
Elvira Mayordomo,
University of Zaragoza, Spain

Title: TBAAbstract: TBA - 5/2/2023 4PM,
TBA

Title: TBAAbstract: TBA - 5/16/2023 (tentative date) 4PM,
Dilip Raghavan,
National University of Singapore (visiting University of Toronto)

Title: TBAAbstract: TBA

Dinner: TBA around 5:30PM

(No seminar on February 14 due to Valentine's Day.)

(No seminar on March 14, 21 and 28 due to spring break and conferences.)

- 9/13/2022 4PM,
Jim
Freitag, University of Illinois at Chicago

Title: What is forking degree and why should you care? (video and slides)Abstract: In this talk we will introduce a new invariant of types in stable theories which has applications to functional transcendence and the geometry of compact complex manifolds. The talk won't assume that you know any stability theory (or really even any model theory at all). In this talk, we'll focus on applications around transcendence results and talk about connections with point-counting problems and o-minimality. If time permits, we'll talk about how the new invariant has played a role in the resolution of an old open problem in algebraic differential equations and new proofs of the irreducibility of equations from the Painlevé family.

Dinner: Great Dane Pub (123 E. Doty St.) around 6PM - 9/20/2022 4PM,
Sam
Braunfeld, Charles University, Prague, Czech Republic

Title: A tour of monadically tame theories (video and slides)Abstract: For a property P, say a theory T is monadically P if every unary expansion of T has P. We will survey various characterizations of the monadic variants of model-theoretic dividing lines, and their applications to the combinatorics of finite and countable structures. - 9/27/2022 4PM,
Manlio Valenti,
UW

Title: Some results on the structure of Weihrauch degrees (video and slides)Abstract: In this talk, we will explore some algebraic properties of the Weihrauch degrees. Despite the recent efforts, a large number of questions regarding the structure of Weihrauch degrees are still unexplored. We will start with a brief overview of some known results, and then present some recent findings on the existence of chains/antichains in the Weihrauch degrees. We will also show how, despite the close interplay between Medvedev and Weihrauch reducibility, the two lattices have a very different structure. - 10/4/2022 4PM,
Steffen Lempp,
UW

Title: Toward deciding the ∀∃-theory of the Σ^{0}_{2}-enumeration degrees (video and slides)Abstract: I will report on joint work with Goh, Ng and Soskova on particular extensions of embeddings of finite partial orders into the Σ^{0}_{2}-enumeration degrees: Let P be a finite antichain, and let Q_{i}(i ≤ n) each extend P by one point. We will present a complete decision procedure on when an embedding of P into the Σ^{0}_{2}-enumeration degrees can be extended to an embedding of Q_{i}for some i ≤ n.This constitutes progress toward the general case of arbitrary finite partial orders Q

_{i}(i ≤ n) extending an arbitrary finite partial order P, a decision procedure for which would also give a decision procedure for the ∀∃-theory of the Σ^{0}_{2}-enumeration degrees. - 10/11/2022 4PM,
Dan
Turetsky, Victoria University of Wellington, New Zealand

Title: Wadge degrees, games, and the separation and reduction properties (video and slides)Abstract: In this talk, I will give an overview of the picture of the Borel Wadge degrees. Our system of descriptions allows us to describe their Delta-classes, as well as specify which degrees have the separation or reduction properties. Part of our analysis is based on playing games along our descriptions, and so I will explain how these games are played and what they can tell us. - 10/18/2022 4PM,
Dana
Bartošová, University of Florida, Gainesville

Title: Transfer of Ramsey phenomena via semi-retractions (video and slides)Abstract: The classical finite Ramsey theorem states that for any natural numbers m ≤ n and a number of colours k ≥ 2, there is a natural number N such that whenever we colour m-tuples of {1,2,..., N} by k colours, there is an n-element subset of {1,2,..., N} whose all m-element subsets received the same colour. This theorem has generalizations in possibly every area of mathematics. In this talk, we will focus on structural Ramsey theory, which in place of finite sets speaks about finite structures in some first-order language, such as finite graphs, finite Boolean algebras, or finite vector spaces over finite fields. Lynn Scow isolated a model-theoretic notion of a semi-retraction between a pair of structures. In our recent paper, we identified the optimal conditions on the structures under which a semi-retraction transfers the Ramsey properties from the class of finitely generated substructure of one structure to the other. We found that, surprisingly, the notion of semi-retraction is related to a more abstract notion of pre-adjunction from category theory. This is a joint work with Lynn Scow.

Dinner: Himal Chuli (318 State St.) around 5:30PM - 10/25/2022 4PM,
Joe Miller, UW

Title: Generic Muchnik reducibility (video and slides)Abstract: If A and B are countable structures, then A is Muchnik reducible to B if every ω-copy of B computes an ω-copy of A. This can be interpreted as saying that B is intrinsically at least as complicated as A. Schweber suggested a natural extension of Muchnik reducibility to arbitrary structures: if A and B are (possibly uncountable) structures, then A is generically Muchnik reducible to B if in some (equivalently, any) forcing extension that makes both A and B countable, A is Muchnik reducible to B.I will survey most of what is known about the generic Muchnik degrees, culminating in work with Andrews, Schweber, and Soskova. We have proved the existence of a structure with degree strictly between Cantor space and Baire space. It remains open whether an expansion of Cantor space can be strictly in between, but we have proved that no closed expansion or unary expansion can work. Similar results hold for the interval between Baire space and the Borel complete degree (i.e., the degree that bounds all Borel structures). The proofs mix descriptive set theory (including some use of determinacy) with injury and forcing constructions native to computable model theory.

- 11/1//2022
**Midwest Computability Seminar, University of Chicago, Ryerson 352 (masks recommended indoors!)**

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

Brown bag lunch: in Ryerson 352 at noon

Speakers:- 1PM, Luca San Mauro,
Sapienza University of Roma, Italy

Title: Effectivizing the theory of Borel equivalence relations (video and slides)Abstract: The study of the complexity of equivalence relations has been a major thread of research in diverse areas of logic. In descriptive set theory, one investigates Borel reductions of equivalence relations on Polish spaces. In computability theory, one focuses on computable reductions of countable equivalence relations. Despite the clear analogy between the two notions, for a long time the study of Borel reducibility and the study of computable reducibility were conducted independently. Yet, a theory of computable reductions which blends ideas from both computability theory and descriptive set theory is rapidly emerging. In this talk, we will discuss differences and similarities between the Borel and the computable settings as we provide computable, or computably enumerable, analogs of fundamental concepts from the Borel theory. In particular, we concentrate on natural effectivizations of two classic concepts: orbit equivalence relations and the Friedman-Stanley jump. This is joint work with Uri Andrews.

- 2:30PM, Don Stull,
Northwestern University, Evanston, Illinois

Title: Pinned distance sets using effective dimension (video and slides)Abstract: Given a set E in the plane and a point x, the pinned distance set of E with respect to x is the set of distances between x and the points in E. Determining the Hausdorff dimension of pinned distance sets is a central open problem in geometric measure theory. In this talk, I will discuss how we can use effective methods to improve the bounds on the dimension of pinned distance sets.

- 4PM, Manlio
Valenti, UW

Title: The first-order part of computational problems (video and slides)Abstract: Given a partial order (P,≤), a natural strategy to prove that a ≤ b is to present an example of some c ≤ a such that c ≰ b. In general, finding such a c can be very challenging.In this talk, we will present a degree-theoretic operator on computational problems called "first-order part". This operator was introduced by Dzhafarov, Solomon, Yokoyama, and maps a multi-valued function f to 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. After a few examples, we will discuss some results on the algebraic properties of the first-order part, showing how they can simplify the characterization of the first-order part in many practical situations.

- 1PM, Luca San Mauro,
Sapienza University of Roma, Italy
- 11/15/2022 4PM,
Natasha Dobrinen, University of Notre Dame, Indiana

Title: Infinite-dimensional structural Ramsey theory (video and slides)Abstract: Infinite-dimensional Ramsey theory extends Ramsey’s Theorem for colorings of finite sets of natural numbers to colorings of infinite sets, i.e., points of the Baire space, [**N**]^{N}. A subset X of the Baire space is called Ramsey if given any infinite set N ⊆**N**, there is an infinite subset M ⊆ N such that the cube [M]^{N}is either contained in X or disjoint from X. The Galvin–Prikry Theorem states that Borel sets are Ramsey; Ellentuck’s Theorem extends this to sets with the property of Baire in the Ellentuck topology.The question of developing infinite-dimensional Ramsey theory for Fraïssé structures was raised in the 2005 paper of Kechris–Pestov–Todorcevic. We addressed this question for the Rado graph in 2019, proving Galvin–Prikry analogues. Recently we proved Galvin–Prikry and some Ellentuck analogues for the class of binary relational structures satisfying an amalgamation property called SDAP

^{+}; this work recovers exact big Ramsey degrees as a Nash-Williams corollary. In ongoing work with Zucker, we prove infinite-dimensional Ramsey theorems for binary relational structures with free amalgamation and finitely many forbidden substructures; e.g., k-clique-free Henson graphs.

Dinner: The Globe Restaurant (309 N. Henry St.) at 5:30PM (**Monday, Nov. 14th**) - 11/18/2022
(
**department colloquium**), 4PM in**room B239 Van Vleck**,

Jim Freitag, University of Illinois-Chicago

Title: When any three solutions are independent (video and slides)Abstract: In this talk, we'll talk about a surprising recent result about the algebraic relations between solutions of a differential equation. The result has applications to functional transcendence, diophantine geometry, and compact complex manifolds.

Lunch: Steenbock's on Orchard (330 N. Orchard St.) leaving from 2nd floor of Van Vleck at noon

Dinner: Cadre (2540 University Ave.) at 6PM - 11/29/2022 4PM,
Uri Andrews, UW

Title: Equivalence relations on ω under computable reductions: Low levels of the arithmetical hierarchy (video and slides)Abstract: We study equivalence relations on ω modulo computable reductions. That is, we say that E ≤ R if there is a total computable f so that xEy iff f(x)Rf(y). This is an old notion studied by Ershov and Lachlan in the 1970's, but has recently been revived. It has received a lot of attention lately with focus towards structural questions, and the topic has received new motivation coming from analogies with invariant descriptive set theory. I'll give a survey of what is known about this structure on the lowest levels of the arithmetical hierarchy. I'll try to point to open questions that are likely quite tractable and some (hopefully) deeper research directions. - 12/6/2022 4PM,
Don Stull,
Northwestern University, Evanston, Illinois

Title: Optimal oracles for point-to-set principles (video and slides)Abstract: The point-to-set principle of J. Lutz and N. Lutz characterizes the Hausdorff dimension of a set by the effective dimension of its points. Recent work has used this bridge to prove results in geometric measure theory using algorithmic techniques. One of the fundamental results of geometric measure theory is Marstrand's projection theorem. This theorem gives tight bounds on the size of the orthogonal projection of a set onto a line through the origin. Until recently, Marstrand's theorem was only known to hold for analytic sets. In this talk, we will discuss the notion of optimal oracles, which give the weakest known sufficient conditions for Marstrand's theorem to hold.

Dinner: TBA around 6PM - 12/13/2022 4PM,
Andrej Bauer, University of
Ljubljana, Slovenia

Title: Extended Weihrauch degrees (video and related paper)Abstract: Say that a predicate φ ranging over A is instance reducible to a predicate ψ ranging over B when ∀ x ∈ A ∃ y ∈ B (ψ(y) ⇒ φ(x)). This notion is ubiquitous in constructive mathematics, and is generally the usual way of showing that ∀ y ∈ B ψ(y) implies ∀ x ∈ A φ(x). Such predicates form a complete lattice with respect to instance reducibility, even a frame and therefore a Heyting algebra. Its structure is related to Smyth’s upper powerdomain.When instance reducibility is interpreted in the Kleene-Vesley realizability topos, it yields a proper generalization of the Weihrauch degrees, which I call the extended Weihrauch degrees. Apart from having a better order-theoretic structure than the Weihrauch degrees, the extended degrees offer a new and interesting notion of reduction that allows one to mix and combine uniform and non-uniform reducibility.