- 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 ordersTBA

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

Lunch: in Ryerson 352 at noon

Speakers:- 1:30PM, Uri
Andrews, UW

Title: TBATBA

- 2:30PM, Tim McNicholl, Iowa State University, Ames

Title: TBATBA

- 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, Uri
Andrews, UW
- 12/11/2018 (tentative) 4PM,
Manat Mustafa,
Nazarbayev University, Astana, Kazakhstan

Title: TBATBA

Dinner: TBA at 6PM