Degree spectra of intrinsically c.e. relations

DOI10.2307/2695024zbMath0988.03065OpenAlexW2025254909MaRDI QIDQ2747697

Denis R. Hirschfeldt

Publication date: 15 May 2002

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2695024

zbMATH Keywords

computable structuredegree spectrumintrinsically c.e. relation

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Theory of numerations, effectively presented structures (03D45)

Related Items

Degree spectra of relations on structures of finite computable dimension, On a question of Kalimullin, Algorithmic relationships of relations \(S_{\mathcal{L}}^n\) on linear orders, Degrees of orders on torsion-free abelian groups, Computable linear orders and the Ershov hierarchy, A computably categorical structure whose expansion by a constant has infinite computable dimension, A computably stable structure with no Scott family of finitary formulas, Non-density in punctual computability, Computable linear orders and the ershov hierarchy, Degree spectra of relations on computable structures in the presence of Δ₂⁰isomorphisms

Cites Work

• Unnamed Item
• Computable single-valued numerations
• Intrinsically \(\Sigma ^ 0_{\alpha}\) relations
• Autostability of models and Abelian groups
• Problem of the number of non-self-equivalent constructivizations
• The d.r.e. degrees are not dense
• The possible Turing degree of the nonzero member in a two element degree spectrum
• Computable isomorphisms, degree spectra of relations, and Scott families
• Permitting, forcing, and copying of a given recursive relation