Computable structures and the hyperarithmetical hierarchy

zbMath0960.03001MaRDI QIDQ1572657

C. J. Ash, Julia F. Knight

Publication date: 20 July 2000

Published in: Studies in Logic and the Foundations of Mathematics (Search for Journal in Brave)

zbMATH Keywords

stabilityeffectivenesscomputabilitycountable modelsadjacencycomputable categoricitycomputable model theorycomputable presentation

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30) Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45)

Related Items

WHICH CLASSES OF STRUCTURES ARE BOTH PSEUDO-ELEMENTARY AND DEFINABLE BY AN INFINITARY SENTENCE? ⋮ Definable Subsets of Polynomial-Time Algebraic Structures ⋮ Turing degrees of nonabelian groups ⋮ A fixed point for the jump operator on structures ⋮ AN INTRODUCTION TO THE SCOTT COMPLEXITY OF COUNTABLE STRUCTURES AND A SURVEY OF RECENT RESULTS ⋮ Π₁¹ relations and paths through ⋮ Bounding prime models ⋮ Arithmetical independence results using higher recursion theory ⋮ Another Jump Inversion Theorem for Structures ⋮ COPYING ONE OF A PAIR OF STRUCTURES ⋮ Primitive recursive reverse mathematics ⋮ On the complexity of the theory of a computably presented metric structure ⋮ On the effective universality of mereological theories ⋮ ON COHESIVE POWERS OF LINEAR ORDERS ⋮ The complexity of decomposability of computable rings ⋮ ASSIGNING AN ISOMORPHISM TYPE TO A HYPERDEGREE ⋮ Polynomial-time axioms of choice and polynomial-time cardinality ⋮ Computable Stone spaces ⋮ On two types of concept lattices in the theory of numberings ⋮ Computable Heyting algebras with distinguished atoms and coatoms ⋮ Towards characterizing the \(> \omega^2\)-fickle recursively enumerable Turing degrees ⋮ Jump inversions of algebraic structures and Σ‐definability ⋮ Degrees of categoricity of trees and the isomorphism problem ⋮ STRUCTURAL HIGHNESS NOTIONS ⋮ Separating notions in effective topology ⋮ Punctually presented structures I: Closure theorems ⋮ Classes of algebraic structures ⋮ A structure of punctual dimension two ⋮ A local version of the Slaman-Wehner theorem and families closed under finite differences ⋮ COMPUTABLY COMPACT METRIC SPACES ⋮ Induction, Bounding, Weak Combinatorial Principles, and the Homogeneous Model Theorem ⋮ The Complexity of Orbits of Computably Enumerable Sets ⋮ Isomorphism relations on computable structures ⋮ Complexity of Scott sentences ⋮ COMPUTABLE LINEAR ORDERS AND PRODUCTS ⋮ CODING IN GRAPHS AND LINEAR ORDERINGS ⋮ Friedberg numberings in the Ershov hierarchy ⋮ Up to equimorphism, hyperarithmetic is recursive ⋮ The property “arithmetic-is-recursive” on a cone ⋮ The complexity of ascendant sequences in locally nilpotent groups ⋮ TRIAL AND ERROR MATHEMATICS II: DIALECTICAL SETS AND QUASIDIALECTICAL SETS, THEIR DEGREES, AND THEIR DISTRIBUTION WITHIN THE CLASS OF LIMIT SETS ⋮ DEGREES OF CATEGORICITY ON A CONE VIAη-SYSTEMS ⋮ Turing computable embeddings ⋮ Π₁⁰ classes and strong degree spectra of relations ⋮ Friedberg numberings in the Ershov hierarchy ⋮ 2-Computably Enumerable Degrees of Categoricity for Boolean Algebras with Distinguished Automorphisms ⋮ Boolean Algebras with Distinguished Endomorphisms and Generating Trees ⋮ Solovay's theorem cannot be simplified ⋮ Ranked structures and arithmetic transfinite recursion ⋮ The importance of Π₁⁰ classes in effective randomness ⋮ Index sets for classes of high rank structures ⋮ Ash's theorem on \(\Delta_{\alpha}^{0}\)-categorical structures and a condition for infinite \(\Delta_{\alpha}^{0}\)-dimension ⋮ Tree-Automatic Well-Founded Trees ⋮ RANK AND RANDOMNESS ⋮ AUTOMATIC AND POLYNOMIAL-TIME ALGEBRAIC STRUCTURES ⋮ Decompositions of decidable abelian groups ⋮ Computable trees of Scott rank ω₁^CK, and computable approximation ⋮ FOUNDATIONS OF ONLINE STRUCTURE THEORY ⋮ INDECOMPOSABLE LINEAR ORDERINGS AND HYPERARITHMETIC ANALYSIS ⋮ Degrees of bi-embeddable categoricity ⋮ Categoricity properties for computable algebraic fields ⋮ Relativizing computable categoricity ⋮ Unnamed Item ⋮ THE COMPLEXITY OF SCOTT SENTENCES OF SCATTERED LINEAR ORDERS ⋮ ON THE COMPLEXITY OF CLASSIFYING LEBESGUE SPACES ⋮ PUNCTUAL CATEGORICITY AND UNIVERSALITY ⋮ COMPUTABILITY OF POLISH SPACES UP TO HOMEOMORPHISM ⋮ Computing on the Banach space C [ 0 , 1 ] ⋮ ORDINAL ANALYSIS OF PARTIAL COMBINATORY ALGEBRAS ⋮ SCOTT COMPLEXITY OF COUNTABLE STRUCTURES ⋮ Effectivizing Lusin’s Theorem ⋮ Continuous higher randomness ⋮ Computable embeddability for algebraic structures ⋮ THE PREHISTORY OF THE SUBSYSTEMS OF SECOND-ORDER ARITHMETIC ⋮ On categoricity spectra for locally finite graphs ⋮ New degree spectra of Polish spaces ⋮ The index set of the groups autostable relative to strong constructivizations ⋮ Degrees of autostability for prime Boolean algebras ⋮ Degrees of autostability relative to strong constructivizations for Boolean algebras ⋮ Embeddability of the semilattice \(L_m^0\) in Rogers semilattices ⋮ Degrees of autostability for linear orders and linearly ordered abelian groups ⋮ Index sets of constructive models of finite and graph signatures that are autostable relative to strong constructivizations ⋮ Limiting partial combinatory algebras ⋮ Abelian \(p\)-groups and the halting problem ⋮ Implicit definability in arithmetic ⋮ Completeness of the hyperarithmetic isomorphism equivalence relation ⋮ Isomorphisms and algorithmic properties of structures with two equivalences ⋮ Scott ranks of models of a theory ⋮ Computable categoricity of the Boolean algebra \(\mathfrak{B}(\omega )\) with a distinguished automorphism ⋮ The branching theorem and computable categoricity in the Ershov hierarchy ⋮ Turing reducibility in the fine hierarchy ⋮ Index sets and Scott sentences ⋮ The diversity of categoricity without delay ⋮ Computable numberings of the class of Boolean algebras with distinguished endomorphisms ⋮ Computable torsion abelian groups ⋮ Constructivizability of the Boolean algebra \( \mathfrak{B}( \omega ) \) with a distinguished automorphism ⋮ Enumerating abelian \(p\)-groups ⋮ The omega-rule interpretation of transfinite provability logic ⋮ The minimality of certain decidability conditions for Boolean algebras ⋮ A note on decidable categoricity and index sets ⋮ Index sets of autostable relative to strong constructivizations constructive models for familiar classes ⋮ Spaces of orders and their Turing degree spectra ⋮ Classifications of computable structures ⋮ Degrees of categoricity and the hyperarithmetic hierarchy ⋮ Classifying equivalence relations in the Ershov hierarchy ⋮ Online presentations of finitely generated structures ⋮ Limit computable integer parts ⋮ Learning families of algebraic structures from informant ⋮ Cuts of linear orders ⋮ Realizing levels of the hyperarithmetic hierarchy as degree spectra of relations on computable structures ⋮ The complexity of computable categoricity ⋮ Computable bi-embeddable categoricity ⋮ Elementary theories and hereditary undecidability for semilattices of numberings ⋮ Index sets of constructive models of nontrivial signature autostable relative to strong constructivizations ⋮ HKSS-completeness of modal algebras ⋮ Independence in computable algebra ⋮ The index set of Boolean algebras autostable relative to strong constructivizations ⋮ Measuring complexities of classes of structures ⋮ Proper divisibility in computable rings ⋮ Scott sentences for certain groups ⋮ Categoricity spectra for polymodal algebras ⋮ On two problems of Turing complexity for strongly minimal theories ⋮ Hanf number for Scott sentences of computable structures ⋮ Algebraic structures computable without delay ⋮ The existence of strongly computable representations in the class of Boolean algebras ⋮ The computable embedding problem ⋮ Metric structures and probabilistic computation ⋮ Using computability to measure complexity of algebraic structures and classes of structures ⋮ Eliminating unbounded search in computable algebra ⋮ Turing computable embeddings, computable infinitary equivalence, and linear orders ⋮ Coding and definability in computable structures ⋮ Complexity of the isomorphism problem for computable free projective planes of finite rank ⋮ The back-and-forth method and computability without delay ⋮ A note on computable distinguishing colorings ⋮ Punctual categoricity relative to a computable oracle ⋮ Partial automorphism semigroups ⋮ Categoricity spectra of computable structures ⋮ Degrees of enumerations of countable Wehner-like families ⋮ Computable presentability of countable linear orders ⋮ Non-density in punctual computability ⋮ Degree spectra of the successor relation of computable linear orderings ⋮ Chains and antichains in partial orderings ⋮ The metamathematics of ergodic theory ⋮ Index sets for some classes of structures ⋮ Weakly precomplete equivalence relations in the Ershov hierarchy ⋮ Computable embeddings for pairs of linear orders ⋮ Effective categoricity of abelian \(p\)-groups ⋮ Detecting properties from descriptions of groups ⋮ Scott sentences for equivalence structures ⋮ Categorical linearly ordered structures ⋮ Rogers semilattices for families of equivalence relations in the Ershov hierarchy ⋮ On bi-embeddable categoricity of algebraic structures ⋮ Effectiveness for the dual Ramsey theorem ⋮ An effective analysis of the Denjoy rank ⋮ Reductions between types of numberings ⋮ Coding a family of sets ⋮ On decidability of list structures ⋮ Computable topological abelian groups ⋮ Computability-theoretic properties of injection structures ⋮ Computing and dominating the Ryll-Nardzewski function ⋮ Families without minimal numberings ⋮ Cone avoidance and randomness preservation ⋮ \(\mathsf{WKL}_0\) and induction principles in model theory ⋮ Calculating the mind change complexity of learning algebraic structures ⋮ Well-orders realized by C.E. equivalence relations ⋮ Enumerating classes of effective quasi-Polish spaces ⋮ On \(\Delta_2^0\)-categoricity of equivalence relations ⋮ Computable analysis and classification problems ⋮ Degrees of non-computability of homeomorphism types of Polish spaces ⋮ \(\Delta_{2}^{0}\)-categoricity in Boolean algebras and linear orderings ⋮ Weak truth table degrees of structures ⋮ Autostability spectra for Boolean algebras ⋮ Searching for applicable versions of computable structures ⋮ Limitwise monotonic spectra and their generalizations ⋮ Equivalence between Fraïssé's conjecture and Jullien's theorem ⋮ A robuster Scott rank ⋮ Membrane system models for super-Turing paradigms ⋮ Classes of Ulm type and coding rank-homogeneous trees in other structures ⋮ An example related to Gregory's theorem ⋮ Effectively categorical abelian groups ⋮ On optimal Scott sentences of finitely generated algebraic structures ⋮ Rogers semilattices of families of two embedded sets in the Ershov hierarchy ⋮ Computable linearizations of well-partial-orderings ⋮ Computable completely decomposable groups ⋮ Boolean algebra approximations ⋮ A LIGHTFACE ANALYSIS OF THE DIFFERENTIABILITY RANK ⋮ Prime Model with No Degree of Autostability Relative to Strong Constructivizations ⋮ A Note on the Computable Categoricity of $$\ell ^p$$ ℓ p Spaces ⋮ On a question of Kalimullin ⋮ Torsion-free abelian groups with optimal Scott families ⋮ Specification, testing and verification of unconventional computations using generalizedX-machines ⋮ Spectrum of the field of computable real numbers ⋮ Bounded low and high sets ⋮ Effective categoricity for distributive lattices and Heyting algebras ⋮ UNIFORM PROCEDURES IN UNCOUNTABLE STRUCTURES ⋮ Orders on magmas and computability theory ⋮ Computable isomorphisms for certain classes of infinite graphs ⋮ The computational strength of matchings in countable graphs ⋮ Unnamed Item ⋮ Computable elements and functions in effectively enumerable topological spaces ⋮ Rogers semilattices with least and greatest elements in the Ershov hierarchy ⋮ Descriptive complexity of \(\mathsf{qc} \mathsf{b}_0\)-spaces ⋮ A Friedberg enumeration of equivalence structures ⋮ ON THE DECIDABILITY OF THE THEORIES OF THE ARITHMETIC AND HYPERARITHMETIC DEGREES AS UPPERSEMILATTICES ⋮ Learning algebraic structures with the help of Borel equivalence relations ⋮ Describing groups ⋮ Degrees of categoricity for superatomic Boolean algebras ⋮ Effectively Existentially-Atomic Structures ⋮ Enumeration Reducibility and Computable Structure Theory ⋮ Strength and Weakness in Computable Structure Theory ⋮ On Constructive Nilpotent Groups ⋮ Injection Structures Specified by Finite State Transducers ⋮ MASS PROBLEMS AND HYPERARITHMETICITY ⋮ Complexity of \(\Sigma^0_n\)-classifications for definable subsets ⋮ Generalization of Shapiro's theorem to higher arities and noninjective notations ⋮ COMPUTABLE STRUCTURES IN GENERIC EXTENSIONS ⋮ COMPARING TWO VERSIONS OF THE REALS ⋮ Analytic computable structure theory and $L^p$ spaces ⋮ A Note on Effective Categoricity for Linear Orderings ⋮ A bounded jump for the bounded Turing degrees ⋮ Avoiding uniformity in the \(\Delta_2^0\) enumeration degrees ⋮ On the Π₁ ¹ -separation principle ⋮ Well Quasi-orderings and Roots of Polynomials in a Hahn Field ⋮ Well-Quasi Orders and Hierarchy Theory ⋮ Jump degrees of torsion-free abelian groups ⋮ DEGREES OF CATEGORICITY AND SPECTRAL DIMENSION ⋮ A COMPUTABLE FUNCTOR FROM GRAPHS TO FIELDS ⋮ 2010 European Summer Meeting of the Association for Symbolic Logic. Logic Colloquium '10 ⋮ Degree Spectra of Relations on a Cone ⋮ BOREL FUNCTORS AND INFINITARY INTERPRETATIONS ⋮ Embedding jump upper semilattices into the Turing degrees ⋮ A computable ℵ₀-categorical structure whose theory computes true arithmetic ⋮ Equivalence Relations on Classes of Computable Structures ⋮ Notes on the Jump of a Structure ⋮ Minimality and completions of PA ⋮ Depth zero Boolean algebras ⋮ A characterization of the 0-basis homogeneous bounding degrees ⋮ On the Equimorphism Types of Linear Orderings ⋮ Barwise: Infinitary Logic and Admissible Sets ⋮ Effective categoricity of equivalence structures ⋮ On the orbits of computably enumerable sets ⋮ Boolean algebras, Tarski invariants, and index sets ⋮ A local characterization of VC-minimality ⋮ COMPUTABLE ABELIAN GROUPS ⋮ AUTOMORPHISM GROUPS OF COUNTABLE ARITHMETICALLY SATURATED MODELS OF PEANO ARITHMETIC ⋮ Computable topological groups and Pontryagin duality ⋮ Effectively closed subgroups of the infinite symmetric group ⋮ Degrees of autostability relative to strong constructivizations ⋮ The degree spectra of homogeneous models ⋮ Computable structures and operations on the space of continuous functions ⋮ 2004 Annual Meeting of the Association for Symbolic Logic ⋮ The isomorphism problem for computable Abelian _p-groups of bounded length ⋮ CLASSES OF STRUCTURES WITH NO INTERMEDIATE ISOMORPHISM PROBLEMS ⋮ Computability of Fraïssé limits ⋮ Effective Categoricity of Injection Structures ⋮ Conservative Extensions of Abstract Structures ⋮ COMPUTABLE STRUCTURES OF RANK $\omega_{1}^{{\rm CK}}$ ⋮ ON THE COMPLEXITY OF THE SUCCESSIVITY RELATION IN COMPUTABLE LINEAR ORDERINGS ⋮ Intrinsic bounds on complexity and definability at limit levels ⋮ Coding in the automorphism group of a computably categorical structure ⋮ The degrees of categorical theories with recursive models ⋮ Bounds on Scott ranks of some polish metric spaces ⋮ Mass Problems and Measure-Theoretic Regularity ⋮ Comparing theorems of hyperarithmetic analysis with the arithmetic Bolzano-Weierstrass theorem ⋮ Describing free groups ⋮ On the $n$-back-and-forth types of Boolean algebras ⋮ The isomorphism problem on classes of automatic structures with transitive relations ⋮ Enumerations in computable structure theory ⋮ RELATIVE TO ANY NON-HYPERARITHMETIC SET ⋮ Bounding homogenous models ⋮ Spectra of structures and relations ⋮ Classification from a Computable Viewpoint ⋮ 2005 Summer Meeting of the Association for Symbolic Logic. Logic Colloquium '05 ⋮ Sequences of n-diagrams