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

Degree spectra of relations on structures of finite computable dimension

โœ Scribed by Denis R. Hirschfeldt

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
415 KB
Volume
115
Category
Article
ISSN
0168-0072

No coin nor oath required. For personal study only.

โœฆ Synopsis

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 that this theorem remains true with -c.e. in place of c.e. for any โˆˆ ! โˆช {!}. A modiรฟcation of the proof of this result similar to what was done in Hirschfeldt (J. Symbolic Logic, to appear) shows that for any โˆˆ ! โˆช {!} and any -c.e. degrees a0; : : : ; an there is an intrinsically -c.e. relation on the domain of a computable structure of computable dimension n + 1 whose degree spectrum is {a0; : : : ; an}. These results also hold for m-degree spectra of relations.

๐Ÿ“œ 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

Symmetry and the Ramsey Degrees of Finit
Symmetry and the Ramsey Degrees of Finite Relational Structures
โœ Willem L. Fouchรฉ ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 134 KB

In this paper, we introduce a measure of the extent to which a finite combinatorial structure is a Ramsey object in the class of objects with a similar structure. We show for classes of finite relational structures, including graphs, binary posets, and bipartite graphs, how this measure depends on t