- 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 Σ^{0}_{2}-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: T_{2.5}-classes of enumeration degrees which are not submetrizableAbstract: A point in a represented second-countable T_{0}-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 T_{0}-space. For example, the ω-product of the Sierpiński space is universal for second-countable T_{0}-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 T

_{1}-space contains all enumeration degrees. Similarly, they separate T_{2}-classes from T_{1}-classes, and T_{2.5}-classes from T_{2}-classes. We give separations of the T_{2.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, Π^{1}_{1}-CA_{0}. Kihara, Marcone and Pauly already showed that many problems representing principles equivalent to ATR_{0}lie in different Weihrauch degrees; for Π^{1}_{1}-CA_{0}, 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 PK_{Tr}, 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 PK_{Tr}<_{W}PK_{X}, where PK_{X}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 PK

_{X}and wCB_{X}(i.e., same as PK_{X}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 CB_{X}(i.e., same as wCB_{X}but where the output provides also the cardinality of the scattered part) "almost" splits into two Weihrauch degrees, one having as representative PK_{X}and the other having CB_{NN}.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 Σ^{0}_{2}-enumeration degrees (video)Abstract: While the ∃-theory of the Σ^{0}_{2}-enumeration degrees is easily seen to be decidable, and the ∃∀∃-theory of the Σ^{0}_{2}-enumeration degrees was shown to be undecidable by Kent (2006), the decidability of the ∀∃-theory of the Σ^{0}_{2}-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: Comparing induction and bounding principles over RCA_{0}and RCA^{*}_{0}(video and slides)Abstract: In this talk, I will discuss joint work with Damir D. Dzhafarov and Denis R. Hirschfeldt, and more recent work following that line of research.Our work centers on the characterization of reductions between Π

^{1}_{2}-problems P and Q in terms of winning strategies in certain games. These characterizations were originally introduced by Hirschfeldt and Jockusch in [1]. I will discuss extensions and generalizations of these characterizations, including a certain notion of compactness that allows us, for strategies satisfying particular conditions, to bound the number of moves it takes to win. This bound is independent of the instance of the problem P being considered. This allows us to develop the idea of Weihrauch and generalized Weihrauch reductions over some base theory. Here, we will focus on the base theory RCA_{0}and the weaker system RCA^{*}_{0}. In this talk, I will explore these notions of reductions among various principles, including bounding and induction principles. I will present a metatheorem that allows us to obtain many nonreductions between these principles.[1] D. R. Hirschfeldt and C. G. Jockusch, Jr.: On notions of computability-theoretic reduction between Π

^{1}_{2}-principles. Journal of Mathematical Logic 16 (1650002), 59 pp. (2016) - 10/25/2021 4PM
(Midwest Computability Seminar),
Diego Rojas, Iowa State University, Ames

Title: Effective convergence notions for measures on the real line (video and slides)Abstract: In classical measure theory, there are two primary convergence notions studied for sequences of measures: weak and vague convergence. In this talk, we discuss a framework to study the effective theory of weak and vague convergence of measures on the real line. For effective weak convergence, we give an effective version of a characterization theorem for weak convergence called the Portmanteau Theorem. We also discuss the relationship between effective weak convergence and the structure of the space of finite Borel measures on the real line as a computable metric space. In contrast to effective weak convergence, we give an example of an effectively vaguely convergent sequence of measures that has an incomputable limit. Nevertheless, we discuss the conditions for which the limit of an effectively vaguely convergent sequence is computable and the conditions for which effective weak and vague convergence of measures coincide. This talk will feature joint work with Timothy McNicholl. - 11/1/2021 3:30PM (local UW logic seminar),
Olivia Caramello,
University of Insubria, Como, Italy; and University of Paris-Saclay, France

Title: Relative topos theory via stacks (video and slides)Abstract: In this talk, based on joint work with Riccardo Zanfa, we shall introduce new foundations for relative topos theory based on stacks. One of the central results in our theory is an adjunction between the category of (relatively small) toposes over the topos of sheaves on a given site (C, J) and that of C-indexed categories. This represents a wide generalization of the classical adjunction between presheaves on a topological space and bundles over it, and allows one to interpret several constructions on sheaves and stacks in a geometrical way; in particular, it leads to fibrational descriptions of direct and inverse images of sheaves and stacks, as well as to a geometric understanding of the sheafification process. It also naturally allows one to regard any Grothendieck topos as a ‘petit’ topos associated with a ‘gros’ topos, thereby providing an answer to a problem posed by Grothendieck in the seventies. - 11/8/2021 3:30PM
(Midwest Computability Seminar),
Cristóbal Rojas, Pontifical Catholic University of Chile,
Santiago

Title: Computability of harmonic measure (video and slides)Abstract: We will review recent results relating the geometry of a connected domain to the computability of its harmonic measure at a given point x. In particular, we will discuss examples of domains whose harmonic measure at x is always computable relative to x, but not uniformly. As a by-product, this construction produces "natural" examples of harmonic functions arising as solutions to a Dirichlet problem which are piecewise computable (i.e., all their values are computable relative to the input point), but not computable. This is a work in collaboration with I. Binder, A. Glucksam and M. Yampolsky. - 11/15/2021 3:30PM: no seminar due to Dagstuhl workshop
- 11/22/2021 3:30PM
(Midwest Computability Seminar),
Elvira Mayordomo,
University of Zaragoza, Spain

Title: Extending the reach of the point-to-set principle (video and slides)Abstract: The point-to-set principle of J. Lutz and N. Lutz (2018) has recently enabled the theory of computing to be used to answer open questions about fractal geometry in Euclidean spaces**R**^{n}. These are classical questions whose statements do not involve computation or related aspects of logic.I will present the generalization of the point-to-set principle from Euclidean spaces to arbitrary separable metric spaces and to a large class of gauge families.

Then I will demonstrate the power of our extended point-to-set principle by using it to prove new theorems about classical fractal dimensions in hyperspaces.

(The results presented are joint work with Jack Lutz and Neil Lutz).

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

Title: Coalgebras and corecursive algebras in continuous mathematics (video and slides)Abstract: A slogan from coalgebra in the 1990's holds that'discrete mathematics : algebra :: continuous mathematics : coalgebra' The idea is that objects in continuous math, like real numbers, are often understood via their approximations, and coalgebra gives tools for understanding and working with those objects. Some examples of this are (1) Pavlovic and Escardo's relation of ordinary differential equations with coinduction, and (2) Freyd's formulation of the unit interval [0,1] as a final coalgebra. My talk will be an organized survey of these and other results in this area, including a new proof of (2) with extensions to fractal sets; (3) other presentations of sets of reals as corecursive algebras and final coalgebras; (4) a coinductive proof of the correctness of policy iteration from Markov decision processes; and (5) final coalgebra presentations of universal Harsanyi type spaces from economics.This talk is aimed at a general audience of mathematical logicians. You don't need to know what most of the terms in the last paragraph mean. It would be good to know the basics of category theory, including examples of functors from the category of sets to itself. To get the most out of it, it might be good to look up the connection of definition by recursion on the natural numbers with initial algebras of the functor 1 + X on Set.

This talk reports on joint work with several groups in the past 5-10 years.

- 11/30/2021
**4PM**(local UW logic seminar), Martino Lupini, Victoria University of Wellington, New Zealand

Title: The classification problem for extensions of countable torsion abelian groups (video and (partial) slides)Abstract: Given two countable abelian groups A and B, the group Ext(A,B) comprises the isomorphism classes of extensions of A by B. How difficult is it to check whether two such extensions are isomorphic? In this talk, I will present a result that, in the torsion case, completely characterizes the Borel complexity class of such a classification problem in terms of A and B. In particular, this result shows that the complexity of such a problem can be arbitrarily high in the Borel hierarchy. - 12/3/2021
**4PM**(**department colloquium in room B239 and Zoom**), Martino Lupini, Victoria University of Wellington, New Zealand

Title: Borel-definable algebraic topology (video and slides)Abstract: In this talk, I will explain how ideas and methods from logic can be used to obtain refinements of classical invariants from homological algebra and algebraic topology. I will then present some applications to classification problems in topology. This is joint work with Jeffrey Bergfalk and Aristotelis Panagiotopoulos. - 12/6/2021 3:30PM
(Midwest Computability Seminar),
Francesca Zaffora Blando, Carnegie Mellon University,
Pittsburgh, Pennsylvania

Title: Algorithmic randomness and Bayesian convergence (video and slides)Abstract: Much recent work in algorithmic randomness has concerned characterizations of randomness notions in terms of effectivizations of almost-everywhere convergence theorems in analysis and probability theory. In this talk, I will consider some results that are part of the basic toolkit of Bayesian epistemologists from this perspective. In particular, I will focus on certain martingale convergence theorems that form one of the cornerstones of Bayesian epistemology and that fall under the general umbrella of "Bayesian convergence-to-the-truth results". These results are standardly taken to establish that a Bayesian agent’s beliefs are guaranteed to converge to the truth with probability one as the evidence accumulates. We will see that, for computable Bayesian agents (i.e., Bayesian agents with computable priors), we not only have that convergence to the truth occurs with probability one, but we can also provide precise characterizations of the data streams along which beliefs converge to the truth: they are precisely the algorithmically random data streams. I will conclude by sketching a broader computability-theoretic approach to Bayesian epistemology suggested by these results.This is joint work with Simon Huttegger and Sean Walsh.

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

Title: Parametrizing the Ramsey theory of vector spaces (video and slides)Abstract: In the late 1990's, Gowers proved a Ramsey-theoretic dichotomy for subspaces of infinite-dimensional Banach spaces. The combinatorial essence of this result was later extracted by Rosendal in the setting of discrete vector spaces. Both dichotomies say, roughly, that given an analytic partition of the set of infinite block sequences of vectors, there is an infinite-dimensional subspace with a wealth of block sequences entirely contained in, or disjoint from, one piece of the partition. We will describe a new "parametrized" form of Rosendal's dichotomy: Given an analytic family of partitions indexed by the reals, there is a single subspace which witnesses Rosendal's dichotomy for uncountably many of the partitions, simultaneously. An integral part of our proof is the preservation of certain analogues of selective ultrafilters, by Sacks forcing. We will also discuss applications to families of linear transformations. - 12/15/2021 3:30PM (local UW logic seminar,
**room 901 Van Vleck**), Linda Westrick, Pennsylvania State University, University Park

Title: Existential and universal definitions in algebraic extensions of the rationals (video and slides)Abstract: The set of algebraic extensions of**Q**admits a natural topology. We show that with respect to this topology, the set of fields which have a universally definable ring of integers is meager, as is the set of fields which have an existentially definable ring of integers. The result holds more generally if the integers are replaced by any set whose intersection with**Q**is neither thin nor co-thin in**Q**. The main tools are Hilbert's Irreducibility Theorem and a new normal form theorem for Σ^{0}_{1}-definitions. The normal form theorem, which may be of independent interest, says roughly that every Σ^{0}_{1}-definable subset of an algebraic extension of**Q**is a finite union of single points and hypersurfaces defined by an absolutely irreducible polynomial. Joint work with Kirsten Eisenträger, Russell Miller and Caleb Springer.

- 1/24/2022 3:30PM
(Midwest Computability Seminar),
Don Stull,
Northwestern University, Evanston, Illinois

Title: The dimension spectrum conjecture for lines (video and slides)Abstract: Effective dimension gives a fine-grained measure of randomness of individual points in Euclidean space. Let L be a line in the Euclidean plane.The dimension spectrum sp(L) is the set of all effective dimensions of individual points on L. Jack Lutz, in the early 2000s, posed the dimension spectrum conjecture. This conjecture states that, for every line L, sp(L) contains a unit interval. In this talk, we present a proof of the dimension spectrum conjecture. We also discuss its relation to open problems in geometric measure theory, and avenues for future research.

- 1/31/2022 3:30PM
(local UW logic seminar),
Uri Andrews,
UW

Title: The computable Friedman-Stanley jumpAbstract: In 1989, Friedman and Stanley introduced a jump operator on the space of equivalence relations on standard Borel spaces. Recently, Clemens, Coskey, and Krakoff introduced a computable version of this for equivalence relations on ω. The classical Friedman-Stanley jump is proper for Borel equivalence relations and gives benchmark equivalence relations for the Borel S_{∞}-orbit equivalence relations. In the computable reducibility setting, the computable Friedman-Stanley jump is proper for HYP equivalence relations and gives benchmark equivalence relations going up the HYP hierarchy. I may also talk about the highness hierarchy for this jump on the local structure of c.e. equivalence relations. All original work is joint with Luca San Mauro, and some of the talk will be based on Clemens, Coskey, and Krakoff's recent paper (https://arxiv.org/pdf/2005.13777.pdf). - 2/7/2022 3:30PM
(Midwest Computability Seminar),
Matthew
Harrison-Trainor, University of Michigan, Ann Arbor

Title: Kolmogorov extractors and evenly-distributed hypergraphs (video and slides)Abstract: Suppose that we have a string which has some amount of randomness and we want to produce from it, in an effective way, a string which is more random. Though we cannot do this, it is possible to produce two strings, at least one of which is more random than the original string. Moreover, the more strings we are allowed to produce, the more we can increase the randomness. How much can we increase the randomness, and how many strings are required? This question turns out to be related to a purely graph-theoretic question about how evenly the edges of a hypergraph can be distributed. - 2/11/2022 4PM
(UW Math Department Colloquium in
**room B239**), Mariya Soskova, UW

Title: The e-verse (slides)Abstract: Computability theory studies the relative algorithmic complexity of sets of natural numbers and other mathematical objects. Turing reducibility and the induced partial order of the Turing degrees serve as the well-established model of relative computability. Enumeration reducibility captures another natural relationship between sets of natural numbers in which positive information about the first set is used to produce positive information about the second set. The induced structure of the enumeration degrees can be viewed as an extension of the Turing degrees, as there is a natural way to embed the second partial order in the first. In certain cases, the enumeration degrees can be used to capture the algorithmic content of mathematical objects, while the Turing degrees fail. Certain open problems in degree theory present as more approachable in the extended context of the enumeration degrees, e.g., first order definability. We have been working to develop a richer “e-verse”: a system of classes of enumeration degrees with interesting properties and relationships, in order to better understand the enumeration degrees. I will outline several research directions in this context. - 2/14/2022 3:30PM
(local UW logic seminar),
Alexandra
Soskova, University of Sofia, Bulgaria

Title: Cohesive powers of linear orders (video and slides)Abstract:*Cohesive powers*of computable structures are effective analogs of ultrapowers, where cohesive sets play the role of ultralters. The aim is also to compare and contrast properties of cohesive powers with those of classical ultrapowers. Classically, an ultrapower of a structure is elementarily equivalent to the base structure by Łoś's theorem. Effectively, Łoś's theorem holds for cohesive powers of decidable structures. For cohesive powers of n-decidable structures, Łoś's theorem needs to only hold up to Δ^{0}_{n+3}-expressible sentences. In fact, every Σ^{0}_{n+3}-sentence true of an n-decidable structure is also true of all of its cohesive powers, but this is optimal in general. Classically, ultrapowers of isomorphic structures over a fixed ultrafilter are isomorphic. Effectively, cohesive powers of computably isomorphic computable structures over a fixed cohesive set are isomorphic. However, it is possible for isomorphic (but not computably isomorphic) computable structures to have non-elementarily equivalent (hence non-isomorphic) cohesive powers. Classically, the Keisler-Shelah theorem states that two structures are elementarily equivalent if and only if there is an ultrafilter over which the corresponding ultrapowers are isomorphic. Effectively, an analogous result holds for decidable structures. If the structures are computable but not necessarily decidable, then the effective version of the Keisler-Shelah theorem can fail in either direction. Classically, for a countable language, ultrapowers over countably incomplete ultrafilters are ℵ_{1}-saturated. Effectively, cohesive powers of decidable structures are recursively saturated. Furthermore, cohesive powers of n-decidable structures are Σ^{0}_{n}-recursively saturated. Most interestingly, if the cohesive set is assumed to be co-c.e., then we obtain an additional level of saturation: Cohesive powers of n-decidable structures over co-c.e. cohesive sets are Σ^{0}_{n+1}-recursively saturated.We investigate the cohesive powers of computable linear orders, with special emphasis on computable copies of ω. If L is a computable copy of ω that is computably isomorphic to the standard presentation of ω, then every cohesive power of L has order-type ω+ζη. However, there are computable copies of ω, necessarily not computably isomorphic to the standard presentation, having cohesive powers not elementarily equivalent to ω+ζη. For example, we show that there is a computable copy of ω with a cohesive power of order-type ω+η. Our most general result is that if X ⊆ N-{0} is a Boolean combination of Σ

^{0}_{2}-sets, thought of as a set of finite order-types, then there is a computable copy of ω with a cohesive power of order-type ω+σ(X ∪ {ω+ζη+ω^{*}}), where σ(X ∪ {ω+ζη+ω^{*}}) denotes the shuffle sum of the order-types in X and the order-type ω+ζη+ω^{*}. Furthermore, if X is finite and non-empty, then there is a computable copy of ω with a cohesive power of order-type ω+σ(X).This is a joint work with Rumen Dimitrov, Valentina Harizanov, Andrey Morozov, Paul Shafer and Stefan Vatev.

It was partially supported by Bulgarian National Science Fund KP-06-Austria-04/06.08.2019, FNI-SU 80-10-136/26.03.2021.

- 2/21/2022 3:30PM
(Midwest Computability Seminar),
Katia Fokina,
Vienna University of Technology, Austria

Title: Algorithmic learning of structures (video and slides)Abstract: Assume we have a class of structures closed under isomorphism. Assume further, we receive information about one of these structures step by step: finitely much information at each step. Our goal is to determine, after finitely many steps, which structure from the class we are observing. If we can reach the goal, we call the class learnable. In the talk we formalise various aspects of this problem using ideas from computable structure theory and computational learning theory. We give syntactic characterisations for several notions of learnability and apply these results to get examples of learnable and non-learnable classes of structures. - 2/28/2022 3:30PM (local UW logic seminar),
Josiah
Jacobsen-Grocott, UW

Title: The failure of Selman's Theorem for hyperenumeration reducibility (specialty exam) (video and slides)Abstract: Hyperenumeration reducibility was first introduced by Sanchis. The relationship between hyperenumeration and hyperarithmetic reducibility shares many parallels with the relationship between enumeration and Turning reducibility. We ask if this relationship can be pushed to prove an analog of Selman's Theorem for hyperenumeration reducibility. By studying e-pointed trees in Baire space, we are able to get a counterexample. - 3/7/2022 3:30PM: no seminar due to Luminy workshop
- 3/21/2022 3:30PM
(Midwest Computability Seminar),
Meng-Che
"Turbo" Ho, California State University Northridge

Title: Zero-one laws for finitely presented structures (video and slides)Abstract: Gromov proposed the notion of random groups as a model to study the typical behavior of finitely presented groups. They share many properties of the free group, and Knight conjectured that random groups satisfy the zero-one law and have the same first-order theory as the free group. In this joint work with Franklin and Knight, we study this zero-one law in other classes of structures. In particular, we consider random presentations in algebraic varieties in the sense of universal algebra. We will discuss some examples where the zero-one law holds and some other examples where the zero-one law fails. We also establish some general conditions for the zero-one law to hold (or fail). - 3/28/2022 3:30PM
(local UW logic seminar),
Rod Downey,
Victoria University of Wellington, New Zealand

Title: Notes on the Sacks Splitting Theorem (video and slides)Abstract: We explore the complexity of the Sacks Splitting Theorem in terms of the mind change functions associated with the members of the splits. We prove that, for any c.e. set A, there are low computably enumerable sets A_{0}⊔ A_{1}= A splitting A with A_{0}and A_{1}both totally ω^{2}-c.a. in terms of the Downey-Greenberg hierarchy. We also show that if upper cone avoidance is added then there is no level below ε_{0}which can be used to characterize the complexity of A_{0}and A_{1}.Joint work with Klaus Ambos-Spies, Martin Monath and Keng Meng Ng.

- 4/4/2022 3:30PM
(Midwest Computability Seminar),
Jun Le Goh, UW

Title: Extensions of embeddings in the Σ^{0}_{2}-enumeration degrees (video and slides)Abstract: In order to measure the algorithmic content of partial functions, or the positive information content of subsets of the natural numbers, one can use the notion of enumeration reducibility. The associated degree structure, known as the enumeration degrees (e-degrees), forms a superstructure of the Turing degrees. We present ongoing work with Steffen Lempp, Keng Meng Ng and Mariya Soskova on the algebraic properties of a countable substructure of the e-degrees, namely the Σ^{0}_{2}-enumeration degrees.The Σ

^{0}_{2}-enumeration degrees are analogous to the computably enumerable (c.e.) Turing degrees, but these structures are not elementarily equivalent as partial orders. Indeed, Ahmad showed that there are incomparable Σ^{0}_{2}-enumeration degrees a and b such that if c < a, then c < b, implying that a cannot be expressed as the join of two degrees below it. This stands in contrast to the Sacks Splitting Theorem for the c.e. Turing degrees.One can view Ahmad's result as a two-quantifier sentence in the language of partial orders which holds in the Σ

^{0}_{2}-enumeration degrees. While it is easy to compute whether a given one-quantifier sentence is true in the Σ^{0}_{2}-enumeration degrees (because all finite partial orders embed), the corresponding task for two-quantifier sentences (which corresponds to an extension of embeddings problem) is not known to be algorithmically decidable. Towards solving this problem, we investigate the extent to which Ahmad's result can be generalized. For instance, we show that it does not generalize to triples: For any incomparable Σ^{0}_{2}-enumeration degrees a, b and c, there is some x such that one of the following holds: x is below a but not below b, or x is below b but not below c.We shall also discuss speculative generalizations of the above result, and how they may lead to an algorithm which decides a class of two-quantifier sentences in the Σ

^{0}_{2}-enumeration degrees. - 4/11/2022 3:30PM
(local UW logic seminar),
Ted Slaman,
University of California-Berkeley

Title: Computability Theory, Set Theory and Geometric Measure Theory (video and slides)Abstract: We will explore issues of Geometric Measure Theory using methods from Computability Theory and Set Theory. We will not assume any prior knowledge of these areas. - 4/18/2022 3:30PM
(Midwest Computability Seminar),
Jeff Hirst,
Appalachian State University, Boone, North Carolina

Title: Three views of LPO and LLPO (video and slides)Abstract: The Limited Principle of Omniscience (LPO) and Lesser Limited Principle of Omniscience (LLPO) are frequently included in discussions of constructive mathematics. We will compare and contrast the principles using ideas from Weihrauch reducibility, reverse mathematics, and higher order reverse mathematics. The preliminary results in higher order reverse mathematics are joint work with Carl Mummert. - 4/25/2022 3:30PM
(local UW logic seminar),
Randall Holmes,
Boise State University, Idaho

Title: Prefatory material to a proof of Con(NF) (video and slides)Abstract: We will present preliminary definitions and results which should suggest the nature of the author’s claimed and not very approachable proof of the consistency of Quine’s “New Foundations”. This will include basic definitions, and indication of the fundamental results obtained by Specker, Jensen’s proof of the consistency of the related theory NFU, and the results of the author (1995) on equiconsistency of NF with “tangled type theory”, followed by a mere sketch of the strategy of a version of the proof the author has claimed since 2010. - 5/2/2022 3:30PM
(local UW logic seminar),
Uri Andrews,
UW

Title: My favorite theorem (video and slides)Abstract: I will take you on a journey involving overspill in models of arithmetic, the (non)-solution of Hilbert's 10th problem, model-theoretic homogeneity, and some computable model theory, all to prove my favorite theorem, which seemingly has nothing to do with any of these topics.The theorem is due to David Marker building on work by Scott, Tennenbaum, Matiyasevich, Solovay, Goncharov, and Peretyatkin. I promise no original results.

- 5/24/2022 3:30PM
(local UW logic seminar, online only),
Dilip Raghavan,
National University of Singapore

Title: Galvin's problem in higher dimensions (slides)Abstract: I will discuss Galvin's conjecture on Ramsey-theoretic properties of the topological space of the rationals within various different classes of spaces. The behavior in dimension 2 is quite different from the behavior in higher dimensions. Large cardinals imply a positive solution to Galvin's conjecture in dimension 2 within a nearly optimal class of spaces. In higher dimensions, there are counterexamples. I will provide the necessary background and focus on the recent counterexamples in higher dimensions.