The Foundational Impact of Recursion Theory

University of Connecticut at Storrs
May 22, 2016


• Set-theoretic interpretations below $\text{ATR}_0$

François G. Dorais
University of Vermont

Simpson has shown that $\text{ATR}_0$ has a natural set-theoretic interpretation called $\text{ATR}_0^{\text{set}}$. Consequently, subsystems of second order arithmetic extending $\text{ATR}_0$ also have set-theoretic interpretations. In this talk, we will discuss a refinement of this interpretation which gives a natural set-theoretic interpretation of subsystems of $\text{ATR}_0$ all the way down to $\text{ACA}_0^+$. Remarkably, the new set-theoretic system, which is called $\text{PROVI}$, was first discovered by Mathias — without any concern for second order arithmetic — in order to distill the axioms of set theory that are essential to make set-forcing work. We will see how this new correspondence highlights and clarifies the connection between transfinite recursion in second order arithmetic and in set theory. We will also discuss connections with higher order arithmetic and other subsystems of set theory.

Joint work with A. R. D. Mathias.

• The Logic of Graph Decompositions

Stephen Flood
Bridgewater State University

We will use reverse mathematics and computability theory to study the theory of simplicial graph decompositions. This area of graph theory studies the graphs that can be built by pasting irreducible graphs together at complete subgraphs. Many of the classical definitions refer to arbitrary ordinal lengths, and many classical proofs use Zorn's lemma.

We will characterize the strength of one existence theorem, known as Halin's Theorem, by eliminating the use of Zorn's lemma from its proof. This will allow us to prove that Halin's theorem is equivalent to $\text{ACA}_0.$ We will also compare the ordinal lengths of different classes of graphs. This will allow us to study the complexity of the index sets for these classes of graphs.

• Effectiveness and strength of Hindman's theorem for bounded sums

Carl Jockusch
University of Illinois at Urbana-Champaign

I will discuss joint work with Damir Dzhafarov, Reed Solomon, and Linda Brown Westrick. Hindman's Theorem HT asserts that whenever the positive integers are colored with finitely many colors there is an infinite set X of positive integers such that all nonempty finite sums of distinct elements of X have the same color. It was shown by A. Blass, J. Hirst, and S. Simpson in 1987 that HT implies $\text{ACA}_0$ and follows from $\text{ACA}_0^+$ in $\text{RCA}_0.$ We consider weaker versions of HT in which the length of the sums has a specified finite bound. We show from corresponding results in computability theory that HT for 2 colors and sums of length at most 2 implies $\text{SRT}^2_2$ (Stable Ramsey's Theorem for 2-colorings of pairs) and that HT for 3 colors and sums of length at most 3 implies $\text{ACA}_0$ in $\text{RCA}_0.$ I will also mention several open questions.

• Many-one degrees with names like John or Paul

Antonio Montalbán
University of California, Berkeley

We prove a version of the uniform Martin's conjecture for functions from Turing degrees to many-one degrees. We will talk about some other somewhat connected new results on topics like Fraisse's conjecture and analytic equivalence relations.

The part on many-one degrees is joint with Kihara and Slaman.

• The weakness of Ramsey's theorem under omniscient reductions

Ludovic Patey
Université Paris Diderot (VII)

A problem $P$ is strongly omnisciently computably reducible to another problem $Q$ if for every $P$-instance $X$, there is a $Q$-instance $Y$ such that every solution to $Y$ computes a solution to $X$. In other words, identifying a $P$-instance to the mass problem $\{ Z : Z \text{ is a solution to X} \}$ and seeing $P$ as a collection of Muchnik degrees, $P$ is strongly omnisciently computably reducible to $Q$ if every $d$ in $P$ is Muchnik below some $e$ in $Q$. In this talk, we shall emphasize that strong omniscient computable reduction is a natural notion revealing deep structural differences between variants of Ramsey's theorem and Konig's lemma.

• A tour of the mass problems

Paul Shafer
University of Ghent

We give a brief tour of the degrees of unsolvability of mass problems.

• The Muchnik degrees of nonempty $\Pi_{1}^{0}$ classes are dense

Richard Shore
Cornell University

Let $\mathcal{E}_{w}$ and $\mathcal{S}_{w}$ be the lattices of nonempty $\Pi_{1}^{0}$ subclasses of $\{0,1\}^{\mathbb{N}}$ and $\mathbb{N}^{\mathbb{N}},$ respectively, under Muchnik reducibility $\leq_{w}.$ Recall that for subclasses $P$ and $Q$ of $\{0,1\}^{\mathbb{N}}$ or $\mathbb{N}^{\mathbb{N}}$ we say that $P$ is Muchnik reducible to $Q$, $P\leq _{w}Q,$ if for every $Y\in Q,$ there is an $X\in P$ such that $X\leq_{T}Y,$ i.e. every member of $Q$ computes a member of $P.$ The Muchnik degrees are defined as usual as the equivalence classes of this reducibility. The two structures (for $\{0,1\}^{\mathbb{N}}$ and $\mathbb{N}^{\mathbb{N}}$) are distributive lattices with many other known structural properties. There are many connections between $\mathcal{E}_{T},$ the usl of r.e. Turing degrees, and $\mathcal{E}_{w}$ including a natural embedding of $\mathcal{E}_{T}$ into $\mathcal{E}_{w}.$ We extend the analogies by showing that both $\mathcal{E}_{w}$ and $\mathcal{S}_{w}$ are dense. Our proof uses methods from both the Turing degrees and hyperarithmetic theory.

This is joint work with Stephen Simpson and Stephen Binns.

• Recursion Theory and Diophantine Approximation

Ted Slaman
University of California, Berkeley

Recursion Theory deals with the definability of sets, especially sets of natural numbers or equivalently real numbers. Diophantine Approximation deals with the approximation of real numbers by rational numbers, which can be viewed as a number theoretic form of definability. We will discuss connections between these areas.