Overview

Date: Sunday, October 6, 2013
Time: 11 am-4:20 pm
Place: Kemeny Hall 108, Dartmouth College

Schedule

11:00–11:30	Coffee and snacks (Kemeny Hall 300)
11:30–12:30	David Belanger (Cornell University)	Saturated models and disjunctions in second-order arithmetic
12:30–2:00	Lunch and discussion time (Kemeny Hall 300)
2:00–3:00	Stephen Flood (University of Connecticut)	Paths, trees and the computational strength of some Ramsey-like theorems, Room 108 Kemeny
3:00–4:00	Damir Dzhafarov (University of Connecticut)	Limits to joining with generics and randoms

Abstracts

David Belenger

We look at the reverse-mathematical strength of the existence theorem for countable saturated models of a countable theory, formalized in second-order arithmetic. As it turns out, this theorem admits more than one formalization, each with its own degree of strength. One of these leads us to a curious family of statements whose best proof, from a reverse-mathematical point of view, requires a disjunction of two well- known axioms–in this case, Weak Konig’s Lemma and the induction principle for $\Sigma^0_2$ formulas.

Stephen Flood

Ramsey’s theorem states that each coloring has an infinite homogeneous set, but these sets can be arbitrarily spread out. Paul Erdos and Fred Galvin proved that for each coloring $f$, there is an infinite set that is “packed together” which is given “a small number” of colors by $f$. In this talk, we will give the precise statement of this packed Ramsey’s theorem, and discuss its computational and reverse mathematical strength. We will also discuss a related combinatorial principle called $RKL$ which combines features of Weak Konig’s Lemma and Ramsey’s Theorem. We will give a precise statement of this principle and two of its generalizations, and discuss their reverse mathematical strength.

Damir Dzhafarov

It is a fundamental theorem of computability theory that the Turing jump of a set A always has strictly greater Turing degree than A itself, i.e., $deg(A) 1$. Our result applies generally to many other forcing notions commonly used in computability theory. I will also mention a variant of our result, showing that the set $G$ cannot be chosen to be $2$-random.