The computable dimension of ordered abelian groups
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 dimension 1 or \(\infty\). It will have dimension 1 iff it has finite rank. The depth of the arguments is mainly algebraic.
scientific article; zbMATH DE number 1917864
scientific article