UW Logic Seminar

UW Logic Seminar 2017-18

Fall 2017

9/5/2017 4PM, Dino Rossegger, Vienna University of Technology, Austria
Title: Bi-embeddability spectra of structures

One aim in computable structure theory is to measure the computational complexity of countable structures. The main property to investigate in this line of research is the degree spectrum of a structure, the set of Turing degrees of its isomorphic copies.

In joint work with Ekaterina Fokina and Luca San Mauro we investigate a related notion, bi-embeddability spectra. Two structures are bi-embeddable if each is embeddable in the other and the bi-embeddability spectrum of a structure is the set of Turing degrees of its bi-embeddable copies. We give general results on bi-embeddability spectra and investigate bi-embeddability spectra of strongly locally finite graphs.

Dinner: Great Dane Pub (123 E. Doty St.) at 6PM

9/12/2017 4PM, Steffen Lempp, UW
Title: Numberings of finite families of c.e. sets

I will discuss an old open problem posed by Ershov in the 1970's: The Rogers semilattice of a family F of c.e. sets is the collection of computable numberings (i.e., uniform enumerations) of F, identifying numberings which can be effectively reduced to each other, and partially ordered by this reducibility (i.e., a numbering μ reduces to a numbering ν if there is a computable function f taking a μ-index n to a ν-index f(n) of the same set). It is not hard to check that a Rogers semilattice always forms a distributive upper semilattice.
Ershov asked for a characterization of the finite families F and G of c.e. sets such that their Rogers semilattices are isomorphic. In the late 1970's, two results were shown: Khutoretskii proved that the Rogers semilattice of any family of c.e. sets must be infinite or of size at most 1. Denissov showed that for any n, the Rogers semilattices of {∅, {0}} and {∅, {0}, {1}, ..., {n}} are isomorphic. (Note that for finite families of c.e. sets, the isomorphism type of the Rogers semilattice is completely determined by the isomorphism type of F under set inclusion.) Denissov's proof is quite delicate, by a non-effective back-and-forth argument. In 2003, Ershov showed a partial generalization of Denissov's result: If the Rogers semilattices of the finite families F and G are isomorphic, then the collections of nonmaximal elements of F and G (under set inclusion) must be isomorphic; the converse is open and was conjectured by Kudinov to give the desired characterization.
After some background, I will sketch Denissov's and Ershov's proofs and point out the difficulties in proving Kudinov's conjecture. My talk will be based on extensive discussions with Badaev, Ng and Wu.

9/19/2017 4PM, Jim Freitag, University of Illinois at Chicago
Title: Model theory and the combinatorics of banned sequences

In this talk, we will introduce the combinatorial notion of thicket density. Roughly, the notion sits in relation to Shelah 2-rank as VC-density is to VC-dimension. Earlier this year, Bhaskar established a growth dichotomy theorem in this setting along the lines of the Sauer-Shelah Lemma. In this talk, we will explain how Bhaskar's result, the Sauer-Shelah Lemma, and several other model-theoretic results all come from one unifying combinatorial result. If time permits, we will explain several new results in the style of the Sauer-Shelah Lemma in various model-theoretic settings and we will explain how our combinatorial principle can be used to improve bounds of Malliaris-Terry.

9/26/2017 4PM, John Baldwin, University of Illinois at Chicago
Title: What is Euclid's continuum problem?

We explore the changing conceptions of the geometric continuum in Euclid, Archimedes, Descartes, Hilbert, and Tarski and argue: Hilbert's first-order axioms account for the bulk of Euclid; he adopted an equivalent of Dedekind's axiom to ground analysis, not geometry. Tarski's first-order complete first-order axiomatization provides a finitistically justifiable basis for Descartes' geometry (which is not the modern notion of `Cartesian geometry'). Using o-minimality, we extend this theory to provide a first-order account of the formulas for area and circumference of a circle. Finally, we provide L_ω₁,ω-categorical axiomatizations of various geometries that we find more fruitful than the traditional second-order versions. This analysis demonstrates the importance of logical formalization for both philosophy and mathematics.

Dinner: Kabul Restaurant (541 State St.) at 6PM

10/3/2017 Midwest Model Theory Day, University of Illinois at Chicago
Lunch: in SEO 636 at noon
Speakers:

1PM, Caroline Terry, University of Maryland, College Park
Title: A stable arithmetic regularity lemma
In this talk we present a stable version of the arithmetic regularity lemma for vector spaces over fields of prime order. 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. Our main result is that, under a natural stability theoretic assumption, the bad bounds and non-uniform elements are not necessary. Specifically, we present an arithmetic regularity lemma for k-stable sets A ⊆ Fⁿ_p, where the bound on the index of the subspace is only polynomial in the degree of uniformity, and where there are no non-uniform elements. This result is a natural extension to the arithmetic setting of the work on stable graph regularity lemmas initiated by Malliaris and Shelah.
2:30PM, John Goodrick, Universidad de los Andes, Bogotá, Colombia
Title: Model theory of groups of finite dp-rank and finite burden
We will present several recent results concerning the model theory of groups whose theories are of finite rank, where "rank" means either dp-rank or burden (inp-rank). First, we review some results (joint with A. Dolich) about ordered Abelian groups of finite burden, where "burden" or "inp-rank" is a generalization of weight which is useful in unstable theories; in this context, we can show that unary definable sets satisfy various desirable properties. Next, we present more recent results (joint with J. Dobrowolski) showing that inp-minimal groups with an ordering invariant under left translations are Abelian, and also showing that finite weight stable groups cannot be too far from being Abelian. Finally, we will present some open questions and possible future directions for research.
4PM, Joel Nagloo, Bronx Community College, CUNY, New York
Title: Towards strong minimality and the Fuchsian triangle groups
From the work of Freitag and Scanlon, we have that the ODEs satisfied by the Hauptmoduls of arithmetic subgroups of SL2(Z) are strongly minimal and geometrically trivial. A challenge is to now show that same is true of ODEs satisfied by the Hauptmoduls of all (remaining) Fuchsian triangle groups. The aim of this talk is to both explain why this an interesting/important problem and also to discuss some of the progress made so far.

Dinner: Bracket Room (1315 S. Halsted St.) at 6PM

10/10/2017 4PM, Steffen Lempp, UW
Title: Computable linear orders and products

There are quite a few results in the study of computable linear orders of the form "τ·L is computable iff L is 0⁽ⁿ⁾-computable". The goal of joint work with Frolov, Ng and Wu is to classify the order types τ for which such statements are true. We will concentrate on the case n=0, where we have an exact classification: An order type τ has the property that "τ·L is computable iff L is computable" iff τ is finite and nonempty. I will conclude with some general comments.

10/17/2017 4PM, Noah Schweber, UW
Title: Banach-Mazur games in computability theory

I'll talk about computability-theoretic aspects of Banach-Mazur games. I'll talk about the reals which can be coded into games, and analyze the strength of Banach-Mazur determinacy principles for levels of the Borel hierarchy. Time permitting, I'll also show some interactions between one of the forcings used in studying reals coded into games and general set-theoretic questions.

10/24/2017 1PM, Midwest Computability Seminar, University of Chicago
Lunch: Ryerson Hall 352 at noon
Speakers:

1PM, Noah Schweber, UW
Title: Computability and Banach-Mazur games
We'll look at some questions around Banach-Mazur games. On the pure computability-theoretic side, after establishing the effectiveness of some basic facts about Banach-Mazur games, we classify the functions computable from all winning strategies for some Banach-Mazur game as exactly the hyperarithmetic sets, using an analogue of Hechler forcing for building strategies. On the reverse mathematical side, we parallel this by showing that Borel Banach-Mazur determinacy is equivalent to ATR0, and that this equivalence goes "level-by-level;" by contrast, we also show that there is a Turing ideal satisfying lightface Σ¹₁-Banach-Mazur determinacy but not containing 0^(α), this time using an analogue of Spector forcing for building strategies.
2PM, Don Stull, Iowa State University, Ames
Title: Effective dimension of points on lines
This talk will cover recent work using Kolmogorov complexity to study the dimension of points on lines in the Euclidean plane and its application to important questions in fractal geometry. In particular, we will show that this work strengthens the lower bounds of the dimension of Furstenberg sets. We will also discuss future research and open problems in this area. This talk is based on joint work with Neil Lutz.
3:30, Rose Weisshaar, University of Notre Dame, Indiana
Title: Countable ω-models of KP and paths through computable ω-branching trees
It is well known that the Π⁰₁-class C_PA ⊆ 2^ω of completions of Peano arithmetic is universal among nonempty Π⁰₁-subsets of Cantor space. When we consider Π⁰₁-subsets of Baire space, however, there is no such universal example. In this talk, we consider a Π⁰₁-class C_KP ⊆ ω^ω whose paths compute the complete diagrams of countable ω-models of Kripke-Platek set theory (KP). We develop an analogy between how elements of C_PA and C_KP try to compute members of nonempty Π⁰₁-subsets of Cantor space and Baire space, respectively, and we examine how this analogy breaks down. This is joint work with Julia Knight and Dan Turetsky.
4:10PM, Dan Turetsky, University of Notre Dame, Indiana
Title: C.e. equivalence relations and the linear orders they realize
Quotient structures are well studied. In the case of linear orders, it is known that the order-types realized by c.e. quotient structures are precisely those realized by Δ⁰₂-linear orders. We come at this from a different perspective, by considering, for each c.e. equivalence relation, which order-types can be realized as a quotient by that equivalence relation. We study the relationship between computability-theoretic properties of the equivalence relation and the algebraic properties of the order-types it can realize. We also define a pre-order on equivalence relations by comparing the collection of order-types realized in each.

Dinner: Nella Pizza & Pasta (1125 E. 55th St.) at 5:30PM

11/2/2017 4PM (B231 Van Vleck), Anand Pillay, University of Notre Dame, Indiana
Title: Stability, Vapnik-Chervonenkis dimension, groups, and regularity theorems

I will try to give an accessible and not particularly technical talk about dividing lines in model theory, and the connections to other parts of mathematics including combinatorics. I plan to include some current work with Conant and Terry.

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

11/7/2017 4PM, Iván Ongay Valverde, UW
Title: Effectivizing Localization numbers: the surviving degrees

Inspired by the work of Rupprecht and others, we study the effective analogue of k-localization numbers. These, the k-surviving degrees, are the degrees that are capable of computing a function in (k+1)^ω that is not a branch of any k-subtree of (k+1)^<ω. Interestingly, these degrees can be computably traceable. In this talk I will introduce the necessary concepts to talk about these degrees and their weaker brother, the globally k-surviving degrees which, surprisingly, lead us in a direction to have new results in cardinal invariants of set theory related to evasion and prediction. This is a joint work with Noah Schweber.

11/14/2017 4PM, Mariya Soskova, UW
Title: Characterizing the continuous degrees

The continuous degrees were introduced by J. Miller as a way to capture the effective content of elements of computable metric spaces. They properly extend the Turing degrees and naturally embed into the enumeration degrees. Although nontotal (i.e., non-Turing) continuous degrees exist, they are difficult to construct: every proof we know invokes a nontrivial topological theorem.

In 2014, M. Cai, Lempp, J. Miller and Soskova discovered an unusual structural property of the continuous degrees: if we join a continuous degree with a total degree that is not below it then the result is always a total degree. We call degrees with this curious property almost total. We prove that the almost total degrees coincide with the continuous degrees. Since the total degrees are definable in the partial order of the enumeration degrees, this implies that the continuous degrees are also definable. Applying earlier work of J. Miller on the continuous degrees, this shows that the relation "PA above" on the total degrees is definable in the enumeration degrees.

In order to prove that every almost total degree is continuous, we pass through another characterization of the continuous degrees that slightly simplifies one of Kihara and Pauly. Like them, we identify our almost total degree as the degree of a point in a computably regular space with a computable dense sequence, and then we apply the effective version of Urysohn's metrization theorem to reveal our space as a computable metric space.

This is joint work with Uri Andrews, Greg Igusa, and Joseph Miller.

11/21/2017 4PM, Meng-Che ("Turbo") Ho, Purdue University
Title: Finitely generated groups are universal

It is well known that any structure can be coded in a graph. Hirschfeldt, Khoussainov, Shore, and Slinko showed that you can also code any structure in a partial ordering, lattice, integral domain, or 2-step nilpotent group, and showed that certain computability properties are preserved under this coding. Recently, R. Miller, Poonen, Schoutens, and Shlapentokh added fields to this list, and they gave a category-theoretic framework to establish their result. Around the same time, Montalbán introduced the notion of effective interpretation and showed that effectively bi-interpretable structures share many computability-theoretic properties. Thus, using either of these notions, we may define the notions of a class of structures being universal, and Harrison-Trainor, Melnikov, R. Miller, and Montalbán showed that these two notions are indeed equivalent.

In joint work with Harrison-Trainor, we use these ideas to define a class of structures being universal within finitely generated structures. We then use small cancelation techniques from group theory to show that the class of finitely generated groups with finitely many constants named is universal within finitely generated structures.

Dinner: Great Dane Pub (123 E. Doty St.) at 6PM

11/28/2017 4PM, Ethan McCarthy, UW
Title: Cototal enumeration degrees and their applications to effective mathematics

A set A ⊆ ω is cototal under enumeration reducibility if A is e-reducible to its complement, in which case we also call the enumeration degree of A cototal. We will look at several classes of mathematical objects whose enumeration degrees are characterized by cototality, including the complements of maximal anti-chains on ω^<ω, the enumeration-pointed trees on 2^<ω (which are known to code every nontrivial structure spectrum with an F_σ base), and the languages of minimal subshifts on 2^<ω (which are known to code the Turing degree spectra of minimal subshifts on 2^<ω).

12/5/2017 4PM, Tamvana Makuluni, UW
Title: "Local" continuity of functions in ordered convexly orderable theories

A convexly orderable theory is one in which a linear order can be added in such a way that families of definable sets in the home sort have uniformly finitely many convex components in the added order. Convex orderability is a generalization of VC-minimality, but it is unknown exactly how they are related. I present a result on the behavior of functions definable in certain convexly orderable theories which indicates a potential means of attacking this question, and also hints at a potential classification of definable sets in a convexly orderable theory.

12/12/2017 4PM, Denis Hirschfeldt, University of Chicago, Illinois
Title: The reverse mathematics of model theory and first-order principles

Reverse mathematics seeks to classify the relative strength of theorems across mathematics, often in terms of a small number of axiomatic systems with natural computability-theoretic analogs, such as RCA₀, which corresponds\ roughly to computable mathematics, and ACA₀, which corresponds roughly to arithmetic mathematics. Recently, a great deal of attention has been focused on theorems that fall outside of this neat picture, exhibiting complex reverse-mathematical and computability-theoretic behaviors. Many of these, like Ramsey's Theorem for pairs, have come from combinatorics, but model theory has also been a rich source.

I will discuss some results on the computability theory and reverse mathematics of theorems concerning basic model-theoretic notions such as atomic, homogeneous, and saturated models, including connections with combinatorial principles, and with first-order principles such as forms of induction restricted to formulas of low complexity. I will draw in particular from my recent paper "Induction, bounding, weak combinatorial principles, and the Homogeneous Model Theorem" with Karen Lange and Richard Shore.

Dinner: Morris Ramen (106 King St.) at 6PM

Spring 2018

2/20/2018 4PM, Joe Miller, UW
Title: Dimension 1 sequences are close to randoms

TBA

2/27/2018 4PM, James Hanson, UW
Title: Encoding metric structures as metric spaces

It is a classical result in model theory that arbitrary structures in finite signatures with finitely many sorts are bi-interpretable with graphs by a very explicit, effective encoding. The proof does not generalize to the context of metric structures, but as it happens, a slightly better result is true: All metric structures in countable signatures with countably many sorts are bi-interpretable with metric spaces by a very explicit, effective encoding.

3/6/2018 4PM, Iván Ongay Valverde, UW
Title: Tameness, localization and prediction numbers

After my work with Noah Schweber with the computable Cichon diagram, I was able to split the localization numbers from the prediction numbers. While doing this, I used a preservation condition that falls in the category of 'tamness conditions'.

In this talk we will talk about these 'tameness' conditions (examples are the Sacks property, Laver property and others) and how they relate to the cardinal characteristics of localization and prediction.

3/13/2018 4PM, Dan Turetsky, University of Notre Dame, Indiana
Title: Which Harrison-type orderings look most like ordinals?

By a Harrison-type ordering, we mean a computable presentation of an ill-founded linear order with no descending Δ¹₁-sequences. The order-types of such orderings are well understood, but different presentations can have different levels of 'niceness' -- that is, ways in which they resemble computable presentations of ordinals. Computable presentations of ordinals admit jump structures, and there are models of KP or even ZFC in which they are isomorphic to an ordinal. Harrison-type orderings can have some, all or none of these properties.

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

3/20/2018 4PM, Noah Schweber, UW
Title: Computability and the Axiom of Choice

Suppose we have a well-ordering ≤ of a set A. Given a family F of nonempty subsets of A, can we find a choice function for F (that is, a function mapping each set x in F to an element of x)? Classically, of course, the answer is yes: Simply pick the least element of x (in the sense of the well-ordering). However, finding this element intuitively requires both sorting through the elements of x and repeatedly asking an existential question ("Is there another element lower in the well-ordering?"). From a computability-theoretic perspective, both these tasks appear nontrivial. This raises the question:

From ≤ and F, can we compute a choice function for F?

In this talk, we'll look at this question. Right from the start we run into difficulty even phrasing the question precisely: If our underlying set A is a set of natural numbers, everything is trivially computable, and if it's not then we need to find the right notion of "compute." We'll discuss what this should be, and sketch the proof that in a precise sense, the answer to the above question is no.

4/3/2018 4PM, Jin-Yi Cai, UW
Title: Offerings from the Classification Program for Counting Problems

Suppose α and β are two angles satisfying tan(α) = r tan(β) > 0, for some rational number r > 1. Can both α and β be rational multiples of π?

Let p(x,y) = x⁵ - (2y+1) x³ - (y²+2) x² + y(y-1)x + y³. Is it true that for every integer y ≥ 4, p(x, y) is an irreducible polynomial in Q[x], whereby we can determine its Galois group?

We encounter questions like this in our quest to achieve complexity classifications for counting problems, in the world of P versus NP. In this talk I will outline a proof to the first question (using character theory), and describe at a high level how answers to such questions lead to complexity dichotomy theorems, which classify ALL problems in a complexity class as either computable in polynomial time, or as hard as #P, which is harder than NP. I will give an overview of the status of the Classification Program for Counting Problems, including all partition functions for graph homomorphisms, counting constraint satisfaction problems, and Holant problems.

4/10/2018 4PM, Tejas Bhojraj, UW
Title: Quantum Solovay randomness (specialty exam)

Martin-Löf randomness and Solovay randomness are equivalent for infinite sequences of bits: elements of 2^ω. Nies and Scholz (NS) defined quantum Martin-Löf randomness (q-MLR), a notion of randomness for infinite sequences of quantum bits (qubits). They suggested that one could define Solovay randomness in the quantum setting and asked if such a notion is equivalent to q-MLR. We define a notion of quantum Solovay randomness (q-SR) and show that it is equivalent to q-MLR. NS asked if the set of quantum Martin-Löf random states is convex. We answer this in the affirmative using the equivalence of q-MLR and q-SR and give two more applications of q-SR. I will assume familiarity with the basics of quantum randomness which I will talk about in the Logic Seminar on April 9. However, I would be happy to discuss these again if needed.

4/17/2018 (tentative) Midwest Computability Seminar, University of Chicago, Ryerson 352
Lunch: meet at the carts at Ellis and 58th around 12:30PM and walk back to Ryerson
Speakers:

2PM, Peter Cholak, University of Notre Dame, Indiana
Title: Encodable by thin sets
Let c be a coloring of n-tuples (of ω) by finitely many colors. For l less than the number of colors, a set T is l-thin iff c uses at most l colors to color all the n-tuples from T. We say a set S is RTⁿ_<∞,l-encodable iff there is a coloring c as above such that every l-thin set computes S. Wang showed that when l is "large" only the computable sets are RTⁿ_<∞,l-encodable. Dorais, Dzhafarov, Hirst, Mileti, and Shafer showed that the hyperarithmetic sets are RTⁿ_<∞,l-encodable for "small" l. Cholak and Patey showed that the arithmetic sets are RTⁿ_<∞,l-encodable for "medium" l. Of course, what is missing here is the exact definition of small, medium, and large. In the talk we will provide "tight" definitions, at least, for a "few" n. This is joint work with Ludovic Patey. Much of this will be a repeat of my talk at SEALS 2018 but there will be more material.
2:50PM, Ethan McCarthy, UW
Title: Cototal enumeration degrees and the degree spectra of minimal subshifts
A set of natural numbers is cototal if it is enumeration-reducible to its complement. The degrees of cototal sets, the cototal degrees, form an intermediate structure between the Turing degrees and the enumeration degrees. We characterize the cototal degrees as the degrees of maximal anti-chain complements on ω^<ω, the degrees of enumeration-pointed trees on 2^<ω, and the degrees of languages of minimal subshifts on 2^ω. As a corollary, we obtain a characterization of the Turing degree spectra of nontrivial minimal subshifts: they are the enumeration cones of cototal sets.
4:20PM, Joe Miller, UW
Title: A structural dichotomy in the enumeration degrees
The continuous degrees measure the computability-theoretic content of elements of computable metric spaces. They properly extend the Turing degrees and naturally embed into the enumeration degrees. Although nontotal (i.e., non-Turing) continuous degrees exist, they are all very close to total: joining a continuous degree with a total degree that is not below it always results in a total degree. We call this property "almost totality". Recently, Andrews, Igusa, Soskova and I proved that almost totality characterizes the continuous degrees inside the enumeration degrees.
In this talk, I will describe another natural structural characterization of the continuous degrees. Kalimullin introduced the notion of a K-pair in order to define the enumeration jump. K-pairs, which can be thought of as "robust minimal pairs", play a part in almost all known definability results in the enumeration degrees. Indeed, they were used to define totality, and hence almost totality. We show that the non-continuous enumeration degrees are exactly the halves of nontrivial K-pairs relative to some (total) degree. Along with the earlier definition of the continuous degrees, this gives us a structural dichotomy in the enumeration degrees.
This talk is on joint work with Ganchev, Kalimullin, and Soskova.
5:10PM, Meng-Che ("Turbo") Ho, Purdue University
Title: Finitely generated groups are universal
It is well-known that any structure can be coded in a graph. Hirschfeldt, Khoussainov, Shore, and Slinko showed that any structure can be coded in a partial ordering, lattice, integral domain, or 2-step nilpotent group, and showed that certain computability properties are preserved under this coding. Recently, Miller, Poonen, Schoutens, and Shlapentokh added fields to this list, and they gave a category-theoretic framework to establish their result. Around the same time, Montalbántroduced the notion of effective interpretation and showed that effectively bi-interpretable structures share many computability-theoretic properties. Thus, using either of these notions, we may define the notions of a class of structures being universal. Harrison-Trainor, Melnikov, Miller, and Montalbán showed that these two notions are indeed equivalent. In joint work with Harrison-Trainor, we use these ideas to define a class of structures being universal within finitely generated structures. We then use small cancellation techniques from group theory to show that the class of finitely generated groups with finitely many constants named is universal within finitely generated structures. One application of this is to the study of Scott sentences of finitely generated groups. Knight et al. showed that a finitely generated structure always have a Σ₃-Scott sentence, but most interesting classes of finitely generated groups admit d-Σ₂-Scott sentences. Using the same coding technique, Harrison-Trainor and I construct a finitely generated group that admits no d-Σ₂-Scott sentence.

Dinner: Jolly Pumpkin (5215 S. Harper Ave.) at 6:15PM

4/23/2018 3:45PM (room B231) Ethan McCarthy, UW
Title: Cototal enumeration degrees and their applications to effective mathematics (thesis defense)

The enumeration degrees measure the relative computational difficulty of enumerating sets of natural numbers. Unlike the Turing degrees, the enumeration degrees of a set and its complement need not be comparable. A set is total if it is enumeration above its complement. Taken together, the enumeration degrees of total sets form an embedded copy of the Turing degrees within the enumeration degrees. A set of natural numbers is cototal if it is enumeration reducible to its complement. Surprisingly, the degrees of cototal sets, the cototal degrees, form an intermediate structure strictly between the total degrees and the enumeration degrees. Jeandel observed that cototal sets appear in a wide class of structures: as the word problems of simple groups, as the languages of minimal subshifts, and more generally as the maximal points of any c.e. quasivariety. In the case of minimal subshifts, the enumeration degree of the subshift's language determines the subshift's Turing degree spectrum: the collection of Turing degrees obtained by the points of the subshift. We prove that cototality precisely characterizes the Turing degree spectra of minimal subshifts: The degree spectra of nontrivial minimal subshifts are precisely the cototal enumeration cones. On the way to this result, we will give several other characterizations of the cototal degrees, including as the degrees of maximal anti-chain complements on ω^<ω and as the degrees of enumeration-pointed trees on 2^<ω, and we will remark on some additional applications of these characterizations.

4/24/2018 4PM, Tamvana Makuluni, UW
Title: Complexity classifications in model theory and computable structures (thesis defense)

This talk explores three questions of complexity in model theory and computable structures. We look at the complexity of the "embeds in" relation on the isomorphism classes of at most countable groups, which we show is as complicated as second-order arithmetic. We then look at the complexity of uncountable categoricity, which we show to be complete for intersections of Π⁰₂- and Σ⁰₂-sets. Finally, we look at convex orderability, a relatively new notion of an "uncomplicated" structure in model theory. We explore what is known about convexly orderable (CO) orders. Some of the main results are that discrete CO orders can be decomposed into dense and discrete orders; the discrete orders have periodic definable sets, and the definable functions in the dense orders have nowhere dense graph.

5/1/2018 4PM, Linda Brown Westrick, University of Connecticut-Storrs
Title: How to decorate a tree

In Reverse Math, a determined Borel set consists of a Borel code (a well-founded tree, labeled with intersections, unions and clopen sets), together with the guarantee that for every X in the model, X is either in or out of the coded set (there is a witness in the model proving this). Considering the principle DPB, "Every determined Borel set has the property of Bair"', we show that DPB does not hold in the ω-model HYP. The main tool is the method of decorating an overflowed Borel code so that every hyperarithmetic X has a hyperarithmetic witness to its being in or out. We describe this method, which also forms the basis of a more general result: If M is the second-order part of an ω-model of DPB, then for every Z in M, there is a G in M such that G is hyperarithmetically generic relative to Z. Joint work with Eric Astor, Damir Dzhafarov, Antonio Montalbán, and Reed Solomon.

Dinner: Kabul Restaurant (541 State St.) at 6PM

5/29/2018 4PM, Dilip Raghavan, National University of Singapore
Title: Proof of a conjecture of Galvin

We will show that large cardinals settle a long-standing conjecture of Galvin in Ramsey theory. We will describe the background to the problem and give a sketch of the proof.

This is is joint work with Stevo Todorčević.

Dinner: Casa de Lara (341 State St.) at 6PM