UW Logic Seminar

9/4/2018 4PM, Mike Benedikt, Oxford University, England
Title: A computational view of Beth definability
The 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 pregeometries
The 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 ordinals
Given 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 sets
Let 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ⁿ_{< ∞,ℓ}-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ⁿ_{< ∞,ℓ}-encodable. Dorais, Dzhafarov, Hirst, Mileti, and Shafer showed that the hyperarithmetic sets are RTⁿ_{< ∞,ℓ}-encodable for ℓ < 2^n-1. Cholak and Patey showed that the arithmetic sets are RTⁿ_{< ∞,ℓ}-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 orders
TBA

10/9/2018 Midwest Computability Seminar, University of Chicago
Lunch: in Ryerson 352 at noon
Speakers:
- 1:30PM, Uri Andrews, UW
  Title: TBA
  TBA
- 2:30PM, Tim McNicholl, Iowa State University, Ames
  Title: TBA
  TBA
- 4:15PM, Alexandra Soskova, Sofia University, Bulgaria
  Title: Strong jump inversion
  We 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₀ (the theory of differentially closed fields of characteristic 0) admit strong jump inversion. Our conditions involve an enumeration of B₁-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₀. This also yields the fact that the saturated model of DCF₀ has a decidable copy.
  This is a joint work with Calvert, Frolov, Harizanov, Knight, McCoy, and Vatev.
Dinner: TBA at 6PM

12/11/2018 (tentative) 4PM, Manat Mustafa, Nazarbayev University, Astana, Kazakhstan
Title: TBA
TBA

Dinner: TBA at 6PM

UW Logic Seminar Schedule