Strong enumeration reducibilities (Q850805)

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\).