Computable isomorphisms, degree spectra of relations, and Scott families

DOI10.1016/S0168-0072(97)00059-6zbMath0927.03072OpenAlexW2131332739MaRDI QIDQ1295389

Richard A. Shore, Bakhadyr Khoussainov

Publication date: 16 August 1999

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0168-0072(97)00059-6

zbMATH Keywords

computable structureScott familyTuring degreescomputably categorical structurescomputable isomorphism typescomputable partially ordered setintrinsically c.e. relationspectrum of a relation

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45)

Related Items

Degree spectra and computable dimensions in algebraic structures, Degree spectra of relations on structures of finite computable dimension, Π₁¹ relations and paths through, Freely generated projective planes with finite computable dimension, Degree Spectra of Relations on a Cone, Degree spectra of intrinsically c.e. relations, A computably categorical structure whose expansion by a constant has infinite computable dimension, On computably enumerable structures, Effective categoricity of equivalence structures, 1998–99 Annual Meeting of the Association for Symbolic Logic, The theory of projective planes is complete with respect to degree spectra and effective dimensions, Prime models of finite computable dimension, The computable dimension of trees of infinite height, Computable categoricity of trees of finite height, Computability of Fraïssé limits, Categoricity properties for computable algebraic fields, Degree Spectra of Relations on Computable Structures, Degree spectra of relations on computable structures in the presence of Δ₂⁰isomorphisms

Cites Work

• Recursive properties of relations on models
• Pairs of recursive structures
• Constructions by transfinitely many workers
• Generic copies of countable structures
• Autostability of models and Abelian groups
• Autostability of models
• Some effects of Ash-Nerode and other decidability conditions on degree spectra
• Polynomial-time versus recursive models
• The possible Turing degree of the nonzero member in a two element degree spectrum
• Strong and weak constructivization and computable families
• Autostability and computable families of constructivizations
• Algorithmic dimensions of homomorphic images of models
• Recursive unary algebras and trees
• Effectively infinite classes of weak constructivizations of models
• Permitting, forcing, and copying of a given recursive relation
• On the spectrum of degrees of decidable relations
• Categoricity in hyperarithmetical degrees
• Effective procedures in field theory
• Recursive isomorphism types of recursive Boolean algebras
• A metatheorem for constructions by finitely many workers
• Recursive categoricity and persistence
• Degrees coded in jumps of orderings
• Computably categorical structures and expansions by constants
• CONSTRUCTIVE ALGEBRAS I
• Computable Algebra, General Theory and Theory of Computable Fields
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item