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.
NERDS: New England Recursion & Definability SeminarSaturday, October 18, 20143:20 pmAssumption College, Worcester, MA

Reed Solomon

Ramsey’s Theorem applied to infinite traceable graphs

University of Connecticut

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.

NERDS: New England Recursion & Definability SeminarSaturday, October 18, 20142:00 pmAssumption College, Worcester, MA

Leah Marshall

Computability theoretic properties of isomorphisms between partial computable injection structures

George Washington University

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: New England Recursion & Definability SeminarSaturday, October 18, 2014Assumption College, Carriage House

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.

NERDS: New England Recursion & Definability SeminarSunday, March 30, 201411:00 amAcademic Center, Room 113, Olin College

Damir Dzhafarov

Notions of robust information-coding

University of Connecticut

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.

NERDS: New England Recursion & Definability SeminarSunday, March 30, 20142:00 pmAcademic Center, Room 113, Olin College

Jesse Johnson

Quasiminimality and computability

Westfield State University

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.

NERDS: New England Recursion & Definability SeminarSunday, March 30, 20143:15 pmAcademic Center, Room 113, Olin College

Russell Miller

Spectra of differentially closed fields

City University of New York

The spectrum Spec(M) of a countable structure M is the set of all Turing degrees of structures isomorphic to M. This topic has been the focus of much research. Here we describe the spectra of countable differentially closed fields of characteristic 0: they are precisely the preimages { d : d’ ∈ Spec(G) } of spectra of arbitrary countable graphs G, under the jump operation. To establish this, we describe the proofs of two theorems: one showing how to build the appropriate differential field K from a given graph G, and the other showing that every low model of the theory DCF0 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 low4 case for Boolean algebras does not hold for DCF0.

This is joint work by Dave Marker and the speaker.