The isomorphism problem for classes of computable fields

zbMATH Open1059.03039arXivmath/0212190MaRDI QIDQ701725FDOQ701725

Authors: Wesley Calvert 

Publication date: 16 December 2004

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

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.

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

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
• 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

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)

Cited In (22)

• The computable embedding problem
• Equivalence Relations on Classes of Computable Structures
• On the hardness of the finite field isomorphism problem
• Isomorphism of Computable Structures and Vaught's Conjecture
• A note on decidable categoricity and index sets
• 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
• Scott sentences for certain groups
• Computable numberings of the class of Boolean algebras with distinguished endomorphisms
• On the isomorphism problem for some classes of computable algebraic structures
• Computable valued fields
• Isomorphisms of non-standard fields and Ash's conjecture
• Title not available (Why is that?)
• Index sets for some classes of structures
• Computability in infinite Galois theory and algorithmically random algebraic fields
• Classes of structures with no intermediate isomorphism problems
• Degrees of categoricity of trees and the isomorphism problem
• Isomorphism and classification for countable structures
• Classifications of computable structures
• Computable transformations of structures
• An introduction to the Scott complexity of countable structures and a survey of recent results
• Ranked structures and arithmetic transfinite recursion

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)