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: Tavernakaya (27 E. Main 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, Gabe Conant, University of Notre Dame, Indiana
Title: Arithmetic regularity with forbidden bipartite configurations
Szemerédi's regularity lemma is a fundamental result in graph theory, which says that sufficiently large finite graphs can be partitioned into a small number of pieces so that the edges between most pairs of pieces are randomly distributed. In other words, the regularity lemma processes finite graphs into ingredients that are either highly structured (namely, the partition of the graph) or highly random (namely, the edges between regular pairs). In 2005, Green introduced arithmetic regularity, which is a group-theoretic analogue of Szemerédi's result. Green's work involves decompositions of finite abelian groups into algebraically structured pieces, which behave randomly with respect to some chosen subset of the group.
In this talk, I will consider subsets A of arbitrary groups G, such that the bipartite graph determined by x · y in A omits some bipartite graph of a fixed finite size. I will present strengthened versions arithmetic regularity in this setting, which yield algebraic structure theorems for sets A as above. This work combines tools from model theory, additive combinatorics, and the structure of compact topological groups. Joint with A. Pillay and C. Terry.

Dinner: The Old Fashioned Tavern (23 N. Pinckney St.) at 6PM

3/26/2019 4PM, Noah Schweber, UW
Title: Topology, games, and reverse mathematics
"Reverse mathematics" is (roughly) the analysis of classical theorems of mathematics in terms of their computability-theoretic content: Some theorems are "computably true" in that all the constructions required in their proofs can be done computably, while others have nontrivial computational strength. This can be thought of as analogous to the study of the role of the Axiom of Choice, but at a more fine-grained level.
In this talk, I'll present some results on the reverse mathematics of topology. Any "reasonable" set X of reals has the Baire property, which is to say that such an X is either meager (i.e., a countable union of nowhere dense sets) or comeager on some open interval; it turns out that there is a game (the Banach-Mazur game), the determinacy of which captures this dichotomy. I'll show how this gives us a satisfying way of analyzing the complexity of principles of the form "Every [complexity-level] set has the Baire property," and in particular demonstrates that such principles exhibit a strange combination of strength and weakness, which seems new in reverse mathematics.

4/3/2019 4PM in room B115, Johanna Franklin, Hofstra University, Hempstead, New York
Title: Effective measures for algebraic structures
R. Miller has introduced a method for defining an effective measure on the spaces of the isomorphism types of computable structures such as field extensions of the rationals and finitely branching trees. This allows us to determine whether certain properties of computable structures are null or conull for these classes. Furthermore, if a property is conull, we can often effectivize our answer and say that every random structure has this property for some notion of randomness. I will discuss the definitions of these measures and the applications of these ideas to the property of computable categoricity.
This work is joint with R. Miller.

Dinner: Himal Chuli Restaurant (318 State St.) at 6PM

4/9/2019 4PM, Tom Drucker, UW-Whitewater
Title: Von Platon zu von Plato: What have technical results done for foundations?
Plato raised some objections to what mathematicians did 2400 years ago by way of what he saw as the lack of relevance to understanding mathematics. Current philosophers can ask the same question about the technical results of the twentieth century. This talk will look at some of the results that provide support for understanding how the foundations of mathematics work, especially in light of Jan von Plato’s recent book on the twentieth century’s advances in logic.

4/18/2019 Midwest Model Computability Seminar, University of Chicago
Lunch: in Ryerson 352 at noon
Speakers:
- 1PM, Wesley Calvert, Southern Illinois University, Carbondale
  Title: Probability, density, and structure
  This talk will give account of some converging trends at the intersection of logic and probability. Randomized computation, dense/generic/coarse computability, theories of random graphs and structures, and theoretical machine learning have subtle connections, and their points of contactpose interesting problems for mathematical logic. In addition to an exposition on several older results and their interactions, this talk will include some recent results on categoricity in an environment of generic and coarse computability.
- 2PM, Russell Miller, Queens College, New York City
  Title: Hilbert's Tenth Problem as an enumeration operator
  For a ring R, Hilbert's Tenth Problem is the set HTP(R) of polynomials f ∈ R[X0,X1,...] for which f = 0 has a solution in R. It has been known since the work of Davis, Putnam, Robinson, and Matiyasevich in 1970 that HTP(Z) is as hard as the Halting Problem, and indeed that every computably enumerable set is diophantine in Z, i.e., definable in Z by an existential formula, and thus decidable from HTP(Z). In contrast, the decidability of HTP(Q) is an open question.
  It is natural to view HTP as a pseudojump operator, mapping each set W of prime numbers to the set HTP(Z[W^-1]). (Every subring of Q is of this form, for some W.) One might hope to relate it to the jump operator, which maps W to its jump W'. In fact, though, HTP is an enumeration operator. We will discuss ways in which this distinguishes it from the jump operator. There do exist sets W (including the empty set) for which W' is diophantine in HTP(Z[W^-1]), and indeed they occur in every Turing degree; on the other hand, under Lebesgue measure, they are quite rare. The weaker statement that HTP(Z[W^-1]) at least computes W' is known to be false in certain cases, but remains open for most sets W. We will show that no single oracle Turing machine can accomplish this reduction uniformly on a set of rings of full Lebesgue measure.
- 4PM, Steffen Lempp, UW
  Title: Toward deciding the ∀∃-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.
Dinner: Nella Pizza e Pasta (1125 E. 55th St.) at 5:30PM

4/22/2019 4PM in room B239 (department colloquium), Justin Hsu, UW computer science department
Title: From couplings to probabilistic relational program logics
Many program properties are relational, comparing the behavior of a program (or even two different programs) on two different inputs. While researchers have developed various techniques for verifying such properties for standard, deterministic programs, relational properties for probabilistic programs have been more challenging. In this talk, I will survey recent developments targeting a range of probabilistic relational properties, with motivations from privacy, cryptography, machine learning. The key idea is to meld relational program logics with an idea from probability theory, called probabilistic couplings. The logics allow a highly compositional and surprisingly general style of program analysis, supporting clean proofs for a broad array of probabilistic relational properties.

4/23/2019 MidWest Model Theory Day, University of Illinois-Chicago
Lunch: in SEO 636 at noon
Speakers:
- 1PM, Nir Avni, Northwestern University, Evanston, Illinois
  Title: Rigidity and bi-interpretability with Z for higher rank lattices
  A lattice in a Lie group is a discrete subgroup with finite co-volume. In many contexts, there is a dichotomy between lattices in Lie groups of rank one and lattices in Lie groups of higher rank, where the two classes behave in qualitatively different ways. I will talk about this dichotomy in the context of model theory.
- 2:30PM, Rizos Sklinos, Stevens Institute of Technology, Hoboken, New Jersey
  Title: Fraïssé constructions in the free group
  In an influential paper Fraïssé obtained the ordered rationals as a limit of finite linear orders through amalgamations. Furthermore, his construction implied the (ultra)-homogeneity, the countability and universality of the limit structure. Since then various adaptations of Fraïssé's method had given very interesting examples in many mathematical disciplines. The random graph in graph theory and Philip Hall's universally locally finite group in group theory to name a few.
  In joint work with Kharlampovich and Myasnikov, we look into the possibility of applying Fraïssé constructions in classes of groups that played a central role in answering Tarski's question on nonabelian free groups. In particular, we modify Fraïssé's method to prove that nonabelian limit groups form a ∀-Fraïssé class, and finitely generated elementary free groups form an elementary-Fraïssé class.
- 4PM, Meng-Che ("Turbo") Ho, Purdue University, West Lafayette, Indiana
  Title: Scott sentences of finitely-generated groups
  Scott showed that for every countable structure A, there is an L_ω₁,ω-sentence, called the Scott sentence, whose countable models are the isomorphic copies of A. The quantifier complexity of a Scott sentence can be thought of as a measure of the complexity of the structure. Knight et al. have studied the Scott sentences of many structures. In particular, Knight and Saraph showed that a finitely-generated structure always has a Σ₃-Scott sentence. In this talk, we will focus on finitely-generated groups. On the one hand, most "natural" finitely-generated groups have a d-Σ₂-Scott sentence. On the other hand, we give a characterization of finitely-generated structures where the Σ₃-Scott sentence is optimal. We then give a construction of a finitely-generated group where the Σ₃-Scott sentence is optimal.
  This is joint work with Matthew Harrison-Trainor.
Dinner: TBA at 6PM

4/30/2019 4PM, Nick Ramsey, University of California-Los Angeles
Title: Exact saturation in pseudo-elementary classes
Suppose κ is your favorite singular cardinal and T is your favorite complete theory. Now ask the question: Does T have a κ-saturated model that is not κ⁺-saturated? Perhaps your favorite theory was the theory of algebraically closed fields, in which case the answer is 'yes', but maybe it was the theory of dense linear orders, in which case the answer is 'no'. What's the difference? This turns out to be a question without a very nice answer, but reformulated in the context of pseudo-elementary classes, it connects to a number of interesting notions from classification theory. We will describe some of these connections, bringing together techniques from model theory, set theory, and (if you squint) a tiny bit of recursion theory. This is joint work with Itay Kaplan and Saharon Shelah.

Fall 2019

9/3/2019 4PM, Jun Le Goh, UW
Title: TBA
TBA

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

Dinner: TBA at 6PM

9/17/2019 4PM, Iskander Kalimullin, Kazan Federal University, Russia
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

UW Logic Seminar Schedule