The isomorphism problem for classes of computable fields

MaRDI QIDQ701725zbMATH OpenFDO

Authors Wesley Calvert

Publication date 16 December 2004

Published in Archive for Mathematical Logic (Search for Journal in Brave)

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

zbMATH Keywords

isomorphism problemcomputable modelcomputable fieldindex set of a class of models

Mathematics Subject Classification ID

Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45)

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 models 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 some classes (undirected graphs, fields of fixed characteristic, and real closed fields) we show that the isomorphism problem is Sigma^1_1 complete (the maximum possible), and for others it is of relatively low complexity. For instance, for algebraically closed fields, archimedean real closed fields, and vector spaces, we show that the isomorphism problem is Pi^0_3 complete.

Recommendations

• On the isomorphism problem for some classes of computable algebraic structures
• Isomorphism of Computable Structures and Vaught's Conjecture
• Isomorphism relations on computable structures
• On isomorphism classes of computably enumerable equivalence relations
• Isometries and computability structures
• scientific article; zbMATH DE number 4154700
• On the complexity of the isomorphism relation for fields of finite transcendence degree
• Computable fields and Galois theory
• Generically and coarsely computable isomorphisms
• On the hardness of the finite field isomorphism problem

Cited in

(22)

• A note on decidable categoricity and index sets
• Computable valued fields
• Equivalence Relations on Classes of Computable Structures
• Scott sentences for certain groups
• Ranked structures and arithmetic transfinite recursion
• On the hardness of the finite field isomorphism problem
• Isomorphism and classification for countable structures
• Index sets for some classes of structures
• scientific article; zbMATH DE number 7147443 (Why is no real title available?)
• Computable transformations of structures
• Isomorphism of Computable Structures and Vaught's Conjecture
• Degrees of categoricity of trees and the isomorphism problem
• Complexity of the isomorphism problem for computable free projective planes of finite rank
• The \(\delta_\alpha^0\)-computable enumerations of the classes of projective planes
• Classes of structures with no intermediate isomorphism problems
• On the isomorphism problem for some classes of computable algebraic structures
• Computability in infinite Galois theory and algorithmically random algebraic fields
• The computable embedding problem
• Isomorphisms of non-standard fields and Ash's conjecture
• An introduction to the Scott complexity of countable structures and a survey of recent results
• Computable numberings of the class of Boolean algebras with distinguished endomorphisms
• Classifications of computable structures

This page was built for publication: The isomorphism problem for classes of computable fields

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