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

computable fieldcomputable modelindex set of a class of modelsisomorphism problem

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.

Review text

Identifying a computable structure \(M\) whose basic set is \(\omega\) with its atomic diagram, we say that a computable structure has index \(a\) if \(a\) is the number of a Turing machine that enumerates this diagram. If \(a\) is an index for \({\mathcal A}\), we write \({\mathcal A}={\mathcal A}_a\). The isomorphism problem for a class \(K\) of computable models is the set \(E(K)=\{(a,b)\mid {\mathcal A}_a,{\mathcal A}_b\in K \wedge {\mathcal A}_a\cong{\mathcal A}_b\}\). The author proves the set \(E(K)\) to be \(\Sigma^0_3\)-complete for the following classes \(K\): computable vector spaces over an infinite computable field, computable algebraically closed fields of fixed characteristic, computable Archimedian real closed fields; and when \(K\) is either the class of computable real closed fields or the class of computable fields of characteristic \(0\), he proves the set \(E(K)\) to be \(\Sigma^1_1\)-complete. As a corollary, it is obtained that there is no Friedberg numbering up to isomorphism of computable fields of characteristic \(0\).

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)

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

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)