## UW Logic Seminar Schedule

This semester, our seminar will be in hybrid format: You will be able to attend in person in B115 Van Vleck Hall unless stated otherwise, or you can watch remotely using the information given below. Given the current pandemic conditions, face masks covering nose and mouth will be required for in-person attendance, and no eating in the seminar room will be allowed.

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

On alternate Mondays, we will join the biweekly virtual Midwest Computability Seminar (a joint seminar of the University of Wisconsin-Madison, the University of Chicago and the University of Notre Dame), with the following login information:

Zoom link to Midwest Computability Seminar
Meeting ID: 997 5433 2165
Passcode: midwest

Some of us will be watching the Midwest Computability Seminar in room B115 Van Vleck, so feel free to join us in person or remotely.

Fall 2021
• 9/13/2021 3:30PM (Midwest Computability Seminar), Rachael Alvir, University of Notre Dame, Indiana
Title: Finitely α-generated structures (video and slides)
Abstract: In this talk, we define the notion of a finitely $\alpha$-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.

• 9/13/2021 4PM (Midwest Computability Seminar), Josiah Jacobsen-Grocott, UW
Title: A characterization of the strongly η-representable many-one degrees (video and slides)
Abstract: η-representations are a way of coding sets in computable linear orders that were first introduced by Fellner in his thesis. Limitwise monotonic functions have been used to characterize the sets with η-representations and give characterizations for several variations of η-representations. The one exception is the class of sets with strong η-representations, the only class where the order type of the representation is unique. We introduce the notion of a a connected approximation of a set, a variation on Σ02-approximations. We use connected approximations to give a characterization of the many-one degrees of sets with strong η-representations as well as new characterizations of the variations of η-representations with known characterizations.

• 9/20/2021 3:30PM (local UW logic seminar), Josiah Jacobsen-Grocott, UW
Title: T2.5-classes of enumeration degrees which are not submetrizable
Abstract: A point in a represented second-countable T0-space can be identified with the set of basic open sets containing that point. Using this coding, we can consider the enumeration degrees of the points in a second-countable T0-space. For example, the ω-product of the Sierpiński space is universal for second-countable T0-spaces and gives us all enumeration degrees, and the Hilbert cube gives us all continuous degrees. A natural question to ask is whether topological separation axioms separate classes of degrees.

Kihara, Ng, and Pauly have studied various classes that arise from different spaces. They show that any enumeration degree is contained in a class arising from some computable, submetrizable space, and that no T1-space contains all enumeration degrees. Similarly, they separate T2-classes from T1-classes, and T2.5-classes from T2-classes. We give separations of the T2.5-classes from the submetrizable classes using the Arens co-d-CEA degrees and the Roy halfgraph above degrees.

• 9/27/2021 3:30PM (Midwest Computability Seminar), Benoît Monin, University of Paris-Est Créteil, France
Title: The computational content of Milliken’s tree theorem (video and slides)
Abstract: Milliken’s tree theorem is an extension of Ramsey’s theorem to trees. It implies, for instance, that if we assign to all the sets of two strings of the same length one among k colors, there is an infinite binary tree within which every pair of strings of the same length has the same color. We are going to present some results on Milliken’s tree theorem from the viewpoint of computability theory and reverse mathematics.

• 10/4/2021 3:30PM (local UW logic seminar), Jun Le Goh, UW
Title: Redundancy of information: Lowering effective dimension (related slides)
Abstract: The effective Hausdorff dimension of an infinite binary sequence can be characterized using the (normalized) Kolmogorov complexity of its initial segments (Mayordomo). It is invariant under changes on a set of positions of upper density 0. Greenberg, Miller, Shen, and Westrick initiated the study of how effective Hausdorff dimension can be changed if one is allowed to change a sequence on a set of positive upper density. Specifically, given some X of dimension t, what is the minimum density of changes needed to obtain some Y of dimension s? The situation differs depending on X, as well as the value of the target dimension s relative to the value of the starting dimension t. We present joint work with Miller, Soskova and Westrick on these questions.

• 10/11/2021 3:30PM (Midwest Computability Seminar), Vittorio Cipriani, University of Udine, Italy
Title: Cantor-Bendixson Theorem in the Weihrauch lattice (video and slides)
Abstract: In this talk we will study the Cantor-Bendixson theorem using the framework of Weihrauch reducibility. (Variations of) this theorem falls into the highest of the big-five axiom systems of reverse mathematics, namely, Π11-CA0. Kihara, Marcone and Pauly already showed that many problems representing principles equivalent to ATR0 lie in different Weihrauch degrees; for Π11-CA0, we actually have a natural candidate, namely, the one mapping a countable sequence of trees to the characteristic function of the set of indices corresponding to well-founded trees. This principle was first considered by Hirst, who also showed its Weihrauch equivalence with PKTr, the function that takes as input a tree and outputs its perfect kernel for trees. Even if in reverse mathematics it is actually equivalent to consider trees or closed sets, we will show that PKTr <W PKX, where PKX takes as input a closed set of a computable Polish space X and outputs its perfect kernel. The equivalence between these two shows up if we switch to arithmetical Weihrauch reducibility.

We will continue in this direction showing (non)reductions between problems related to the Cantor-Bendixson theorem with particular attention paid to classifying them for every computable Polish space X. This leads us to the result that, while PKX and wCBX (i.e., same as PKX but where the output also provides a listing of the elements in the scattered part) are equivalent for any space X that we consider, the problem CBX (i.e., same as wCBX but where the output provides also the cardinality of the scattered part) "almost" splits into two Weihrauch degrees, one having as representative PKX and the other having CBNN.

This is joint work with Alberto Marcone and Manlio Valenti.

• 10/11/2021 4PM (Midwest Computability Seminar), David Webb, University of Hawai'i-Mānoa
Title: Under what reducibilities are KLR and MLR Medvedev equivalent? (video and slides)
Abstract: Motivated by the observation that one half of a Kolmogorov-Loveland random is Martin-Löf random, we consider the problem of outputting (Martin-Löf) random bits given a pair of oracles, an unknown member of which is itself random. We show that a truth-table reduction can be used to do this so that KLR and MLR are truth-table Medvedev equivalent. We also investigate whether even stronger reducibilities can be used, obtaining negative results for linear, positive, and bounded truth-table reducibilities.

• 10/18/2021 3:30PM (local UW logic seminar), Steffen Lempp, UW
Title: The ∀∃-theory of the Σ02-enumeration degrees
Abstract: While the ∃-theory of the Σ02-enumeration degrees is easily seen to be decidable, and the ∃∀∃-theory of the Σ02-enumeration degrees was shown to be undecidable by Kent (2006), the decidability of the ∀∃-theory of the Σ02-enumeration degrees remains wide open.

We present a new result toward showing the decidability by proving that no so-called Ahmad triple can exist. At the end, we will sketch how this proof can be obtained by varying a direct proof of Ahmad (1990) that there is no symmetric Ahmad pair; on the other hand, we also show that our result cannot be strengthened to so-called weak Ahmad triples.

• 10/25/2021 3:30PM (Midwest Computability Seminar), Sarah Reitzes, University of Chicago, Illinois
Title: TBA
Abstract: TBA

• 10/25/2021 4PM (Midwest Computability Seminar), Diego Rojas, Iowa State University, Ames
Title: TBA
Abstract: TBA

• 11/1/2021 3:30PM (local UW logic seminar), Olivia Caramello, University of Insubria, Como, Italy; and University of Paris-Saclay, France
Title: TBA
Abstract: TBA

• 11/8/2021 3:30PM (Midwest Computability Seminar), Cristóbal Rojas, Pontifical Catholic University of Chile, Santiago
Title: TBA
Abstract: TBA

• 11/15/2021 3:30PM (local UW logic seminar), TBA
Title: TBA
Abstract: TBA

• 11/22/2021 3:30PM (Midwest Computability Seminar), Elvira Mayordomo, University of Zaragoza, Spain
Title: TBA
Abstract: TBA

• 11/29/2021 3:30PM (local UW logic seminar), Larry Moss, Indiana University, Bloomington
Title: TBA
Abstract: TBA

• 12/6/2021 3:30PM (Midwest Computability Seminar), Francesca Zaffora Blando, Carnegie Mellon University, Pittsburgh, Pennsylvania
Title: TBA
Abstract: TBA

• 12/13/2021 3:30PM (local UW logic seminar), Iian Smythe, University of Michigan, Ann Arbor
Title: TBA
Abstract: TBA

Archived UW Logic Seminar Pages