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

Turing degrees of hypersimple relations on computable structures

โœ Scribed by Valentina S. Harizanov

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
175 KB
Volume
121
Category
Article
ISSN
0168-0072

No coin nor oath required. For personal study only.

โœฆ Synopsis

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รฟnability of certain e ective sequences of relations on A. Assuming that R is formally hypersimple on A, we give general su cient conditions for the existence of a computable isomorphic copy of A on whose domain the image of R is hypersimple and of arbitrary nonzero computably enumerable Turing degree.

๐Ÿ“œ SIMILAR VOLUMES

Turing degrees of certain isomorphic ima
Turing degrees of certain isomorphic images of computable relations
โœ Valentina S. Harizanov ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 683 KB

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 ima

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

On the complexity of categoricity in com
On the complexity of categoricity in computable structures
โœ Walker M. White ๐Ÿ“‚ Article ๐Ÿ“… 2003 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 192 KB

## Abstract We investigate the computational complexity the class of ฮ“โ€categorical computable structures. We show that hyperarithmetic categoricity is ฮ ^1^~1~โ€complete, while computable categoricity is ฮ ^0^~4~โ€hard. (ยฉ 2003 WILEYโ€VCH Verlag GmbH & Co. KGaA, Weinheim)