Index Sets of Computable Structures

Details Index Sets of Computable Structures Index Sets of Computable Structures

2008-03-22

arxiv.org/abs/0803.3294v1

Algebra and Logic 45 (2006), 306--325

Mathematics

Logic

Scientific paper

The \emph{index set} of a computable structure $\mathcal{A}$ is the set of indices for computable copies of $\mathcal{A}$. We determine the complexity of the index sets of various mathematically interesting structures, including arbitrary finite structures, $\mathbb{Q}$-vector spaces, Archimedean real closed ordered fields, reduced Abelian $p$-groups of length less than $\omega^{2}$, and models of the original Ehrenfeucht theory. The index sets for these structures all turn out to be $m$-complete $\Pi_{n}^{0}$, $d$-$\Sigma_{n}^{0}$, or $\Sigma_{n}^{0}$, for various $n$. In each case, the calculation involves finding an \textquotedblleft optimal\textquotedblright% \ sentence (i.e., one of simplest form) that describes the structure. The form of the sentence (computable $\Pi_{n}$, $d$-$\Sigma_{n}$, or $\Sigma_{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.

Affiliated with

Also associated with

No associations

Rating

Index Sets of Computable Structures does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Index Sets of Computable Structures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Index Sets of Computable Structures will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-528745