Archive for Mathematical Logic 43 (3):327-336 (2004)
Abstract |
Theories of classification distinguish classes with some good structure theorem from those for which none is possible. Some classes (dense linear orders, for instance) are non-classifiable in general, but are classifiable when we consider only countable members. This paper explores such a notion for classes of computable structures by working out several examples. One motivation is to see whether some classes whose set of countable members is very complex become classifiable when we consider only computable members. We follow recent work by Goncharov and Knight in using the degree of the isomorphism problem for a class to distinguish classifiable classes from non-classifiable. For real closed fields we show that the isomorphism problem is Δ1 1 complete (the maximum possible), and for others we show that it is of relatively low complexity. We show that the isomorphism problem for algebraically closed fields, Archimedean real closed fields, or vector spaces is Π0 3 complete
|
Keywords | Mathematics |
Categories | (categorize this paper) |
DOI | 10.1007/s00153-004-0219-1 |
Options |
![]() ![]() ![]() ![]() |
Download options
References found in this work BETA
A Borel Reducibility Theory for Classes of Countable Structures.Harvey Friedman & Lee Stanley - 1989 - Journal of Symbolic Logic 54 (3):894-914.
Citations of this work BETA
Scott Sentences for Certain Groups.Julia F. Knight & Vikram Saraph - 2018 - Archive for Mathematical Logic 57 (3-4):453-472.
Classification From a Computable Viewpoint.Wesley Calvert & Julia F. Knight - 2006 - Bulletin of Symbolic Logic 12 (2):191-218.
The Isomorphism Problem for Computable Abelian P-Groups of Bounded Length.Wesley Calvert - 2005 - Journal of Symbolic Logic 70 (1):331 - 345.
On the isomorphism problem for some classes of computable algebraic structures.Valentina S. Harizanov, Steffen Lempp, Charles F. D. McCoy, Andrei S. Morozov & Reed Solomon - 2022 - Archive for Mathematical Logic 61 (5):813-825.
An Introduction to the Scott Complexity of Countable Structures and a Survey of Recent Results.Matthew Harrison-Trainor - 2022 - Bulletin of Symbolic Logic 28 (1):71-103.
View all 8 citations / Add more citations
Similar books and articles
The Isomorphism Problem for Computable Abelian P-Groups of Bounded Length.Wesley Calvert - 2005 - Journal of Symbolic Logic 70 (1):331 - 345.
Isomorphism Relations on Computable Structures.Ekaterina B. Fokina, Sy-David Friedman, Valentina Harizanov, Julia F. Knight, Charles Mccoy & Antonio Montalbán - 2012 - Journal of Symbolic Logic 77 (1):122-132.
Isomorphism of Homogeneous Structures.John D. Clemens - 2009 - Notre Dame Journal of Formal Logic 50 (1):1-22.
Effectively Closed Sets and Enumerations.Paul Brodhead & Douglas Cenzer - 2008 - Archive for Mathematical Logic 46 (7-8):565-582.
Categoricity of Computable Infinitary Theories.W. Calvert, S. S. Goncharov, J. F. Knight & Jessica Millar - 2009 - Archive for Mathematical Logic 48 (1):25-38.
The Relation of Recursive Isomorphism for Countable Structures.Riccardo Camerlo - 2002 - Journal of Symbolic Logic 67 (2):879-895.
Computable Embeddings and Strongly Minimal Theories.J. Chisholm, J. F. Knight & S. Miller - 2007 - Journal of Symbolic Logic 72 (3):1031 - 1040.
Strong Isomorphism Reductions in Complexity Theory.Sam Buss, Yijia Chen, Jörg Flum, Sy-David Friedman & Moritz Müller - 2011 - Journal of Symbolic Logic 76 (4):1381-1402.
Computable Isomorphisms of Boolean Algebras with Operators.Bakhadyr Khoussainov & Tomasz Kowalski - 2012 - Studia Logica 100 (3):481-496.
A Model Theoretical Generalization of Steinitz’s Theorem.Alexandre Martins Rodrigues & Edelcio De Souza - 2011 - Principia: An International Journal of Epistemology 15 (1):107-110.
Finite Computable Dimension Does Not Relativize.Charles F. D. McCoy - 2002 - Archive for Mathematical Logic 41 (4):309-320.
Index Sets for Classes of High Rank Structures.W. Calvert, E. Fokina, S. S. Goncharov, J. F. Knight, O. Kudinov, A. S. Morozov & V. Puzarenko - 2007 - Journal of Symbolic Logic 72 (4):1418 - 1432.
Analytic Equivalence Relations and Bi-Embeddability.Sy-David Friedman & Luca Motto Ros - 2011 - Journal of Symbolic Logic 76 (1):243 - 266.
Analytics
Added to PP index
2013-11-23
Total views
16 ( #668,647 of 2,519,507 )
Recent downloads (6 months)
1 ( #407,153 of 2,519,507 )
2013-11-23
Total views
16 ( #668,647 of 2,519,507 )
Recent downloads (6 months)
1 ( #407,153 of 2,519,507 )
How can I increase my downloads?
Downloads