Pi01 Classes and Strong Degree Spectra of Relations

by John Chisholm, Jennifer Chubb , Valentina S. Harizanov, Denis R. Hirschfeldt, Carl G. Jockusch, Jr., Timothy McNicholl, and Sarah Pingrey

Status: Journal of Symbolic Logic 72 (2007) 1003 - 1018.

Availability: PostScript, DVI, and PDF

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.