Classification from a Computable Viewpoint

DOI10.2178/BSL/1146620059MaRDI QIDQ3430937zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Wesley Calvert, J. F. Knight

Publication date 5 April 2007

Published in The Bulletin of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0803.3293

zbMATH Keywords

surveycomputable structuresScott rankBorel embeddingBorel isomorphism relation

Mathematics Subject Classification ID

Computable structure theory, computable model theory (03C57) Model theory of denumerable and separable structures (03C15)

Abstract: Classification is an important goal in many branches of mathematics. The idea is to describe the members of some class of mathematical objects, up to isomorphism or other important equivalence in terms of relatively simple invariants. Where this is impossible, it is useful to have concrete results saying so. In model theory and descriptive set theory, there is a large body of work, showing that certain classes of mathematical structures admit classification, while others do not. In the present paper, we describe some recent work on classification in computable structure theory.

Recommendations

• scientific article; zbMATH DE number 139608
• Complexity of classification problems
• A general approach to classification problems
• Towards a theory of classification
• A combinatorial approach to the classification problem
• Classification via mathematical programming (Survey)
• A predicative approach to the classification problem
• scientific article; zbMATH DE number 1107550
• Methods and algorithms for solution problems of classification
• Approximating a Class of Classification Problems

Cites work

• scientific article; zbMATH DE number 1226875 (Why is no real title available?)
• scientific article; zbMATH DE number 1302869 (Why is no real title available?)
• scientific article; zbMATH DE number 976831 (Why is no real title available?)
• scientific article; zbMATH DE number 934728 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• scientific article; zbMATH DE number 3308418 (Why is no real title available?)
• A Borel reductibility theory for classes of countable structures
• A proof of Vaught's conjecture for \(\omega\)-stable theories
• An example concerning Scott heights
• Autostability of models
• Back and forth relations for reduced abelian p-groups
• Complexity of Categorical Theories with Computable Models
• Composites of algebraically closed fields
• Computable structures and the hyperarithmetical hierarchy
• Infinitary logic and admissible sets
• Models with compactness properties relative to an admissible language
• On strongly minimal sets
• On the Borel classification of the isomorphism class of a countable model
• Recent developments in the theory of Borel reducibility
• Scott sentences and admissible sets
• The degrees of bi‐immune sets
• The isomorphism problem for computable Abelian _p-groups of bounded length
• The isomorphism relation on countable torsion free abelian groups
• The number of countable models
• The number of non-isomorphic models of an unstable first-order theory
• Theories of linear order
• What is a Structure Theory?
• Π₁¹ relations and paths through

Cited in

(21)

• Finitary reducibility on equivalence relations
• The computable embedding problem
• scientific article; zbMATH DE number 2047478 (Why is no real title available?)
• Categoricity spectra of computable structures
• Computable numberings of the class of Boolean algebras with distinguished endomorphisms
• Agreement reducibility
• Scott ranks of models of a theory
• On two types of concept lattices in the theory of numberings
• Computability and computable models
• The isomorphism problem for torsion-free abelian groups is analytic complete
• scientific article; zbMATH DE number 1904842 (Why is no real title available?)
• The isomorphism problem on classes of automatic structures with transitive relations
• Tree-automatic well-founded trees
• Isomorphism and classification for countable structures
• Classifications of computable structures
• On the degree structure of equivalence relations under computable reducibility
• Computable transformations of structures
• Computable embeddings and strongly minimal theories
• The complexity of decomposability of computable rings
• An introduction to the Scott complexity of countable structures and a survey of recent results
• Computability theoretic classifications for classes of structures

This page was built for publication: Classification from a Computable Viewpoint

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3430937)