Degree spectra and computable dimensions in algebraic structures

DOI10.1016/S0168-0072(01)00087-2zbMath1016.03034OpenAlexW1996816738WikidataQ61586383 ScholiaQ61586383MaRDI QIDQ1612482

Arkadii M. Slinko, Denis R. Hirschfeldt, Bakhadyr Khoussainov, Richard A. Shore

Publication date: 22 August 2002

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(01)00087-2

zbMATH Keywords

computable structurecomputable dimensioncomputable algebradegree spectrumrecursive modelinterpretation of structurenonstructure theorems

Mathematics Subject Classification ID

Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45)

Related Items (94)

Degree spectra of relations on structures of finite computable dimension ⋮ New degree spectra of Polish spaces ⋮ The index set of the groups autostable relative to strong constructivizations ⋮ Degrees of autostability for linear orders and linearly ordered abelian groups ⋮ \(\prod_1^1\)-completeness of the computable categoricity problem for projective planes ⋮ Classes of Ulm type and coding rank-homogeneous trees in other structures ⋮ Turing degrees of nonabelian groups ⋮ Complexity of the problem of being equivalent to Horn formulas ⋮ Π₁¹ relations and paths through ⋮ There is no classification of the decidably presentable structures ⋮ Torsion-free abelian groups with optimal Scott families ⋮ Degrees of categoricity of computable structures ⋮ Freely generated projective planes with finite computable dimension ⋮ On functors enumerating structures ⋮ Effective categoricity for distributive lattices and Heyting algebras ⋮ UNIFORM PROCEDURES IN UNCOUNTABLE STRUCTURES ⋮ Preserving categoricity and complexity of relations ⋮ COPYING ONE OF A PAIR OF STRUCTURES ⋮ INTERPRETING A FIELD IN ITS HEISENBERG GROUP ⋮ Graphs are not universal for online computability ⋮ A \(\Delta^{0}_{2}\)-poset with no positive presentation ⋮ Spectral universality of linear orders with one binary relation ⋮ On the effective universality of mereological theories ⋮ On two types of concept lattices in the theory of numberings ⋮ Computable Heyting algebras with distinguished atoms and coatoms ⋮ A Friedberg enumeration of equivalence structures ⋮ A structure of punctual dimension two ⋮ Lowness for isomorphism, countable ideals, and computable traceability ⋮ Classifications of computable structures ⋮ Strength and Weakness in Computable Structure Theory ⋮ On Constructive Nilpotent Groups ⋮ On degree spectra of topological spaces ⋮ The complexity of central series in nilpotent computable groups ⋮ Some Questions in Computable Mathematics ⋮ THE COMPLEMENTS OF LOWER CONES OF DEGREES AND THE DEGREE SPECTRA OF STRUCTURES ⋮ Simple structures with complex symmetry ⋮ Analytic computable structure theory and $L^p$ spaces ⋮ Realizing levels of the hyperarithmetic hierarchy as degree spectra of relations on computable structures ⋮ Degrees of isomorphism types and countably categorical groups ⋮ Computability theory. Abstracts from the workshop held January 7--13, 2018 ⋮ Degree spectra of real closed fields ⋮ Degrees of and lowness for isometric isomorphism ⋮ Some new computable structures of high rank ⋮ CODING IN GRAPHS AND LINEAR ORDERINGS ⋮ HKSS-completeness of modal algebras ⋮ DEGREES OF CATEGORICITY AND SPECTRAL DIMENSION ⋮ A COMPUTABLE FUNCTOR FROM GRAPHS TO FIELDS ⋮ Computability-theoretic categoricity and Scott families ⋮ Measuring complexities of classes of structures ⋮ Computability of distributive lattices ⋮ BOREL FUNCTORS AND INFINITARY INTERPRETATIONS ⋮ Categoricity spectra for polymodal algebras ⋮ A computably categorical structure whose expansion by a constant has infinite computable dimension ⋮ Equivalence Relations on Classes of Computable Structures ⋮ Computable isomorphisms of Boolean algebras with operators ⋮ Finitely generated groups are universal among finitely generated structures ⋮ The computable embedding problem ⋮ TURING DEGREE SPECTRA OF DIFFERENTIALLY CLOSED FIELDS ⋮ COMPUTABLE FUNCTORS AND EFFECTIVE INTERPRETABILITY ⋮ Using computability to measure complexity of algebraic structures and classes of structures ⋮ Degree spectra of structures relative to equivalences ⋮ Turing computable embeddings, computable infinitary equivalence, and linear orders ⋮ COMPUTABLE ABELIAN GROUPS ⋮ Categoricity spectra of computable structures ⋮ Degree spectra of structures ⋮ The theory of projective planes is complete with respect to degree spectra and effective dimensions ⋮ Categoricity and complexity of relations over algebraic structures ⋮ Prime models of finite computable dimension ⋮ Computable structures and operations on the space of continuous functions ⋮ Computable categoricity of trees of finite height ⋮ The isomorphism problem for computable Abelian _p-groups of bounded length ⋮ Non-density in punctual computability ⋮ Categoricity of computable infinitary theories ⋮ Model completeness and relative decidability ⋮ Index sets for some classes of structures ⋮ Computability of Fraïssé limits ⋮ Constructing decidable graphs from decidable structures ⋮ Computable embeddings for pairs of linear orders ⋮ ON THE COMPLEXITY OF THE SUCCESSIVITY RELATION IN COMPUTABLE LINEAR ORDERINGS ⋮ Categorical linearly ordered structures ⋮ d-computable categoricity for algebraic fields ⋮ Spectra of theories and structures ⋮ Limitwise monotonic sequences and degree spectra of structures ⋮ Categoricity properties for computable algebraic fields ⋮ PUNCTUAL CATEGORICITY AND UNIVERSALITY ⋮ \(\Sigma\)-presentations of the ordering on the reals ⋮ Point Degree Spectra of Represented Spaces ⋮ On \(\Delta_2^0\)-categoricity of equivalence relations ⋮ A note on computable embeddings for ordinals and their reverses ⋮ Degrees of non-computability of homeomorphism types of Polish spaces ⋮ Theory spectra and classes of theories ⋮ Weak truth table degrees of structures ⋮ Limitwise monotonic spectra and their generalizations ⋮ Computable procedures for fields

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Autostability of models
• Problem of the number of non-self-equivalent constructivizations
• The possible Turing degree of the nonzero member in a two element degree spectrum
• Strong and weak constructivization and computable families
• The quantity of nonautoequivalent constructivizations
• Handbook of recursive mathematics. Vol. 1: Recursive model theory
• Computable isomorphisms, degree spectra of relations, and Scott families
• A solution of the Goncharov-Ash problem and the spectrum problem in the theory of computable models.
• Degree spectra of relations on structures of finite computable dimension
• Nilpotent groups of finite algorithmic dimension
• A Borel reductibility theory for classes of countable structures
• Degree spectra of relations on computable structures in the presence of Δ₂⁰isomorphisms
• Recursive Labelling Systems and Stability of Recursive Structures in Hyperarithmetical Degrees
• Recursive categoricity and persistence
• Degrees coded in jumps of orderings
• Effective content of field theory
• Stability of nilpotent groups of class 2 and prime exponent
• Recursively Categorical Linear Orderings
• Computably categorical structures and expansions by constants
• New Directions in Descriptive Set Theory
• Relative to any nonrecursive set
• Enumerations, countable structures and Turing degrees
• The completeness of the isomorphism relation for countable Boolean algebras
• A computably categorical structure whose expansion by a constant has infinite computable dimension
• On a correspondence between rings and groups
• Borel equivalence relations and classifications of countable models

This page was built for publication: Degree spectra and computable dimensions in algebraic structures