Extensions of embeddings below computably enumerable degrees (Q2838113)

In this paper the authors study the decidability problem for the \(\forall\exists\)-fragment of \(\mathrm{Th}({\mathcal D}_{(\leq {\mathbf 0}')},\leq,\vee)\), which is the only problem left open for the structure \(({\mathcal D}_{(\leq {\mathbf 0}')},\leq,\vee)\). It is in fact known that the \(\exists\)-fragment is decidable, while the \(\exists\forall\exists\)-fragment is undecidable. The structure \(\langle{\mathcal D}_{(\leq {\mathbf 0}')},\leq,\vee\rangle\) is one of the most important structures studied in computability theory and the decision problem for its \(\forall\exists\)-fragment is very difficult. The authors analyze the decision problem for the \textit{extensions-of-embedding problem} \(\mathbb E\) for the structure \(\langle{\mathcal D}_{(\leq {\mathbf 0}')},\leq,\vee\rangle\), where \({\mathbb E}:=\{({\mathcal P},{\mathcal Q}): {\mathcal P},{\mathcal Q}\) are finite upper semilattices with \({\mathcal P}\subseteq{\mathcal Q}\) such that every usl-embedding of \({\mathcal P}\) into \(\langle{\mathcal D}_{(\leq {\mathbf 0}')},\leq,\vee\rangle\) can be extended to an embedding of \({\mathcal Q}\) into \(\langle{\mathcal D}_{(\leq {\mathbf 0}')},\leq,\vee\rangle\}\). NEWLINENEWLINEThe paper is divided into seven sections. The first section contains a well-written historical background on the extensions-of-embedding problem, and it contains also a useful planning of the results shown in the remaining sections. The paper does not contain a solution of the decision problem for \(\mathbb E\). However, the authors produce a rich collection of advanced results that should provide new ideas in the search for a solution to the decision problem both for \(\mathbb E\) and the \(\forall\exists\)-fragment of \(\mathrm{Th}({\mathcal D}_{(\leq {\mathbf 0}')},\leq,\vee)\). In particular, they generalize Posner's Theorem to any non-generalized low\(_2\) degree, namely: given any non-\(\mathrm{GL}_2\) degree \({\mathbf c}\) and given any non-zero degree \({\mathbf a}<{\mathbf c}\), there is some degree \({\mathbf x}<{\mathbf c}\) such that \({\mathbf a}\vee{\mathbf x}={\mathbf c}\).