Π01 Classes and Strong Degree Spectra of RelationsMathematics
AbstractWe 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 2w and Kolmogorov complexity play a major role in the proof.
Citation InformationJohn Chisholm, Jennifer Chubb, Valentina S. Harizanov, Denise R. Hirschfeldt, et al.. "Π01 Classes and Strong Degree Spectra of Relations" (2007)
Available at: http://works.bepress.com/timothy-mcnicholl/20/