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.

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.

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.

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_ω1,ω-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.

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.

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.

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.

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.

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.

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.

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^<ω).

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.

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.