Lattice initial segments of the hyperdegrees

We affirm a conjecture of Sacks [1972] by showing that every countable distributive lattice is isomorphic to an initial segment of the hyperdegrees, $mathcal{D}_{h}$. In fact, we prove that every sublattice of any hyperarithmetic lattice (and so, in particular, every countable locally finite lattice) is isomorphic to an initial segment of $mathcal{D}_{h}$. Corollaries include the decidability of the two quantifier theory of $% mathcal{D}_{h}$ and the undecidability of its three quantifier theory. The key tool in the proof is a new lattice representation theorem that provides a notion of forcing for which we can prove a version of the fusion lemma in the hyperarithmetic setting and so the preservation of $omega _{1}^{CK}$. Somewhat surprisingly, the set theoretic analog of this forcing does not preserve $omega _{1}$. On the other hand, we construct countable lattices that are not isomorphic to an initial segment of $mathcal{D}_{h}$.

The Strength of Some Combinatorial Principles Related to Ramseys Theorem for Pairs

We study the reverse mathematics and computability-the-o-re-tic strength of (stable) Ramseys Theorem for pairs and the related principles COH and DNR. We show that SRT$^2_2$ implies DNR over RCA$_0$ but COH does not, and answer a question of Mileti by showing that every computable stable $2$-coloring of pairs has an incomplete $Delta^0_2$ infinite homogeneous set. We also give some extensions of the latter result, and relate it to potential approaches to showing that SRT$^2_2$ does not imply RT$^2_2$.

The Strength of the Gratzer-Schmidt Theorem

The Gratzer-Schmidt theorem of lattice theory states that each algebraic lattice is isomorphic to the congruence lattice of an algebra. We study the reverse mathematics of this theorem. We also show that the set of indices of computable lattices that are complete is $Pi^1_1$-complete; the set of indices of computable lattices that are algebraic is $Pi^1_1$-complete; the set of compact elements of a computable lattice is $Pi^{1}_{1}$ and can be $Pi^1_1$-complete; and the set of compact elements of a distributive computable lattice is $Pi^{0}_{3}$, and there is an algebraic distributive computable lattice such that the set of its compact elements is $Pi^0_3$-complete.

Finding subsets of positive measure

An important theorem of geometric measure theory (first proved by Besicovitch and Davies for Euclidean space) says that every analytic set of non-zero $s$-dimensional Hausdorff measure $mathcal H^s$ contains a closed subset of non-zero (and indeed finite) $mathcal H^s$-measure. We investigate the question how hard it is to find such a set, in terms of the index set complexity, and in terms of the complexity of the parameter needed to define such a closed set. Among other results, we show that given a (lightface) $Sigma^1_1$ set of reals in Cantor space, there is always a $Pi^0_1(mathcal{O})$ subset on non-zero $mathcal H^s$-measure definable from Kleenes $mathcal O$. On the other hand, there are $Pi^0_2$ sets of reals where no hyperarithmetic real can define a closed subset of non-zero measure.