Index sets of computable structures

DOI10.1007/S10469-006-0029-0MaRDI QIDQ3546058zbMATH OpenOpenAlexFDO

Authors Wesley Calvert, Sara Miller, Valentina Harizanov, J. F. Knight

Publication date 18 December 2008

Published in Algebra and Logic (Search for Journal in Brave)

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

zbMATH Keywords

index setcomputable structurevector spaceEhrenfeucht theoryArchimedean real-closed ordered fieldreduced abelian \(p\)-group

Mathematics Subject Classification ID

Computable structure theory, computable model theory (03C57)

Abstract: The emph{index set} of a computable structure $mathcalA$ is the set of indices for computable copies of $mathcalA$. We determine the complexity of the index sets of various mathematically interesting structures, including arbitrary finite structures, $mathbbQ$-vector spaces, Archimedean real closed ordered fields, reduced Abelian $p$-groups of length less than $omeg{a}^2$, and models of the original Ehrenfeucht theory. The index sets for these structures all turn out to be $m$-complete $P{i}_n^0$, $d$-$Sigm{a}_n^0$, or $Sigm{a}_n^0$, for various $n$. In each case, the calculation involves finding an extquotedblleft optimal extquotedblright% sentence (i.e., one of simplest form) that describes the structure. The form of the sentence (computable $P{i}_n$, $d$-$Sigm{a}_n$, or $Sigm{a}_n$) yields a bound on the complexity of the index set. When we show $m$% -completeness of the index set, we know that the sentence is optimal. For some structures, the first sentence that comes to mind is not optimal, and another sentence of simpler form is shown to serve the purpose. For some of the groups, this involves Ramsey theory.

Recommendations

• Index sets for some classes of structures
• Index sets and Scott sentences
• Index sets of autostable relative to strong constructivizations constructive models for familiar classes
• Index sets for classes of high rank structures
• Scott sentences for equivalence structures

Cited in

(31)

• Index sets and Scott sentences
• scientific article; zbMATH DE number 4035802 (Why is no real title available?)
• Computable elements and functions in effectively enumerable topological spaces
• Comparing classes of finite sums
• Index sets as a measure of continuous constraint complexity
• The complexity of countable categoricity in finite languages
• A note on decidable categoricity and index sets
• Scott sentences for certain groups
• Computable numberings of the class of Boolean algebras with distinguished endomorphisms
• Categoricity properties for computable algebraic fields
• Complexity of index sets of calculable classes with a finite number of constructive systems
• THE COMPLEXITY OF SCOTT SENTENCES OF SCATTERED LINEAR ORDERS
• Index sets for classes of high rank structures
• Describing groups
• Effective categoricity of abelian p-groups
• The number of nonequivalent computable indexations for a fixed family of sets
• Rice's theorem in effectively enumerable topological spaces
• PAC learning, VC dimension, and the arithmetic hierarchy
• On optimal Scott sentences of finitely generated algebraic structures
• Index sets for some classes of structures
• Describing free groups
• Computability in infinite Galois theory and algorithmically random algebraic fields
• scientific article; zbMATH DE number 5379427 (Why is no real title available?)
• Index sets of prime models
• Finitely generated groups are universal among finitely generated structures
• On Index Sets of Some Properties of Computable Algebras
• Classifications of computable structures
• Detecting properties from descriptions of groups
• Scott sentences for equivalence structures
• An introduction to the Scott complexity of countable structures and a survey of recent results
• ON THE COMPLEXITY OF CLASSIFYING LEBESGUE SPACES

This page was built for publication: Index sets of computable structures

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