$\Pi _{1}^{0}$ Classes and Strong Degree Spectra of Relations

, , , , , &
Journal of Symbolic Logic 72 (3):1003 - 1018 (2007)
  Copy   BIBTEX

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 $\Pi _{1}^{0}$ subsets of 2ω and Kolmogorov complexity play a major role in the proof

Categories

Keywords

Reprint years

DOI

10.2178/jsl/1191333852

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 99,362

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Degree spectra of relations on structures of finite computable dimension.Denis R. Hirschfeldt - 2002 - Annals of Pure and Applied Logic 115 (1-3):233-277.
Hypersimplicity and semicomputability in the weak truth table degrees.George Barmpalias - 2005 - Archive for Mathematical Logic 44 (8):1045-1065.
Degree spectra of relations on computable structures in the presence of Δ20 isomorphisms.Denis R. Hirschfeldt - 2002 - Journal of Symbolic Logic 67 (2):697-720.
Weak Truth Table Degrees of Structures.David R. Belanger - 2015 - Notre Dame Journal of Formal Logic 56 (2):263-285.
$\Pi _{1}^{0}$ Classes with Complex Elements.Stephen Binns - 2008 - Journal of Symbolic Logic 73 (4):1341 - 1353.
$\Pi ^{0}_{1}$ -Encodability and Omniscient Reductions.Benoit Monin & Ludovic Patey - 2019 - Notre Dame Journal of Formal Logic 60 (1):1-12.
Degree spectra of intrinsically C.e. Relations.Denis Hirschfeldt - 2001 - Journal of Symbolic Logic 66 (2):441-469.
Degrees of Categoricity and the Hyperarithmetic Hierarchy.Barbara F. Csima, Johanna N. Y. Franklin & Richard A. Shore - 2013 - Notre Dame Journal of Formal Logic 54 (2):215-231.
The computable Lipschitz degrees of computably enumerable sets are not dense.Adam R. Day - 2010 - Annals of Pure and Applied Logic 161 (12):1588-1602.
Computable isomorphisms, degree spectra of relations, and Scott families.Bakhadyr Khoussainov & Richard A. Shore - 1998 - Annals of Pure and Applied Logic 93 (1-3):153-193.

Analytics

Added to PP
2010-08-24

Downloads
66 (#266,196)

6 months
7 (#564,683)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Valentina Harizanov
George Washington University

Citations of this work

A Hierarchy of Computably Enumerable Degrees.Rod Downey & Noam Greenberg - 2018 - Bulletin of Symbolic Logic 24 (1):53-89.
Weak Truth Table Degrees of Structures.David R. Belanger - 2015 - Notre Dame Journal of Formal Logic 56 (2):263-285.

Add more citations

References found in this work

Computable structures and the hyperarithmetical hierarchy.C. J. Ash - 2000 - New York: Elsevier. Edited by J. Knight.
Intrinsically gs;0alpha; relations.E. Barker - 1988 - Annals of Pure and Applied Logic 39 (2):105-130.

View all 16 references / Add more references