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

Comments

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: http://works.bepress.com/timothy-mcnicholl/20/