Degree spectra of relations on structures of finite computable dimension
From MaRDI portal
Publication:1612487
The author proves that for every c.e. (\(\alpha\)-c.e., \(\alpha\in\omega\cup\{\omega\}\)) degree \(\mathbf d>0\) there is a computable structure whose algorithmic dimension is 2 and an intrinsically c.e. (\(\alpha\)-c.e.) relation on it such that its degree spectrum is \textbf{\{0,d\}}. Some generalizations and variations of this result are also considered.
Recommendations
- Degree Spectra of Relations on Computable Structures
- Degree spectra of relations on computable structures in the presence of Δ20isomorphisms
- On the spectrum of degrees of decidable relations
- scientific article; zbMATH DE number 5066582
- Degree spectra and computable dimensions in algebraic structures
- Realizing levels of the hyperarithmetic hierarchy as degree spectra of relations on computable structures
- The degree spectra of definable relations on Boolean algebras
- Turing degrees of hypersimple relations on computable structures
- On the degree structure of equivalence relations under computable reducibility
- Degree spectra of the successor relation of computable linear orderings
Cites work
- A solution of the Goncharov-Ash problem and the spectrum problem in the theory of computable models.
- Computable isomorphisms, degree spectra of relations, and Scott families
- Computable single-valued numerations
- Computably categorical structures and expansions by constants
- Degree spectra and computable dimensions in algebraic structures
- Degree spectra of intrinsically c. e. relations
- Handbook of recursive mathematics. Vol. 1: Recursive model theory
- scientific article; zbMATH DE number 3732033 (Why is no real title available?)
- scientific article; zbMATH DE number 3732038 (Why is no real title available?)
- scientific article; zbMATH DE number 194103 (Why is no real title available?)
- scientific article; zbMATH DE number 1302870 (Why is no real title available?)
- scientific article; zbMATH DE number 1302871 (Why is no real title available?)
- scientific article; zbMATH DE number 1302872 (Why is no real title available?)
- scientific article; zbMATH DE number 1302875 (Why is no real title available?)
- scientific article; zbMATH DE number 1303201 (Why is no real title available?)
- scientific article; zbMATH DE number 1405578 (Why is no real title available?)
- Intrinsically \(\Sigma ^ 0_{\alpha}\) relations
- Permitting, forcing, and copying of a given recursive relation
- Problem of the number of non-self-equivalent constructivizations
- Recursive isomorphism types of recursive Boolean algebras
- The possible Turing degree of the nonzero member in a two element degree spectrum
- Turing degrees of certain isomorphic images of computable relations
Cited in
(19)- Degree spectra of the successor relation of computable linear orderings
- Some effects of Ash-Nerode and other decidability conditions on degree spectra
- Finite computable dimension does not relativize
- Realizing levels of the hyperarithmetic hierarchy as degree spectra of relations on computable structures
- On the spectrum of degrees of decidable relations
- Degree spectra and computable dimensions in algebraic structures
- Finite computable dimension and degrees of categoricity
- On the isomorphism problem for some classes of computable algebraic structures
- On the degree structure of equivalence relations under computable reducibility
- Freely generated projective planes with finite computable dimension
- Degree spectra of intrinsically c. e. relations
- A directed graph of finite \(\Delta^0_{\alpha}\)-dimension
- Degree spectra of relations on computable structures in the presence of Δ20isomorphisms
- scientific article; zbMATH DE number 2047485 (Why is no real title available?)
- Degree Spectra of Relations on Computable Structures
- Degrees of relations on ordinals
- Degree spectra of relations on a cone
- scientific article; zbMATH DE number 5066582 (Why is no real title available?)
- The theory of projective planes is complete with respect to degree spectra and effective dimensions
This page was built for publication: Degree spectra of relations on structures of finite computable dimension
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1612487)
