Skip to main content
profile image
Selected Works of Timothy McNicholl
Article
Π10 classes and strong degree spectra of relations
The Journal of Symbolic Logic (2007)
  • John Chisholm, Western Illinois University
  • Jennifer Chubb, The George Washington University
  • Valentina S. Harizanov, The George Washington University
  • Denis R. Hirschfeldt, University of Chicago
  • Carl G. Jockusch, University of Illinois at Urbana-Champaign
  • Timothy McNicholl, Lamar University
  • Sarah Pingrey, The George Washington University
Download Find in your library
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 ordering. Countable  subsets of 2ω and Kolmogorov complexity play a major role in the proof.

Disciplines
Publication Date
September, 2007
DOI
10.2178/jsl/1191333852
Publisher Statement
This article is published as Chisholm, John, Jennifer Chubb, Valentina S. Harizanov, Denis R. Hirschfeldt, Carl G. Jockusch, Timothy McNicholl, and Sarah Pingrey. "Π 1 0 classes and strong degree spectra of relations." The Journal of Symbolic Logic 72, no. 3 (2007): 1003-1018. doi: 10.2178/jsl/1191333852. Posted with permission.

© Association for Symbolic Logic 2007
Citation Information
John Chisholm, Jennifer Chubb, Valentina S. Harizanov, Denis R. Hirschfeldt, et al.. "Π10 classes and strong degree spectra of relations" The Journal of Symbolic Logic Vol. 72 Iss. 3 (2007) p. 1003 - 1018
Available at: http://works.bepress.com/timothy-mcnicholl/36/