UW Logic Seminar

1/22/2019 4PM, Chris Laskowski, University of Maryland-College Park
Title: Mutually algebraic sets and structures - their history and new characterizations
We begin by tracing the history that led to the discovery of mutually algebraic structures. Recent work with Caroline Terry has led to new characterizations of this notion in terms of disjoint arrays and uniform bounds on the number of coordinatewise non-algebraic types over models. In work with Sam Braunfeld, we describe the stark dividing lines arising from `worst-case expansions' by mutually algebraic sets.

Dinner: Muramoto (108 King St.) at 6:30PM

1/29/2019 4PM, Sergey Goncharov, Siberian Branch of the Russian Academy of Sciences and Novosibirsk State University, Russia
Title: Some results and questions in computable numberings
I will present some new results and open problems in the theory of computable numberings, generalizing results by Goncharov-Sorbi on classical computable numberings for the hierarchies of analytical and arithmetical sets, and functional and the Ershov hierarchy. I will discuss some open problems in the classical theory of computable numberings.

Dinner: Maharani Restaurant (380 W. Washington Ave.) at 6PM

2/5/2019 4PM, Caroline Terry, University of Chicago, Illinois
Title: A stable arithmetic regularity lemma in finite abelian groups
The arithmetic regularity lemma for Fⁿ_p (first proved by Green in 2005) states that given A ⊆ Fⁿ_p, there exists H ≤ Fⁿ_p of bounded index such that A is Fourier-uniform with respect to almost all cosets of H. In general, the growth of the index of H is required to be of tower type depending on the degree of uniformity, and must also allow for a small number of non-uniform elements. Previously, in joint work with Wolf, we showed that under a natural model-theoretic assumption, called stability, the bad bounds and non-uniform elements are not necessary. In this talk, we present results extending this work to stable subsets of arbitrary finite abelian groups. This is joint work with Julia Wolf.

Lunch: leaving from 5th floor of Van Vleck Hall at 11:30am, place TBA

2/12/2019 4PM, Omer Mermelstein, UW
Title: Closed ordinal Ramsey numbers
In this talk, we will discuss the closed ordinal variant of Ramsey theory. We will restrict ourselves to questions pertaining to triangle-free graphs on ordinals below ω^ω, explain how to reduce these graphs to 'canonical' graphs, and present some precise calculations.

2/19/2019 4PM, James Hanson, UW
Title: Strongly minimal sets in continuous logic
The precise structural understanding of uncountably categorical theories given by the Baldwin-Lachlan theorem is known to fail in continuous logic in the context of inseparably categorical theories. The primary obstacle is the absence of strongly minimal sets in some inseparably categorical theories. We will develop the concept of strongly minimal sets in continuous logic and discuss some common conditions under which they are present in an ω-stable metric theory. Finally, we will examine the extent to which we recover the Baldwin-Lachlan theorem in the presence of strongly minimal sets.

2/26/2019 4PM, Jun Le Goh, Cornell University
Title: A theorem of Halin and hyperarithmetic analysis
In 1965, Halin showed that if a graph contains k many disjoint rays for every k, then it contains infinitely many disjoint rays. We show that a natural formalization of Halin's theorem (which we call IRT) is closely connected to the notion of hyperarithmetic reduction, namely, IRT is a theorem of hyperarithmetic analysis. We also introduce a Σ¹₁-axiom of finite choice and show how it is related to IRT.

Dinner: Crandall's Peruvian Bistro (334 State St.) at 6PM

3/5/2019 4PM, Steffen Lempp, UW
Title: Toward deciding the AE-theory of the enumeration degrees
I will outline an approach, in joint work with Slaman and M. Soskova, toward deciding the ∀∃-theory of the enumeration degrees. The procedure is necessarily more difficult than for the Turing degrees since the enumeration degrees are downward dense; however, by a result of Calhoun and Slaman, even the Π⁰₂-enumeration degrees are not dense. Kent and Lewis have extended this to show that there is a strong minimal cover in the Π⁰₂-enumeration degrees, and our work builds on extending that result.

3/12/2019 4PM, Uri Andrews, UW
Title: TBA
TBA

3/26/2019 4PM, Noah Schweber, UW
Title: TBA
TBA

4/4/2019 4PM in room B239, Johanna Franklin, Hofstra University, Hempstead, New York
Title: TBA
TBA

Dinner: TBA at 6PM

4/9/2019 4PM, Tom Drucker, UW-Whitewater
Title: TBA
TBA

4/16/2019 4PM, TBA
Title: TBA
TBA

4/22/2019 4PM in room B239 (department colloquium), Justin Hsu, UW computer science department
Title: TBA
TBA

4/30/2019 4PM, TBA
Title: TBA
TBA

Fall 2019

9/10/2019 4PM, Rod Downey, Victoria University of Wellington, New Zealand
Title: TBA
TBA

Dinner: TBA at 6PM

9/24/2019 4PM, Dieter van Melkebeek, UW computer science department
Title: Isomorphism problems and minimum circuit size
TBA

Fall 2018

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
The 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^ℵ₀ under set inclusion is ℵ₀. 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 theory
  We 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 ceers
  We 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 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: The Nile Restaurant (1162 E. 55th St.) at 6PM

10/23/2018 4PM, Kyle Gannon, University of Notre Dame
Title: Local Keisler measures
The 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 automorphisms
The 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 cardinals
The 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 logic
A 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 numberings
In 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

Archived 2017-18 Logic Seminar Schedule

Archived 2016-17 Logic Seminar Schedule

UW Logic Seminar Schedule