Classification from a computable viewpoint

Bulletin of Symbolic Logic 12 (2):191-218 (2006)
  Copy   BIBTEX


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.Section 1 gives some background from model theory and descriptive set theory. From model theory, we give sample structure and non-structure theorems for classes that include structures of arbitrary cardinality. We also describe the notion of Scott rank, which is useful in the more restricted setting of countable structures. From descriptive set theory, we describe the basic Polish space of structures for a fixed countable language with fixed countable universe. We give sample structure and non-structure theorems based on the complexity of the isomorphism relation, and on Borel embeddings.Section 2 gives some background on computable structures. We describe three approaches to classification for these structures. The approaches are all equivalent. However, one approach, which involves calculating the complexity of the isomorphism relation, has turned out to be more productive than the others. Section 3 describes results on the isomorphism relation for a number of mathematically interesting classes—various kinds of groups and fields. In Section 4, we consider a setting similar to that in descriptive set theory. We describe an effective analogue of Borel embedding which allows us to make distinctions even among classes of finite structures. Section 5 gives results on computable structures of high Scott rank. Some of these results make use of computable embeddings. Finally, in Section 6, we mention some open problems and possible directions for future work.



    Upload a copy of this work     Papers currently archived: 86,507

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library


Added to PP

71 (#198,386)

6 months
5 (#192,757)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

The Number of Countable Differentially Closed Fields.David Marker - 2007 - Notre Dame Journal of Formal Logic 48 (1):99-113.
The isomorphism problem for ω-automatic trees.Dietrich Kuske, Jiamou Liu & Markus Lohrey - 2013 - Annals of Pure and Applied Logic 164 (1):30-48.
Classifications of Computable Structures.Karen Lange, Russell Miller & Rebecca M. Steiner - 2018 - Notre Dame Journal of Formal Logic 59 (1):35-59.
Computable Embeddings and Strongly Minimal Theories.J. Chisholm, J. F. Knight & S. Miller - 2007 - Journal of Symbolic Logic 72 (3):1031 - 1040.

View all 9 citations / Add more citations

References found in this work

Computable structures and the hyperarithmetical hierarchy.C. J. Ash - 2000 - New York: Elsevier. Edited by J. Knight.
Theory of Recursive Functions and Effective Computability.Hartley Rogers - 1971 - Journal of Symbolic Logic 36 (1):141-146.
Infinitary logic and admissible sets.Jon Barwise - 1969 - Journal of Symbolic Logic 34 (2):226-252.
On strongly minimal sets.J. T. Baldwin & A. H. Lachlan - 1971 - Journal of Symbolic Logic 36 (1):79-96.

View all 34 references / Add more references