Date: Sunday, October 6, 2013
Time: 11 am-4:20 pm
Place: Kemeny Hall 108, Dartmouth College
|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|
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.
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.
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.