๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Turing degrees of certain isomorphic images of computable relations

โœ Scribed by Valentina S. Harizanov

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
683 KB
Volume
93
Category
Article
ISSN
0168-0072

No coin nor oath required. For personal study only.

โœฆ Synopsis

A model is computable if its domain is a computable set and its relations and functions are uniformly computable. Let ~2 be a computable model and let R be an extra relation on the domain of &. That is, R is not named in the language of .d. We define Dgd(R) to be the set of Turing degrees of the images f(R) under all isomorphisms f from cc4 to computable models.

We investigate conditions on S# and R which are sufficient and necessary for l&.&R) to contain every Turing degree. These conditions imply that if every Turing degree GO" can be realized in Dg.d(R) via an isomorphism of the same Turing degree as its image of R, then Dg&R) contains every Turing degree. We also discuss an example of .M' and R whose Dg,d(R) coincides with the Turing degrees which are ~0'.

๐Ÿ“œ SIMILAR VOLUMES

Turing degrees of hypersimple relations
Turing degrees of hypersimple relations on computable structures
โœ Valentina S. Harizanov ๐Ÿ“‚ Article ๐Ÿ“… 2003 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 175 KB

Let A be an inรฟnite computable structure, and let R be an additional computable relation on its domain A. The syntactic notion of formal hypersimplicity of R on A, รฟrst introduced and studied by Hird, is analogous to the computability-theoretic notion of hypersimplicity of R on A, given the deรฟnabil

On Turing degrees of points in computabl
On Turing degrees of points in computable topology
โœ Iraj Kalantari; Larry Welch ๐Ÿ“‚ Article ๐Ÿ“… 2008 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 169 KB

## Abstract This paper continues our study of computable pointโ€free topological spaces and the metamathematical points in them. For us, a __point__ is the intersection of a sequence of basic open sets with compact and nested closures. We call such a sequence a __sharp filter__. A function __f~F~__

Degree spectra of relations on structure
Degree spectra of relations on structures of finite computable dimension
โœ Denis R. Hirschfeldt ๐Ÿ“‚ Article ๐Ÿ“… 2002 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 415 KB

We show that for every computably enumerable (c.e.) degree aยฟ0 there is an intrinsically c.e. relation on the domain of a computable structure of computable dimension 2 whose degree spectrum is {0; a}, thus answering a question of Goncharov and Khoussainov (Dokl. Math. 55 (1997) 55-57). We also show