# 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.# Comparing notions of effective genericity

In recent work, Cholak, Dzhafarov, Hirst and Slaman showed that for *n ≥ 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 ≥ 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 ≥ 3*, the Mathias *n*-generics and the Hechler *n*-generics occupy exactly the same Turing degrees.

# Uncountable free abelian groups via κ-computability

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 Σ^{0}_{1} 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 Σ

^{1}

_{1}-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.

# 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.

# 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.

# Σ11 in every real in a Σ11 class of reals is Σ11

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

# Autumn 2016 NERDS at Wellesley College

The Autumn 2016 meeting of NERDS, the New England Recursion and Definability Seminar, will take place on Sunday, November 6 at Wellesley College, in Wellesley, MA. Details are available from the NERDS website, and talks are also posted here on nylogic.org.

# Randomness and Fourier series

Carleson’s Theorem states that the Fourier series of certain integrable functions converge almost everywhere. I will consider this theorem in the context of computable analysis and show that the points that satisfy Carleson’s Theorem are precisely the Schnorr random points. This work is joint with Timothy H. McNicholl and Jason Rute.

# Density and computability

We develop and discuss some of the theory relating asymptotic density and computability, with attention to the inherent complexity of sets with density invariant under computable permutation. We will make a brief excursion into reverse mathematics on the way, pointing out that a key equivalence of Kjos-Hanssen, Merkle, and Stephan holds over **RCA _{0}**.

# A one-generic that does not compute a modulus for one-genericity

A function *g ∈ 2 ^{ω}* is 1-generic if, for every recursively enumerable

*W⊂ 2*, there is some

^{< ω}*σ⊂ g*such that either

*σ∈W*or σ has no extensions in

*W*. That is, any possible Σ

^{0}

_{1}property of

*g*is either forced to be true or forced to be false by some finite initial segment of

*g*. A function

*f∈ω*is a modulus for 1-genericity if, whenever

^{ω}*h*pointwise dominates

*f*, then

*h*computes some 1-generic. If

*g*is 1-generic and either Δ

^{0}

_{2}-definable or 2-generic, then

*g*computes a modulus for 1-genericity. We give a priority argument to produce a 1-generic

*g*that does not compute a modulus for 1-genericity.

(Joint work with Theodore A. Slaman.)

# Computable categoricity, linear orders and permitting

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 Δ^{0}_{2}-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 Δ^{0}_{2} degrees.

# Climbing (or finding paths) through trees

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.

# NERDS on April 2, 2016

The Spring 2016 New England Recursion and Definability Seminar (“NERDS”) will take place on Saturday, April 2, 2016 at Springfield College, in Springfield, MA. Further details and abstracts of talks will be posted on nylogic.org as they become available.

# The interplay of classes of algorithmically random objects

We study algorithmically random closed subsets (RCS’s) of Cantor space, algorithmically random continuous functions (RCF’s) from Cantor space to Cantor space, and algorithmically random Borel probability measures on Cantor space; especially the interplay between the three. Our main tools are preservation of randomness (PoR) and its converse no randomness ex nihilo (NREN), which say together that given an a.e.-defined computable map between an effective probability space and an effective polish space, a real is (Martin-Löf) random for the pushforward measure if and only if its preimage is random for the domain’s measure. PoR and NREN allow us to prove new facts that were previously open and reprove some known results more simply. Example 1: it was known that every RCS contains a random real and that every random real is contained in some RCS; we reprove this using PoR and NREN. Example 2: It was shown previously that the zero set (that is, the preimage of the sequence of all 0’s) of a RCF is a RCS. We reprove this using PoR and get the converse, which was previously left open, that ever RCS is the zero set of some RCF, via NREN. We also prove some miscellaneous results about the individual objects. Example 3: the Lebesgue measure of the range of a RCF is strictly between 0 and 1. This work is joint with Chris Porter.

# Computably enumerable sets and vector spaces with thin complements

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.

# Computing uniform (metastable) rates of convergence from the statement of the theorem alone

Consider a convergence theorem of the following form.

(T): If the property P holds, then the sequence (*x _{n}*) converges.

For example, the monotone convergence principle states that any monotone, bounded sequence of reals converges.

This talk concerns the notion of metastable rates of convergence. The advantage of this notion is that metastable rates are often uniform and computable. Kohlenbach, using proof theory, showed that if the property P is of a certain form and the theorem (T) is provable in a certain formal type theory, then the rate of metastable convergence is both uniform and computable. Avigad and Iovino, using model theory, showed that if the theorem (T) is true and the property P is preserved by ultraproducts, then the rate of metastable convergence is uniform (no mention of computability). In this result, using computable analysis and computable continuous model theory, we show that if (T) is true and P is axiomatizable in continuous logic, then the corresponding metastable bounds are both uniform and computable from P. This generalizes both of the previous results.

# A-Computable Graphs

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.

# NERDS October 17, 2015 at Assumption College

The 2015 autumn meeting of the New England Recursion & Definability Seminar will be held on the campus of Assumption College, in Worcester Massachusetts, on Saturday, October 17, from 10:00 until 4:15. Titles and abstracts are now posted at the link for NERDS, under the Seminars tab. Directions and visitor information are available here.

# The implicitly constructible universe

The implicitly constructible universe, **IMP**, defined by Hamkins and Leahy, is produced by iterating implicit definability through the ordinals. **IMP** is an inner model intermediate between **L** and **HOD**. We look at some consistency questions about the nature of **IMP**.

# The degree spectra of orders on a computable Abelian group

For any computable abelian group, the collection of possible linear orderings on the group can be represented as a Π^{0}_{1} class. However, not all Π^{0}_{1} classes can occur in this way, and we investigate the possible Turing degrees of their members. First, we describe the connection between orders for a group and bases for the group. Additionally, we extend a previously known result regarding the Turing degrees not represented in the space of orders of some group.

# Low for omega and equivalence class isomorphism properties

We look at the property of being low for isomorphism, restricted to certain classes of structures – if *C* is a class of structures, a set *D* is low for *C* isomorphism iff for any two structures in *C*, if *D* computes an isomorphism between them then there is a computable isomorphism between them. In particular we will show that exactly those sets which cannot compute non-zero Δ_{2} degrees are low for ω-isomorphism (when ω is viewed purely as an order), and we will show that no set which computes a non-zero Δ_{2} set or which computes a separating set for any two computably inseparable c.e. degrees is low for equivalence class isomorphism.