Π01 Classes and Strong Degree Spectra of
Relations
Status: published in the Journal
of Symbolic Logic 72 (2007) 1003 - 1018.
Availability: journal
version and preprint
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 order. Countable
Π01 subsets of
2ω and Kolmogorov complexity play a major role in the
proof.
drh@math.uchicago.edu