Two particularly popular, completely virtual logic seminars:

- Online Logic Seminar organized by Wesley Calvert,
- Computability Theory and Applications Online Seminar organized by Brattka, Dzhafarov, Fokina, Greenberg, Kihara, Patey, Pauly and Westrick.

The regular "virtual" meeting time is Mondays at 3:30PM (Central Time) during the spring semester 2021 (joining the Midwest Computability Seminar) roughly every other week, and with some joint meetings Tuesdays at 4PM (Central Time) with the Midwest Model Theory Seminar).

The **recurring Zoom link for the Midwest Computability Seminar** is:

https://notredame.zoom.us/j/99754332165?pwd=RytjK1RFZU5KWnZxZ3VFK0g4YTMyQT09

Meeting ID: 997 5433 2165, Passcode: midwest

The **recurring Webex link for the Midwest Model
Theory Seminar** is:

Meeting number: 126 507 5533, Password: (stable, but ask me if you don't have it, it is different from the password in fall 2020!)

The **recurring Zoom link for the local UW logic seminar** is:

https://uwmadison.zoom.us/j/99860137362?pwd=RzRIRlY3QmJGTklBK3EvWkZ5dTladz09

Meeting ID: 998 6013 7362, Passcode: 247845

(You need to log into your (personal or institutional) Zoom before you can join the local seminar.)

- 1/25/2021
**1PM**(local UW logic seminar), Joel David Hamkins, University of Oxford, England

Title: Can there be natural instances of nonlinearity in the hierarchy of consistency strength? (video and slides)Abstract: It is a mystery often mentioned in the foundations of mathematics that our best and strongest mathematical theories seem to be linearly ordered and indeed well-ordered by consistency strength. Given any two of the familiar large cardinal hypotheses, for example, generally one of them proves the consistency of the other. Why should this be? The phenomenon is seen as significant for the philosophy of mathematics, perhaps pointing us toward the ultimately correct mathematical theories. And yet, we know as a purely formal matter that the hierarchy of consistency strength is not well-ordered. It is ill-founded, densely ordered, and nonlinear. The statements usually used to illustrate these features are often dismissed as unnatural or as Gödelian trickery. In this talk, I aim to overcome that criticism — as well as I am able to — by presenting a variety of natural hypotheses that reveal ill-foundedness in consistency strength, density in the hierarchy of consistency strength, and incomparability in consistency strength.The talk should be generally accessible to university logic students, requiring little beyond familiarity with the incompleteness theorem and some elementary ideas from computability theory.

Discussion and commentary can be made on the speaker's web site at http://jdh.hamkins.org/natural-instances-of-nonlinearity-in-the-hierarchy-of-consistency-strength-uwm-logic-seminar-january-2021/.

- 1/26/2021
**4PM**(Midwest Model Theory Seminar), Gabe Conant, University of Cambridge, England

Title: NIP approximate groups and arithmetic regularityAbstract: I will speak about joint work with Anand Pillay on the structure of finite approximate groups satisfying a local NIP assumption. Our results can be seen as a unification of the model-theoretic study of "tame" arithmetic regularity with work of Hrushovski and Breuillard, Green, and Tao on the structure theory of approximate groups. - 2/1/2021 3:30PM (Midwest Computability Seminar),
Arno Pauly,
Swansea University, Wales

Title: The structure of Weihrauch degrees - what we know and what we don't know (video and slides)Abstract: The Weihrauch degrees are a popular setting for classifying the computational content of mathematical theorems. Understanding their structure is useful as a technical tool in concrete classifications. Moreover, their structure tells us something about how degrees of non-computability look like in principle. In this talk, I'll summarize what is already known about the structure of the Weihrauch degrees, and try to draw attention to some open problems. For example, we know that they form a distributive lattice, which is not a Heyting algebra and which is not complete. We have further natural algebraic operations, and we know of a few that they are definable in terms of others. The Medvedev degrees embed into the Weihrauch degrees as a lattice, as do the many-one degrees (but in a weird way). - 2/8/2021 3:30PM (local UW logic seminar),
Andrej Bauer,
University of Ljubljana, Slovenia

Title: Synthetic mathematics with an excursion into computability theory (video and slides)Abstract: According to Felix Klein, “synthetic geometry is that which studies figures as such, without recourse to formulae, whereas analytic geometry consistently makes use of such formulae as can be written down after the adoption of an appropriate system of coordinates”. To put it less eloquently, the synthetic method axiomatizes geometry directly by construing points and lines as primitive notions, whereas the analytic method builds a model, the Euclidean plane, from the real numbers.Do other branches of mathematics posses the synthetic method, too? For instance, what would “synthetic topology” look like? To build spaces out of sets, as topologists usually do, is the analytic way. The synthetic approach must construe spaces as primitive and axiomatize them directly, without any recourse to sets. It cannot introduce continuity as a desirable property of functions, for that would be like identifying straight lines as the non-bending curves.

It is indeed possible to build the synthetic worlds of topology, smooth analysis, measure theory, and computability. In each of them, the basic structure – topological, smooth, measurable, computable – is implicit by virtue of permeating everything, even logic itself. The synthetic worlds demand an economy of thought that the unaccustomed mind finds frustrating at first, but eventually rewards it with new elegance and conceptual clarity. The synthetic method is still fruitfully related to the analytic method by interpretation of the former in models provided by the latter.

We demonstrate the approach by taking a closer look at synthetic computability, whose central axiom states that there are countably many countable subsets of the natural numbers. The axiom is validated and explained by its interpretation in the effective topos, where it corresponds to the familiar fact that the computably enumerable sets may be computably enumerated. Classic theorems of computability may be proved in a straightforward manner, without reference to any notion of computation. We end by showing that in synthetic computability, Turing reducibility is expressed in terms of sequential continuity of maps between directed-complete partial orders.

- 2/9/2021
**4PM**(Midwest Model Theory Seminar), Rizos Sklinos, Stevens Institute of Technology, Hoboken, New Jersey

Title: Fields interpretable in the free groupAbstract: In this talk I will show that no infinite field is interpretable in the first-order theory of nonabelian free groups. - 2/15/2021 3:30PM (Midwest Computability Seminar),
Verónica
Becher, University of Buenos Aires, Argentina

Title: Normal numbers and perfect necklaces (video and slides)Abstract: The most famous example of a normal number is Champernowne's constant 0.123456789101112… Although the definition is very simple, the original proof of normality requires quite some work. In this talk, I present "perfect necklaces", a combinatorial object that yields a simple proof of Champernowne's normality result. And with a class of them, the "nested perfect necklaces", I explain M. Levin's constant, the number with the fastest known speed of convergence to normality. - 2/22/2021 3:30PM (local UW logic seminar),
José ("Goyo") Mijares,
California State University-Los Angeles

Title: Coideals and the Local Ramsey Property (video and slides)Abstract: We will talk about characterizations of the local Ramsey property relative to several types of coideal; in different contexts, including infinite games, block sequences of vectors and topological Ramsey spaces. - 2/23/2021
**4PM**(Midwest Model Theory Seminar), Leonardo Nagami Coregliano, University of Chicago, Illinois

Title: Continuous combinatorics and natural quasirandomnessAbstract: The theory of graph quasirandomness studies several asymptotic properties of the random graph that are equivalent when stated as properties of a deterministic graph sequence and was one of the main motivations for the theory of dense graph limits, also known as theory of graphons. Since the theory of graphons can itself be used to study graph quasirandomness and can be generalized to a theory of dense limits of models of a universal first-order theory, a natural question is whether a general theory of quasirandomness is possible.In this talk, I will briefly introduce the general theory of dense limits of combinatorial objects (often associated with the name continuous combinatorics) and talk about the notion of natural quasirandomness, a generalization of quasirandomness to the same general setting of universal first-order theories. The main concept explored by our quasirandomness properties is that of unique coupleability that roughly means that any alignment of two limit objects on the same ground set "looks random".

This talk is based on joint work with Alexander A. Razborov.

- 3/1/2021 3:30PM (Midwest Computability Seminar),
Kirsten
Eisenträger, Pennsylvania State University, University Park

Title: A topological approach to undefinability in algebraic extensions of the rationals (video)Abstract: In 1970, Matiyasevich proved that Hilbert’s Tenth Problem over the integers is undecidable, building on work by Davis-Putnam-Robinson. Hilbert’s Tenth Problem over the rationals is still open, but it could be resolved by giving an existential definition of the integers inside the rationals. Proving whether such a definition exists is still out of reach. However, we will show that only “very few” algebraic extensions of the rationals have the property that their ring of integers are existentially or universally definable. Equipping the set of all algebraic extensions of the rationals with a natural topology, we show that only a meager subset has this property. An important tool is a new normal form theorem for existential definitions in such extensions. As a corollary, we construct countably many distinct computable algebraic extensions whose rings of integers are neither existentially nor universally definable. Joint work with Russell Miller, Caleb Springer, and Linda Westrick. - 3/8/2021 3:30PM (local UW logic seminar),
Daniel Erman, UW

Title: Ultraproducts in commutative algebraAbstract: I’ll explain how an ultraproduct of polynomial rings in an unbounded number of variables turns out to be surprising, and how this was used to answer some old questions in commutative algebra. This is joint work with Steven Sam and Andrew Snowden. - 3/9/2021
**4PM**(Midwest Model Theory Seminar), Natasha Dobrinen, University of Denver, Colorado

Title: TBAAbstract: TBA - 3/15/2021 3:30PM (Midwest Computability Seminar),
Chris Conidis, City University of New York-College of Staten
Island

Title: TBAAbstract: TBA - 3/22/2021 3:30PM (local UW logic seminar),
Dana
Bartošová, University of Florida, Gainesville

Title: TBAAbstract: TBA - 3/29/2021 3:30PM (local UW logic seminar),
Andy Zucker,
University of California-San Diego

Title: TBAAbstract: TBA - 4/5/2021 3:30PM (Midwest Computability Seminar),
Julia
Knight, University of Notre Dame, Indiana

Title: TBAAbstract: TBA - 4/12/2021 3:30PM (local UW logic seminar),
Mike Shulman,
University of San Diego, California

Title: TBAAbstract: TBA - 4/19/2021 3:30PM (Midwest Computability Seminar),
Noam
Greenberg, Victoria University of Wellington, New Zealand

Title: TBAAbstract: TBA - 4/20/2021
**4PM**(Midwest Model Theory Seminar), Omer Mermelstein, UW

Title: TBAAbstract: TBA - 5/3/2021 3:30PM (Midwest Computability Seminar),
André
Nies, University of Auckland, New Zealand

Title: TBAAbstract: TBA

- 8/18/2020 3PM (Midwest Computability Seminar),
Joe Miller,
UW

Title: Redundancy of information: lowering effective dimension (video and slides)Abstract: A natural way to measure the similarity between two infinite binary sequences X and Y is to take the (upper) density of their symmetric difference. This is the Besicovitch distance on Cantor space. If d(X,Y) = 0, then we say that X and Y are coarsely equivalent. Greenberg, Miller, Shen, and Westrick (2018) proved that a binary sequence has effective (Hausdorff) dimension 1 if and only if it is coarsely equivalent to a Martin-Löf random sequence. They went on to determine the best and worst cases for the distance from a dimension t sequence to the nearest dimension s>t sequence. Thus, the difficulty of increasing dimension is understood.Greenberg et al. also determined the distance from a dimension 1 sequence to the nearest dimension t sequence. But they left open the general problem of reducing dimension, which is made difficult by the fact that the information in a dimension s sequence can be coded (at least somewhat) redundantly. Goh, Miller, Soskova, and Westrick recently gave a complete solution.

I will talk about both the results in the 2018 paper and the more recent work. In particular, I will discuss some of the coding theory behind these results. No previous knowledge of coding theory is assumed.

- 8/25/2020 3PM (Midwest Model Theory Seminar),
Nick Ramsey,
University of California-Los Angeles

Title: Model-theoretic tree propertiesAbstract: The first model-theoretic tree properties were introduced by Shelah as a by-product of his analysis of forking in stable theories. Since then, other tree properties have appeared and, together, these combinatorial dividing lines (TP, TP_{1}/SOP_{2}, TP_{2}, SOP_{1}, etc.) serve as the basis for a growing body of research in model theory. I'll survey the work done in this area (and try to justify the idea that it can be understood as an area) by explaining three of the core ingredients in the theory developed so far: generalized indiscernibles, dividing at a generic scale, and amalgamation. - 9/1/2020 3PM (Midwest Computability Seminar),
Patrick Lutz,
University of California-Berkeley

Title: Part 1 of Martin's Conjecture for order preserving functions (video and slides)Abstract: Martin's Conjecture is an attempt to make precise the idea that the only natural functions on the Turing degrees are the constant functions, the identity, and transfinite iterates of the Turing jump. The conjecture is typically divided into two parts. Very roughly, the first part states that every natural function on the Turing degrees is either eventually constant or eventually increasing and the second part states that the natural functions which are increasing form a well-order under eventual domination, where the successor operation in this well-order is the Turing jump.In the 1980's, Slaman and Steel proved that the second part of Martin's Conjecture holds for order-preserving Borel functions. In joint work with Benny Siskind, we prove the complementary result that (assuming analytic determinacy) the first part of the conjecture also holds for order-preserving Borel functions (and under AD, for all order-preserving functions). Our methods also yield several other new results, including an equivalence between the first part of Martin's Conjecture and a statement about the Rudin-Keisler order on ultrafilters on the Turing degrees.

In my talk, I will give an overview of Martin's Conjecture and then describe our new results.

- 9/8/2020 3PM (Midwest Model Theory Seminar),
Jana
Maříková,
Western Illinois University, Macomb (visiting University of Vienna, Austria)

Title: Quantifier elimination for o-minimal groups expanded by a valuational cutAbstract: We let R be an o-minimal expansion of a group in a language in which Th(R) eliminates quantifiers, and we let C be a valuational cut in R. We show that if nonforking in certain Morley sequences is symmetric, then the theory of R expanded by a predicate for C and a small number of constants eliminates quantifiers. This is a generalization of results on o-minimal fields with convex subrings satisfying some extra conditions such as T-convexity or o-minimality of the residue field. This is joint work with C. F. Ealy. - 9/15/2020 3PM (Midwest Computability Seminar),
Justin Miller,
University of Notre Dame, Indiana

Title: Noncomputable coding, density, and stochasticity (video and slides)Abstract: We introduce the`into`

and`within`

set operations in order to construct sets of arbitrary intrinsic density from any Martin-Löf random. We then show that these operations are useful more generally for working with other notions of density as well, in particular, for viewing Church and MWC stochasticity as a form of density. - 9/22/2020 3PM (local UW logic seminar),
Todor Tsankov,
University of Lyon 1, France

Title: Invariant measures on the space of linear orders on an ℵ_{0}-categorical structureAbstract: Let M be an ℵ_{0}-categorical structure and denote by LO(M) the compact space of linear orders on M. We investigate the probability measures on LO(M) invariant under the natural action of the automorphism group of M and prove, under rather general model-theoretic assumptions, that either M has a definable linear order or LO(M) carries a unique invariant measure (which can be easily and explicitly described). For many structures M, the space LO(M) is the universal minimal flow of the group Aut(M), and our work is in part motivated by a general unique ergodicity question of Angel, Kechris, and Lyons in topological dynamics. Our proof uses techniques from model theory, representation theory, and probability theory, but no special knowledge will be assumed in the talk. I will also provide some background and motivation. This is joint work with Colin Jahel. - 9/29/2020 3PM (Midwest Computability Seminar),
Chris Porter,
Drake University, Des Moines, Iowa

Title: Effective dimension and the intersection of random closed sets (video)Abstract: The connection between the effective dimension of sequences and membership in algorithmically random closed subsets of Cantor space was first identified by Diamondstone and Kjos-Hanssen. In this talk, I highlight joint work with Adam Case in which we extend Diamondstone and Kjos-Hanssen's result by identifying a relationship between the effective dimension of a sequence and what we refer to as the degree of intersectability of certain families of random closed sets (also drawing on work by Cenzer and Weber on the intersections of random closed sets).As we show, (1) the number of relatively random closed sets that can have a non-empty intersection varies depending on the choice of underlying probability measure on the space of closed subsets of Cantor space - this number being the degree of intersectability of a given family of random closed sets - and (2) the effective dimension of a sequence X is inversely proportional to the minimum degree of intersectability of a family of random closed sets, at least one of which contains X as a member. Put more simply, a sequence of lower dimension can only be in random closed sets with more branching, which are thus more intersectable, whereas higher dimension sequences can be in random closed sets with less branching, which are thus less intersectable, and the relationship between these two quantities (that is, effective dimension and degree of intersectability) can be given explicitly.

- 10/6/2020 3PM (local UW logic seminar),
Uri Andrews,
UW

Title: Complexity profiles and the generic Muchnik degrees (slides)Abstract: The generic Muchnik degrees, introduced by Schweber, give a way of comparing the computability-theoretic content of uncountable structures. Though obscured slightly by the need for some set-theoretic machinery, I hope to highlight how this notion really gives an easy and natural way to talk about computable structure theory for uncountable structures. I will focus on the tool of complexity profiles.Complexity profiles are a way of measuring, for two structures A generic Muchnik reducible to B, which subsets of A can be defined using B. The complexity profile of A on itself is the natural analog of considering the relatively intrinsically Σ

_{k}sets in A.Using complexity profiles, I will compare three generic muchnik degrees: Cantor space < Baire space < the Borel-complete degree. In particular, I will describe some dichotomy theorems regarding simple expansions of these and describe how to build degrees strictly between them. (Joint work with Joseph S. Miller, Noah Schweber, and Mariya Soskova.)

- 10/13/2020 3PM (Midwest Computability Seminar),
Leszek Kołoziejczyk,
University of Warsaw, Poland

Title: Reverse mathematics of combinatorial principles over a weak base theory (video and slides)Abstract: Reverse mathematics studies the strength of axioms needed to prove various mathematical theorems. Often, the theorems have the form ∀X ∃Y ψ(X,Y) with X and Y denoting subsets of N and ψ arithmetical, and the logical strength required to prove them is closely related to the difficulty of computing Y given X. In the early decades of reverse mathematics, most of the theorems studied turned out to be equivalent, over a relatively weak base theory, to one of just a few typical axioms, which are themselves linearly ordered in terms of strength. More recently, however, many statements from combinatorics, especially Ramsey theory, have been shown to be pairwise inequivalent or even logically incomparable.The usual base theory used in reverse mathematics is RCA0, which is intended to correspond roughly to the idea of "computable mathematics". The main two axioms of RCA

_{0}are: comprehension for computable properties of natural numbers and mathematical induction for c.e. properties. A weaker theory, in which induction for c.e. properties is replaced by induction for computable properties, has also been introduced, but it has received much less attention. In the reverse mathematics literature, this weaker theory is known as RCA^{*}_{0}.In this talk, I will discuss some results concerning the reverse mathematics of combinatorial principles over RCA

^{*}_{0}. We will focus mostly on Ramsey's theorem and some of its well-known special cases: the chain-antichain principle CAC, the ascending-descending chain principle ADS, and the cohesiveness principle COH.The results I will talk about are part of a larger project joint with Marta Fiori Carones, Katarzyna Kowalik, Tin Lok Wong, and Keita Yokoyama.

- 10/20/2020 3PM (Midwest Model Theory Seminar),
Jerry Keisler,
UW

Title: Using Ultraproducts to Compare Continuous StructuresAbstract: We revisit two research programs that were proposed in the 1960's, remained largely dormant for five decades, and then become hot areas of research in the last decade.The monograph "Continuous Model Theory" by Chang and Keisler, Annals of Mathematics Studies (1966), studied structures with truth values in [0,1], with formulas that had continuous functions as connectives, sup and inf as quantifiers, and equality. In 2008, Ben Yaacov, Berenstein, Henson, and Usvyatsov introduced the model theory of metric structures, where equality is replaced by a metric, and all functions and predicates are required to be uniformly continuous. This has led to an explosion of research with results that closely parallel first-order model theory, with many applications to analysis. In my forthcoming paper "Model Theory for Real-valued Structures", the "Expansion Theorem" allows one to extend many model-theoretic results about metric structures to general [0,1]-valued structures - the structures in the 1966 monograph but without equality.

My paper "Ultrapowers Which are Not Saturated", J. Symbolic Logic 32 (1967), 23-46, introduced a pre-ordering M ≤ N on all first-order structures, that holds if every regular ultrafilter that saturates N saturates M, and suggested using it to classify structures. In the last decade, in a remarkable series of papers, Malliaris and Shelah showed that that pre-ordering gives a rich classification of simple first-order structures. Here, we lay the groundwork for using the analogous pre-ordering to classify [0,1]-valued and metric structures.

- 10/27/2020 3PM (Midwest Computability Seminar),
Liling Ko,
University of Notre Dame, Indiana

Title: Fickleness and bounding lattices in the recursively enumerable Turing degrees (video and slides)Abstract: The ability for a recursively enumerable Turing degree d to bound certain important lattices depends on the degree's fickleness. For instance, d bounds L_{7}(or the 1-3-1 lattice) if and only if d's fickleness is > ω (≥ ω^{ω}, respectively). We work towards finding a lattice that characterizes the > ω^{2}levels of fickleness and seek to understand the challenges faced in finding such a lattice. The candidate lattices considered include those that are generated from three independent points, and upper semilattices that are obtained by removing the meets from important lattices. - 11/3/2020 3PM (local UW logic seminar),
Vera
Fischer,
University of Vienna, Austria

Title: Independent families in the countable and the uncountable (slides)Abstract: Independent families on ω are families of infinite sets of integers with the property that for any two disjoint finite subfamilies A and B, the set ⋂ A \ ⋃ B is infinite. Of particular interest are the sets of the possible cardinalities of maximal independent families, which we refer to as the spectrum of independence. Even though we do have the tools to control the spectrum of independence at ω (at least to a large extent), there are many relevant questions regarding higher counterparts of independence in generalized Baire spaces, which remain wide open. - 11/10/2020 3PM (Midwest Computability Seminar),
Paul Shafer,
University of Leeds, England

Title: Randomness notions and reverse mathematics (video and slides)Abstract: There are many notions of algorithmic randomness in addition to classic Martin-Löf randomness, such as 2-randomness, weak 2-randomness, computable randomness, and Schnorr randomness. For each notion of randomness, we consider the statement "For every set Z, there is a set X that is random relative to Z" as a set-existence principle in second-order arithmetic, and we compare the strengths of these principles. We also show that a well-known characterization of 2-randomness in terms of incompressibility can be proved in RCA_{}, which is non-trivial because it requires avoiding the use of Σ^{0}_{2}-bounding.This work is joint with André Nies.

- 11/17/2020 3PM (local UW logic seminar),
Jaap van Oosten,
Utrecht University, Netherlands

Title: Partial combinatory algebras: Variations on a topos-theoretic theme (video and slides)Abstract: We show a number of constructions in the theory of partial combinatory algebras which highlight the interplay between topos theory and recursion theory. - 11/24/2020 3PM (Midwest Computability Seminar),
Karen Lange,
Wellesley College, Massachusetts

Title: Complexity of root-taking in power series fields and related problems (video and slides)Abstract: In earlier work with Knight and Solomon, we bounded the computational complexity of the root-taking process over Puiseux and Hahn series, two kinds of generalized power series. But it is open whether the bounds given are optimal. By looking at the most basic steps in the root-taking process for Hahn series, we together with Hall and Knight became interested in the complexity of problems associated with well-ordered subsets of a fixed ordered abelian group. Here we provide an overview of the results so far in both these settings. - 12/1/2020 3PM (local UW logic seminar),
Martín
Hötzel Escardó,
University of Birmingham, England

Title: Equality of mathematical structures (video and slides)Abstract: Two groups are regarded to be the same if they are isomorphic, two topological spaces are regarded to be the same if they are homeomorphic, two metric spaces are regarded to be the same if they are isometric, two categories are regarded to be the same if they are equivalent, etc. In Voevodsky's Univalent Foundations (HoTT/UF), the above become theorems: we can replace "are regarded to be the same" by "are the same". I will explain how this works. I will not assume previous knowledge of HoTT/UF or type theory. - 12/8/2020 3PM (Midwest Computability Seminar),
Linda Brown Westrick,
Pennsylvania State University, State College

Title: Luzin's (N) and randomness reflection (video)Abstract: We show that a computable real-valued function f has Luzin's property (N) if and only if it reflects Π^{1}_{1}-randomness, if and only if it reflects Δ^{1}_{1}-randomness relative to Kleene's O, and if and only if it reflects Kurtz randomness relative to Kleene's O. Here a function f is said to reflect a randomness notion R if whenever f(x) is R-random, then x is R-random as well. If additionally f is known to have bounded variation, then we show f has Luzin's (N) if and only if it reflects weak-2-randomness, and if and only if it reflects Kurtz randomness relative to 0'. This links classical real analysis with algorithmic randomness.Joint with Arno Pauly and Liang Yu.