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

Archimedean real-closed ordered fieldcomputable structureEhrenfeucht theoryindex setreduced abelian \(p\)-groupvector space

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

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)