Π<sub>1</sub><sup>0</sup> classes and strong degree spectra of relations
Π<sub>1</sub><sup>0</sup> classes and strong degree spectra of relations
Abstract We study the weak truth-table and truth-table degrees of the images of subsets of computable structures under isomorphisms between computable structures. In particular, we show that there is a low c.e. set that is not weak truth-table reducible to any initial segment of any scattered computable linear ordering. Countable …