The ${\Sigma }_2$ theory of ${\mathcal{D}}_h({\le }_h\mathcal{O})$ as an uppersemilattice with least and greatest element is decidable

Abstract

We establish the decidability of the ${\Sigma }_2$ theory of ${\mathcal{D}}_h({\le }_h\mathcal{O})$, the hyperarithmetic degrees below Kleene's $\mathcal{O}$, in the language of uppersemilattices with least and greatest element. This requires a new kind of initial-segment result and a new extension of embeddings result both in the hyperarithmetic setting.