Blog ArchivesThese 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.
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.
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 Σ01 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 Σ11-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.
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.
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.
We first prove a theorem about reals (subsets of N) and classes of reals: If a real X is Σ11 in every member G of a nonempty Σ11 class K of reals then X is itself Σ11. 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 Σ11 in every member of a nonempty Σ11 class B of reals then A is itself Σ11. This is joint work with T. Slaman and L. Harrington .
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.
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.
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 RCA0.
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 Σ01 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 Δ02-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.)
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 Δ02-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 Δ02 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.
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.
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.
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.
Consider a convergence theorem of the following form.
(T): If the property P holds, then the sequence (xn) 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 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 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, 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.
For any computable abelian group, the collection of possible linear orderings on the group can be represented as a Π01 class. However, not all Π01 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.
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.