# Blog Archives

These are the items posted in this seminar, currently ordered by their post-date, rather than by the event date. We will create improved views in the future. In the meantime, please click on the Seminar menu item above to find the page associated with this seminar, which does have a more useful view order.# Ramsey’s Theorem applied to infinite traceable graphs

We consider three applications of Ramsey’s Theorem to infinite traceable graphs and finitely generated lattices from the point of view of reverse mathematics. For two of the applications, we will show that Ramsey’s Theorem is necessary while for the third application, it is not necessary. We will conclude with some related open questions.

# Computability theoretic properties of isomorphisms between partial computable injection structures

A partial computable injection structure consists of a computable set of natural numbers and a partial computable, injective (1-1) function. Clearly, the isomorphism type of such a structure is determined by the kinds and number of orbits of the elements under the function application. First, we investigate partial computable injection structures always having computable isomorphisms to other isomorphic structures, and we analyze what goes wrong in structures without such computable isomorphisms. Additionally, we do the same for partial computable injection structures under Δ_{2}-isomorphisms and Δ_{3}-isomorphisms.

# NERDS

The Autumn 2014 meeting of NERDS, the New England Recursion & Definability Seminar, will take place on Saturday, October 18 at Assumption College, in Worcester, MA, beginning at 10:30 a.m. The principal organizers are Brooke Andersen, Damir Dzhafarov, and Reed Solomon. All talks are posted on nylogic.org (find NERDS under the “Conferences” tab), and they will take place in the Carriage House building on the campus of Assumption College. Directions.

# Notions of robust information-coding

We study several notions of computability-theoretic reducibility between subsets of natural numbers that are “robust” in the following sense: given a notion of largeness, a set $B$ is reducible to a set $A$ if every set that agrees with $A$ on a large domain uniformly computes a set that agrees with $B$ on a large domain. A familiar example is 1-reducibility, for which “large” can be taken to mean “cofinite”. This framework encompasses a wide range of reducibilities, including generic reducibility, for which “large” means “of density 1,” and which was first studied by Jockusch and Schupp. We obtain some new results concerning this reducibility, and introduce several related reducibilities that behave quite counterintuitively. For instance, infinite-information reducibility, for which “large” simply means “infinite”, enjoys the unusual property of admitting maximal pairs. I will discuss this and other results about these reducibilities, and sketch some of the techniques needed to prove them. This is joint work with Greg Igusa.

# Quasiminimality and computability

We briefly define computability on uncountable domains via Σ_{1}-recursion, with an emphasis on ω_{1}-computability. We will then apply this notion of uncountable computability to quasiminimal excellent classes. We will concentrate on the pseudo-exponential fields and the topological group covers of the complex numbers. We show that the group covers are relatively ω_{1}-computably categorical while the pseudo-exponential fields are not even ω_{1}-computably categorical.

# Spectra of differentially closed fields

The spectrum Spec(_{0} is isomorphic to a computable one. The latter theorem (which relativizes, to give the main result above) resembles the famous result of Downey and Jockusch on Boolean algebras, but the proof is different, yielding a Δ_{2} isomorphism between the low model and its computable copy; moreover, our first theorem shows that the extension of the result to the low_{4} case for Boolean algebras does not hold for _{0}.

This is joint work by Dave Marker and the speaker.