Strong enumeration reducibilities
This paper discusses various enumeration reducibilities, with primary emphasis on \(s\)-reducibility. Let \(L\) denote the structure of \(s\)-degrees below \({\mathbf 0}'_s\) (equivalently, the \(\Sigma_2^0\) \(s\)-degrees). The authors prove that a countable atomless Boolean algebra (and hence any countable distributive lattice) is embeddable in \(L\). On the other hand, they show that \(L\) itself is not distributive by embedding the nondistributive lattice \(N_5\) in it. The authors also prove that \(L\) is upwards dense -- indeed, for any \(s\)-degree \({\mathbf a}<{\mathbf 0}'_s\), every countable partial order is embeddable between \({\mathbf a}\) and \({\mathbf 0}'_s\).
scientific article; zbMATH DE number 5070977
scientific article