Classifications of Computable Structures


Abstract
Let K be a family of structures, closed under isomorphism, in a fixed computable language. We consider effective lists of structures from K such that every structure in K is isomorphic to exactly one structure on the list. Such a list is called a computable classification of K, up to isomorphism. Using the technique of Friedberg enumeration, we show that there is a computable classification of the family of computable algebraic fields and that with a 0'-oracle, we can obtain similar classifications of the families of computable equivalence structures and of computable finite-branching trees. However, there is no computable classification of the latter, nor of the family of computable torsion-free abelian groups of rank 1, even though these families are both closely allied with computable algebraic fields.
Keywords computable structure theory   effective classification   equivalence structure  Friedberg enumeration
Categories (categorize this paper)
DOI 10.1215/00294527-2017-0015
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 39,545
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Finite Computable Dimension Does Not Relativize.Charles F. D. McCoy - 2002 - Archive for Mathematical Logic 41 (4):309-320.
Strange Structures From Computable Model Theory.Howard Becker - 2017 - Notre Dame Journal of Formal Logic 58 (1):97-105.
Categoricity Spectra for Rigid Structures.Ekaterina Fokina, Andrey Frolov & Iskander Kalimullin - 2016 - Notre Dame Journal of Formal Logic 57 (1):45-57.
Degrees That Are Not Degrees of Categoricity.Bernard Anderson & Barbara Csima - 2016 - Notre Dame Journal of Formal Logic 57 (3):389-398.
An Example Related to Gregory's Theorem.J. Johnson, J. F. Knight, V. Ocasio & S. VanDenDriessche - 2013 - Archive for Mathematical Logic 52 (3-4):419-434.
Prime Models of Finite Computable Dimension.Pavel Semukhin - 2009 - Journal of Symbolic Logic 74 (1):336-348.
On the Complexity of Categoricity in Computable Structures.Walker M. White - 2003 - Mathematical Logic Quarterly 49 (6):603.
Effective Algebraicity.Rebecca M. Steiner - 2013 - Archive for Mathematical Logic 52 (1-2):91-112.

Analytics

Added to PP index
2017-06-30

Total views
5 ( #920,448 of 2,325,377 )

Recent downloads (6 months)
3 ( #523,443 of 2,325,377 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature