- 1/22/2019 4PM,
Chris Laskowski,
University of Maryland-College Park

Title: TBATBA

Dinner: TBA at 6PM - 1/29/2019 4PM,
Sergey
Goncharov, Siberian Branch of the Russian Academy of Sciences and
Novosibirsk State University, Russia

Title: TBATBA

Dinner: TBA at 6PM - 2/5/2019 4PM,
Caroline Terry,
University of Chicago, Illinois

Title: TBATBA

Dinner: TBA at 6PM - 2/12/2019 4PM,
Omer Mermelstein,
UW

Title: TBATBA - 2/26/2019 4PM,
Dieter van Melkebeek,
UW computer science department

Title: Isomorphism problems and minimum circuit sizeTBA

- 9/4/2018 4PM,
Mike
Benedikt, Oxford University, England

Title: A computational view of Beth definabilityThe Beth Definability Theorem is a result found in many basic logic textbooks, but it may not be clear why the result is interesting or important. In this talk, I will describe a perspective on Beth Definability from query reformulation. In reformulation, one is given a formula Q (the "query") and a background theory T, and the goal is to translate Q either into another formula or a direct procedural implementation such that the translation is equivalent to Q according to T, and such that the translation satisfies additional "interface restrictions". Limitations on the logical vocabulary represent one kind of interface restriction, but I will mention some finer-grained restrictions. I will review the approach to solving these problems using variants of Beth's theorem. The variants in turn require modifications of Craig's interpolation theorem, and I will sketch how these interpolation results can be proven.The majority of the talk won't assume much background beyond basic logic.

Dinner: Crandall's Gourmet Peruvian & American Cuisine (334 State St.) at 6PM - 9/11/2018 4PM,
Omer
Mermelstein, UW

Title: Conjectures and questions on flat combinatorial pregeometriesThe property of "flatness" of a pregeometry (matroid) is best known in model theory as the device with which Hrushovski showed that his example refuting Zilber's conjecture does not interpret an infinite group. Indeed, the pregeometry associated to any hypergraph via Hrushovski's delta-function is flat, and it is known that any finite flat pregeometry (strict gammoid) can be gotten this way.In this talk, after making sense of the first paragraph of this abstract, we will show that the interplay between hypergraphs and flat pregeometries runs deeper, and make some reckless conjectures.

- 9/18/2018 4PM,
Noah
Schweber, UW

Title: Three flavors of computability on ordinalsGiven countable structures M and N in a computable language, say that M is "Medvedev reducible to" N if copies of N uniformly compute copies of M. This notion has been much less studied than its nonuniform version (Muchnik reducibility). Even restricted to countable ordinals (viewed as countable well-orderings), Medvedev reducibility is quite weird.An ongoing project of mine is to understand the general behavior of Medvedev reducibility on the ordinals. In this talk, I'll present one particular aspect of the problem: Given an ordinal α, how does the supremum of the ordinals Medvedev reducible to α (= Med(α)) compare with other notions of "least non-α-computable ordinal?" Specifically, I'll look at two such points emerging naturally from generalized computability theory, and show that in general Med(α) lies strictly between these two points. One of these inequalities is straightforward computability theory; the other requires a more set-theoretic argument, using forcing.

If time remains, I'll also outline a result on the degree structure of Medvedev reducibility on the ordinals; I'll show that it has "large antichains," the key difficulty being proving this result inside ZFC.

- 9/25/2018 4PM,
Peter Cholak, University
of Notre Dame

Title: Encodable by thin setsLet c be a coloring of n-tuples (of ω) by finitely many colors. For ℓ less than the number of colors, a set T is ℓ-*thin*iff c uses at most ℓ colors to color all the n-tuples from T. We say a set S is RT^{n}_{< ∞,ℓ}-*encodable*iff there is a coloring c as above such that every ℓ-thin set computes S. Wang and others showed that when ℓ is "big", only the computable sets are RT^{n}_{< ∞,ℓ}-encodable. Dorais, Dzhafarov, Hirst, Mileti, and Shafer showed that the hyperarithmetic sets are RT^{n}_{< ∞,ℓ}-encodable for ℓ < 2^{n-1}. Cholak and Patey showed that the arithmetic sets are RT^{n}_{< ∞,ℓ}-encodable for "medium" ℓ. In the talk, we will provide definitions of "medium" and "big" (with an error of at most 1). What is also of interest is the role that cone avoidance plays in determining "medium" and "big". This is joint work with Ludovic Patey.

Dinner: Lombardino's Restaurant and Bar (2500 University Ave.) at 6PM - 10/2/2018 4PM,
Steffen
Lempp, UW

Title: On the dimension of partial ordersThe dimension of a partial order is the smallest number of linear extensions such that their intersection is the partial order.We show that the dimension of the partial order of all finite subsets of 2

^{ℵ0}under set inclusion is ℵ_{0}. More generally, if κ ≤ 2^{λ}for infinite cardinals κ and λ such that λ is least such, then [κ]^{<λ}as a partial order under set inclusion has dimension λ.We also show that the dimension of any locally countable partial ordering P of size κ

^{+}for regular uncountable κ is at most κ. In particular, this implies that it is consistent with ZFC that the dimension of the Turing degrees under partial ordering can be strictly less than the continuum.This is joint work with Higuchi (Nagoya) as well as Raghavan and Stephan (Singapore).

- 10/9/2018
Midwest Computability Seminar, University of Chicago

Lunch: in Ryerson 352 at 12:30PM

Speakers:- 1:30PM, Tim McNicholl, Iowa State University, Ames

Title: Effective metric structure theoryWe will survey recent work on extending the classical computable structure theory program to uncountable metric structures by means of the framework of computable analysis. Specifically, we will summarize results on degrees of categoricity, index sets, and computable presentability for metric spaces and Banach space, especially Lebesgue spaces.

- 2:30PM, Uri
Andrews, UW

Title: Recent developments on the structure of ceersWe consider the structure of c.e. equivalence relations (ceers) under computable reduction. That is, if E and R are ceers, then we say E ≤ R if and only if there is a computable function f: ω → ω so that n E m if and only if f(n) R f(m). This structure is simultaneously reminiscent of the r.e. 1-degrees in some ways and the r.e. m-degrees in other ways, while having some interesting unique features of its own. I'll try to give an overview to let you know what is known about this structure and to point to some of the most important (purely based on my personal tastes) open problems in this area.

- 4:15PM, Alexandra Soskova, Sofia University, Bulgaria

Title: Strong jump inversionWe establish a general result with sufficient conditions for a structure A to admit strong jump inversion. We say that a structure A admits strong jump inversion provided that for every oracle X, if X' computes D(C)' for some C isomorphic to A, then X computes D(B) for some B isomorphic to A. Jockusch and Soare showed that there are low linear orderings without computable copies, but Downey and Jockusch showed that every Boolean algebra admits strong jump inversion. More recently, Marker and R. Miller have shown that all countable models of DCF_{0}(the theory of differentially closed fields of characteristic 0) admit strong jump inversion. Our conditions involve an enumeration of B_{1}-types, where these are made up of formulas that are Boolean combinations of existential formulas. Our general result applies to some familiar kinds of structures, including some classes of linear orderings and trees, and Boolean algebras with no 1-atom, with some extra information on the complexity of the isomorphism. Our general result gives the result of Marker and R. Miller. In order to apply our general result, we produce a computable enumeration of the types realized in models of DCF_{0}. This also yields the fact that the saturated model of DCF_{0}has a decidable copy.This is a joint work with Calvert, Frolov, Harizanov, Knight, McCoy, and Vatev.

- 1:30PM, Tim McNicholl, Iowa State University, Ames
- 10/23/2018 4PM,
Kyle Gannon, University
of Notre Dame

Title: Local Keisler measuresThe connection between finitely additive probability measures and NIP theories was first noticed by Keisler. Around 20 years later, the work of Hrushovski, Peterzil, Pillay, and Simon greatly expanded this connection. Out of this research came the concept of generically stable measures. In the context of NIP theories, these particular measures exhibit stable behavior. In particular, Hrushovski, Pillay, and Simon demonstrated that generically stable measures admit a natural approximation.In this talk, we will discuss generically stable measures in the local setting. We will describe connections between these measures and concepts in functional analysis as well as show that this interpretation allows us to derive an approximation theorem.

No prior knowledge beyond basic model theory will be assumed. We will explain all of our definitions in the talk.

Dinner: The Side Door Grill & Tap (240 W. Gilman St.) at 6PM - 10/30/2018 4PM,
Iván Ongay
Valverde, UW

Title: An entangled approach to automorphismsThe question "Is there an automorphisms of the Turing degrees?" has received a lot of attention. A couple of decades ago, Woodin and Slaman showed that there can be at most countably many automorphisms, and all of them be represented in an arithmetical way.Using this result and a modified construction of an entangled set (due to Avraham) we will show that, under set theoretic assumption, some extra restriction can be given to these automorphisms.

- 11/6/2018 4PM,
Sherwood
Hachtman, University of Illinois-Chicago

Title: Trees and guessing near singular cardinalsThe tree property, TP, is a combinatorial principle which generalizes König's infinity lemma to uncountable cardinals. TP is a compactness property, and forcing instances of it requires large cardinals. A longstanding program aims to force the TP to hold simultaneously with as many cardinals as possible; but serious technical obstacles are encountered due to tension with incompactness around singular cardinals.We consider a generalization of the TP to a certain global property, the "super tree property" ITP. The ITP characterizes supercompactness, but can consistently hold for small cardinals. These are closely related to a family of guessing principles which have found a number of applications in inner model theory and infinitary combinatorics.

I will introduce these principles with as few prerequisites as possible, and discuss results on the extent to which the super tree property can hold near a singular. This is joint work with Dima Sinapova.

- 11/20/2018 4PM (
**room 911**), Denis Hirschfeldt, University of Chicago, Illinois

Title: Computability and Ramsey Theory (department colloquium)Computability theory can be seen as the study of the fine structure of definability. Much of its power relies on the deep connections between definability and computation. These connections can be seen in fundamental results such as Post's Theorem, which establishes a connection between the complexity of formulas needed to define a given set of natural numbers and its computability-theoretic strength. As has become increasingly clear, they can also be seen in the computability-theoretic analysis of objects whose definitions come from notions that arise naturally in combinatorics. The heuristic here is that computability-theoretically natural notions tend to be combinatorially natural, and vice-versa. I will discuss some results and open questions in the computability-theoretic analysis of combinatorial principles, in particular Ramsey-theoretic ones such as versions of Ramsey's Theorem for colorings of countably infinite sets, and versions of Hindman's Theorem, which states that for every coloring of the natural numbers with finitely many colors, there is an infinite set of numbers such that all nonempty sums of distinct elements of this set have the same color.

Dinner: Morris Ramen (106 King St.) at 6PM - 11/27/2018 4PM,
Wim Ruitenburg,
Marquette University, Milwaukee, Wisconsin

Title: Differences between intuitionistic and constructive logicA new and coherent proof interpretation of predicate logic leads to a new constructive logic different from intuitionistic predicate logic. The new proof interpretation may have a satisfactory theory of constructions and proofs. - 12/4/2018 4PM,
Peter Gerdes, Oakland
University, Rochester, Michigan

Title: An ω-REA set forming a minimal pair with 0′It is easy to see that no n-REA set can form a (non-trivial) minimal pair with 0' and only slightly more difficult to observe that no ω-REA set can form a (non-trivial) minimal pair with 0''. Shore has asked whether this can be improved to show that no ω-REA set forms a (non-trivial) minimal pair with 0'. We show that no such improvement is possible by constructing a set C with 0 <_{T}C ≤_{T}0' forming a minimal pair with 0'.

Dinner:**Monday, Dec. 3**, Canteen (111 S. Hamilton St.) at 6PM - 12/11/2018 4PM,
Manat Mustafa,
Nazarbayev University, Astana, Kazakhstan

Title: On computable numberingsIn recursive mathematics and computability theory, we encounter various situations which naturally lead one to the study of classes of constructive objects. An examination of the algorithmic properties of classes of constructive objects fares best with the techniques and notions of the theory of computable numberings. In the theory of algorithms, all objects are treated with respect to a numbering modulo computable equivalence, and the notion of equivalent numberings is chosen suitably. Any index n of the set with respect to a numbering may be thought as a description of that set in some formal language. Therefore, equivalent numberings are not distinguishable from an algorithmic point of view. This approach allows formulating most of the problems on numberings in terms of Rogers semilattices.I will discuss some results and open questions on computable numberings and Rogers semilattices.

Dinner: Hopcat (222 W. Gorham St.) at 6PM