Abstracts
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.
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.
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.
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.
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.
Paul Shafer
University of Ghent
We give a brief tour of the degrees of unsolvability of mass problems.
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.
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.