Skip to main content
Π01 Classes and Strong Degree Spectra of Relations
  • John Chisholm
  • Jennifer Chubb, University of San Francisco
  • Valentina S. Harizanov
  • Denise R. Hirschfeldt
  • Carl G. Jockusch
  • Timothy H. McNicholl
  • Sarah Pingrey
Document Type
Publication Date
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 2w and Kolmogorov complexity play a major role in the proof.

Preprint. Article published in Journal of Symbolic Logic 72 (2007) 1003–1018.

Citation Information
John Chisholm, Jennifer Chubb, Valentina S. Harizanov, Denise R. Hirschfeldt, et al.. "Π01 Classes and Strong Degree Spectra of Relations" (2007)
Available at: