NERDS 10.0 | New England Recursion and Definability Seminar

Overview

Date: Sunday, November 6, 2016
Time: 10am-4:30pm
Place: Wellesley College, Science Center, Room E104 (Directions).

The 10th installment of the New England Recursion and Definability Seminar (NERDS) will be a joint meeting of the Mid Atlantic Mathematical Logic Seminar (MAMLS).

Travel funding is available through the NSF, via MAMLS. Please contact Karen Lange if you like to apply for it. Thank you to Arthur Apter for making this support available

Schedule

10:00-10:30	Coffee and pastries
10:30-11:30	Richard Shore (Cornell University)	Σ¹₁ in every real in a Σ¹₁ class of reals is Σ¹₁
11:40-12:10	Rachel Stahl (University of Connecticut)	Recursion Theoretic Results for the Game of Cops and Robbers on Graphs
12:10-1:40	Lunch	Bae Pao Lu Chow Dining Room
1:40-2:40	Andre Nies (University of Auckland)	Structure within the class of K-trivial sets
2:50-3:20	Rose Weisshaar (University of Notre Dame)	Comparing Notions of Effective Genericity
3:30-4:30	Brown Westrick (University of Connecticut)	Uncountable free abelian groups via \kappa-computability

Abstracts

Richard Shore

Σ¹₁ in every real in a Σ¹₁ class of reals is Σ¹₁

We first prove a theorem about reals (subsets of $\mathbb{N}$) and classes of reals: If a real $X$ is $\Sigma_{1}^{1}$ in every member $G$ of a nonempty $\Sigma_{1}^{1}$ class $\mathcal{K}$ of reals then $X$ is itself $\Sigma_{1}^{1}$. We also explore the relationship between this theorem, various basis results in hyperarithmetic theory and omitting types theorems in $\omega$-logic. We then prove the analog of our first theorem for classes of reals: If a class $\mathcal{A}$ of reals is $\Sigma_{1}^{1}$ in every member of a nonempty $\Sigma_{1}^{1}$ class $\mathcal{B}$ of reals then $\mathcal{A}$ is itself $\Sigma_{1}^{1}$. This is joint work with T. Slaman and L. Harrington.

Rachel Stahl

Recursion Theoretic Results for the Game of Cops and Robbers on Graphs

Cops and Robbers is a vertex-pursuit game played on a connected graph wherein two players, a cop and a robber, begin on a pair of vertices and alternate turns moving to adjacent vertices. A graph is cop-win if, from any pair of starting vertices, the cop can occupy the same vertex as the robber after finitely many rounds. In this talk, preliminary computability theoretic and reverse math results about the game of cops and robbers on infinite computable graphs will be discussed. We will consider several characterizations of infinite cop-win trees and graphs, and explore the complexity of winning strategies for both players.

Andre Nies

Structure within the class of K-trivial sets

The K-trivial sets are antirandom in the sense that the initial segment complexity in terms of prefix-free Kolmogorov complexity K grows as slowly as possible. Since 2002, many alternative characterisations of this class have been found: properties such as low for K, low for Martin-Löf (ML) randomness, and basis for ML randomness, which state in one way or the other that the set is close to computable.

Initially the class looked amorphous. More recently, internal structure has been found. Bienvenu et al (JEMS, 2016) showed that there is a “smart” K-trivial set, in the sense that any ML-random computing it must compute all K-trivials. Greenberg, Miller and Nies (submitted) showed that there is a dense hierarchy of subclasses. Even more recent results with Turetsky combine the two approaches via cost functions.

The talk gives an overview and ends with open questions (of which there remain many).

Rose Weisshaar

Comparing Notions of Effective Genericity

In recent work, Cholak, Dzhafarov, Hirst and Slaman showed that for $n \geq 3$, every Mathias $n$-generic computes a Cohen $n$-generic. It is natural to wonder how other types of generic objects compare to one another. We consider generics for an effective version of Hechler forcing. Adapting a method developed by Cholak, Dzhafarov, and Soskova, we show that for $n \geq 3$, every Mathias $n$-generic computes a Hechler $n$-generic, and every Hechler $n$-generic computes a Mathias $n$-generic. Finally, we explore the (open) question of whether, for $n \geq 3$, the Mathias $n$-generics and the Hechler $n$-generics occupy exactly the same Turing degrees.

Brown Westrick

Uncountable free abelian groups via \kappa-computability

One way to study structures of uncountable cardinality $\kappa$ is to generalize the notion of computation. Saying that a subset of $\kappa$ is $\kappa$-c.e. if it is $\Sigma^0_1$ definable (with parameters, in the language of set theory) over $L_\kappa$ provides the notion of $\kappa$-computability. We may also quantify over subsets of $L_\kappa$, providing a notion of a $\kappa$-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 $\kappa$ is a successor cardinal, the set of free abelian groups of size $\kappa$ is $\Sigma^1_1$-complete. If $\kappa$ is the successor of a regular cardinal which is not weakly compact, there is a computable free abelian group of cardinality $\kappa$, all of whose bases compute $\emptyset”$, and this is the best coding result possible. The resolution of questions of this type is more complex for other $\kappa$, and a few questions remain open. This is joint work with Greenberg and Turetsky.