The computable dimension of ordered abelian groups
type: Item
instance of: scholarly article
title: The computable dimension of ordered abelian groups
zbMATH Open document ID: 1031.03058
DOI: 10.1016/S0001-8708(02)00042-7
author: Steffen Lempp
author: S. S. Goncharov
author: Reed Solomon
published in: Advances in Mathematics
publication date: 2003-05-27T00:00:00Z
review text: There has been a lot of recent work studying the computable dimension of computably presented structures. This is defined to be the number of computable isomorphism types of the structure. For example, using a back and forth argument, the linear ordering of the rationals without end points is seen to have computable dimension one, whereas the ordering of \(\omega\) has dimension \(\infty\). Examples of structures (groups, graphs) with finite dimension are originally due to \textit{S. S. Goncharov} [e.g., Sov. Math., Dokl. 23, 58-61 (1981; Zbl 0496.20021)], and recently \textit{D. R. Hirschfeldt}, \textit{B. Khoussainov}, \textit{R. A. Shore} and \textit{A. M. Slinko} [Ann. Pure Appl. Logic 115, No. 1-3, 71-113 (2002; Zbl 1016.03034)] gave a general methodology of constructing structures with prescribed s-dimensions for a wide class of structures including graphs, lattices, groups, etc. Nevertheless the particular model theory of several classes of structures does not seem to admit the kinds of reductions used in this paper. Among these structures, one notable example is discussed in the present paper. An ordered Abelian group \((G,\leq)\) is one which has a relation \(\leq\) such that \(a\leq b\) implies \(a+ x\leq b+ x\) for all \(x\in G\). Computable presentations of ordered Abelian groups were first studied by \textit{R. Downey} and \textit{S. A. Kurtz} [Ann. Pure Appl. Logic 32, 137-151 (1986; Zbl 0629.03020)]. There the authors constructed a computable version of \(\sum_\omega\mathbb{Z}\) which had no computable ordering compatible with the presentation. Here the authors study the question of whether there is a basis of a computably ordered group compatible with the computable ordering. As well the authors study the basic spectral question of the dimensions. The answers are satisfying. If \(G\) is a computable Archimedean ordered group then \(G\) has a computable presentation which admits a computable basis. Every computable ordered Abelian group either has dim…
Mathematics Subject Classification ID: 03C57
Mathematics Subject Classification ID: 06F20
zbMATH DE Number: 1917864
zbMATH Keywords: computability
zbMATH Keywords: computable model theory
zbMATH Keywords: ordered groups
reviewed by: Rodney G. Downey
MaRDI profile type: Publication
cites work: Some constructivizations of Abelian groups
cites work: Recursion theory and ordered groups
cites work: Autostability of models
cites work: Q4956005
cites work: Q5509706
cites work: Q3961013
cites work: Q3331204
cites work: Nilpotent groups of finite algorithmic dimension
cites work: Effective content of field theory
cites work: Strong and weak constructivization and computable families
cites work: Computable Algebra, General Theory and Theory of Computable Fields
cites work: Recursively Categorical Linear Orderings
cites work: Recursively enumerable sets and degrees
cites work: Reverse mathematics and fully ordered groups
cites work: \(\Pi_{1}^{0}\) classes and orderable groups
full work available at URL: s0001-8708(02)00042-7
OpenAlex ID: W1983504991
Recommended article: Q4428702
Recommended article: Q4348127
Recommended article: Computable dimension for ordered fields
Recommended article: \(\Pi_{1}^{0}\) classes and orderable groups
Recommended article: Q5295697
Recommended article: Finite computable dimension does not relativize
Recommended article: Q5393788
Recommended article: STACS 2005
Recommended article: Computable Structure Theory
Recommended article: Degrees of autostability for linear orders and linearly ordered abelian groups
description: scientific article; zbMATH DE number 1917864