It has long been recognized that the existence of an interpretation of one countable structure B in another one A yields a homomorphism from the automorphism group Aut(A) into Aut(B). Indeed, it yields a functor from the category Iso(A) of all isomorphic copies of A (under isomorphisms) into the category Iso(B). In traditional model theory, the converse is false. However, when we extend the concept of interpretation to allow interpretations by L_ω1ω formulas, we find that now the converse essentially holds: every Borel functor arises from an infinitary interpretation of B in A, and likewise every Borel-measurable homomorphism from Aut(A) into Aut(B) arises from such an interpretation. Moreover, the complexity of an interpretation matches the complexities of the corresponding functor and homomorphism. We will discuss the concepts and the forcing necessary to prove these results and other corollaries.

One way to study structures of uncountable cardinality κ is to generalize the notion of computation. Saying that a subset of κ is κ-c.e. if it is Σ⁰₁ definable (with parameters, in the language of set theory) over L_κ provides the notion of κ-computability. We may also quantify over subsets of L_κ, providing a notion of a κ-analytic set (here we assume V=L). In this setting, we consider the difficulty of recognizing free groups and the complexity of their bases. For example, if κ is a successor cardinal, the set of free abelian groups of size κ is Σ¹₁-complete. If κ is the successor of a regular cardinal which is not weakly compact, there is a computable free abelian group of cardinality κ, all of whose bases compute ∅”, and this is the best coding result possible. The resolution of questions of this type is more complex for other κ, and a few questions remain open. This is joint work with Greenberg and Turetsky.

Remmel showed that a computable linear order L is computably categorical if and only if the order type of L has only a finite number of successivities. As part of the proof, Remmel assumes that L has infinitely many successivities and constructs another computable linear order R, which is not computably isomorphic to L, and a Δ⁰₂-isomorphism f such that f is an isomorphism from L onto R. Hence showing that L is not computably categorical. In this talk I will discuss the conditions under which we can use permitting arguments to construct f below certain types of Δ⁰₂ degrees.

You can make a simple family tree by starting with a person at the root and then adding two branches for her parents, and then adding two branches for the parents of each of her two parents, and so on. Such a family tree is an example of a binary tree because each level of the tree has at most two branches. We’ll see that every binary tree with infinitely many nodes has an infinite path. But can we actually *compute* a path, given that we can prove one exists? Answering this question requires us to carefully define the verb “to compute.” This talk will highlight ideas from graph theory, theoretical computer science, and logic, but no background in any of these subjects is necessary.

This talk is aimed primarily at undergraduates.

We will use computability theory to investigate the difficulty of two standard questions from algebra. First, given a field F and a polynomial p∈ F[X], does the equation p=0 have a solution in F? And second, is p(X) irreducible in F[X]? Obviously these two questions are related, but it is not immediately clear which one is more difficult to answer. Indeed, it is not clear how one should measure the “difficulty” of answering these questions.

To address this problem, we will consider computable fields, which are countable fields in which we have algorithms for listing all the field elements and for the basic field operations. It has been known since 1960 that in this context, the two questions are equivalent under the standard notion of Turing reducibility: an algorithm for answering either question can be used to give an algorithm for answering the other one. However, computability theory also provides more precise measures of difficulty, and using one of these measures, known as 1-reducibility, we will show that one of the two questions can definitively be said to be more difficult in general than the other. To find out which is which, come to the talk!

For a ring R, Hilbert’s Tenth Problem is the set HTP(R) of polynomials f ∈ R[X₁,X₂,…] for which f=0 has a solution in R. Matiyasevich, completing work of Davis, Putnam, and Robinson, showed that HTP(Z) is Turing-equivalent to the Halting Problem. The Turing degree of HTP(Q) remains unknown. Here we consider the problem for subrings of Q. One places a natural topology on the space of such subrings, which is homeomorphic to Cantor space. This allows consideration of measure theory and also Baire category theory. We prove, among other things, that HTP(Q) computes the Halting Problem if and only if HTP(R) computes it for a nonmeager set of subrings R.

We will consider several number-theoretic questions which arise from computable model theory. One of these, recently solved by Poonen, Schoutens, Shlapentokh, and the speaker, involves attempting to “embed” a graph into a field: given a graph, one wishes to construct a field with the exact same computable-model-theoretic properties as the graph. (For instance, the automorphisms of the graph should correspond to the automorphisms of the field, by a bijective functorial correspondence which preserves the Turing degree of each automorphism.) Another arises out of consideration of Hilbert’s Tenth Problem for subrings of the rationals: we ask for subrings in which Hilbert’s Tenth Problem is no harder than it is for the rationals themselves. This is known for semilocal subrings, and Eisenträger, Park, Shlapentokh and the speaker have shown that it holds for certain non-semilocal subrings as well, but it remains open whether one can invert “very few” primes and still have it hold. We will explain this problem and discuss the number-theoretic question which arises out of it.

I will talk about a few different results about the Scott ranks of models of a theory. (By a theory, I mean a sentence of L_ω1ω.) These results are all related in that they all follow from the same general construction; this construction takes a pseudo-elementary class C of linear orders and produces a theory T such that the Scott ranks of models of T are related to the well-founded parts of linear orders in C.

The main result is a descriptive-set-theoretic classification of the collections of ordinals which are the Scott spectrum of a theory. We also answer some open questions. First, we show that for each ordinal β, there is a Π₂⁰ theory which has no models of Scott rank less than β. Second, we find the Scott height of computable infinitary sentences. Third, we construct a computable model of Scott rank ω₁^CK+1 which is not approximated by models of low Scott rank.

Simple, hypersimple, hyperhypersimple, and maximal sets play an important role in computability theory. Maximal sets are co-atoms in the lattice of computably enumerable sets modulo finite sets. Soare established that they are automorphic in this lattice. Similarly, maximal vector spaces play an important role in the study of the lattice of computably enumerable vector spaces modulo finite dimension. We will investigate principal filters determined by maximal spaces and how algebraic structure interacts with computability-theoretic properties. We will discuss the problem of finding orbits of maximal spaces under lattice automorphisms, the development of various notions of maximality for vector spaces, and recent progress that is joint work with R. Dimitrov.

A locally finite computable graph G is called A-computable if A can compute the neighbors of the vertices of G. William Gasarch and Andrew Lee introduced this notion to study graphs that are “between” computable and highly computable (i.e., ∅-computable). For any noncomputable c.e. set A, they proved that the A-computable graphs behave just like computable graphs when it comes to colorings. In this talk, we will see that their result also works for Euler paths and domatic partitions. Although it does not extend to arbitrary sets A (that are not necessarily c.e.), we will classify the sets for which it does.

The degree spectrum of a countable structure is the set of all Turing degrees of isomorphic copies of that structure. This topic has been widely studied in computable model theory. Here we examine the possible degree spectra of real closed fields, finding them to offer far more complexity than the related theory of algebraically closed fields. The co-author of this project, Victor Ocasio Gonzalez, showed in his dissertation that, for every linear order L, there exists a real closed field whose spectrum is the pre-image under jump of the spectrum of L. We add further results, distinguishing the cases of archimedean and non-archimedean real closed fields, and splitting the latter into two subcases based on the existence of a least multiplicative class of positive nonstandard elements. If such a class exists, then finiteness in the field is always decidable, but the case with no such class proves more interesting.

Symmetry breaking involves the coloring of elements of a structure so that the only automorphism of the structure which respects the coloring is the trivial one. We investigate how much information we would need to be able to compute a 2-coloring of a computable finite-branching tree under the predecessor function which eliminates all automorphisms except the trivial one; we also generalize to n-colorings for fixed n and for variable n. Then, we suppose the tree is no longer finite branching, and we observe what happens to the difficulty of computing a 2-coloring.