The computable dimension of ordered abelian groups. (English) Zbl 1031.03058
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 S. S. Goncharov [e.g., Sov. Math., Dokl. 23, 58-61 (1981; Zbl 0496.20021)], and recently D. R. Hirschfeldt, B. Khoussainov, R. A. Shore and 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 R. Downey and 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.
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 R. Downey and 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.
Reviewer: R.Downey (Wellington)
MSC:
| 03C57 | Computable structure theory, computable model theory |
| 06F20 | Ordered abelian groups, Riesz groups, ordered linear spaces |
References:
| [1] | Dobritsa, V., Some constructivizations of abelian groups, Siberian Math. J., 24, 167-173 (1983) · Zbl 0528.20038 |
| [2] | Downey, R.; Kurtz, S. A., Recursion theory and ordered groups, Ann. Pure Appl. Logic, 32, 137-151 (1986) · Zbl 0629.03020 |
| [3] | Dzgoev, V. D.; Goncharov, S. S., Autostability of models, Algebra and Logic, 19, 28-37 (1980) · Zbl 0468.03023 |
| [4] | Ershov S. S. Goncharov, Y. L., Constructive models, Siberian School of Algebra and Logic (2000), Consultants Bureau: Consultants Bureau New York · Zbl 0954.03036 |
| [5] | Fuchs, L., Partially Ordered Algebraic Systems (1963), Pergamon Press: Pergamon Press Oxford · Zbl 0137.02001 |
| [6] | S.S. Goncharov, Constructive Boolean Algebras, Third All-Union Conference on Mathematical Logic, Novosibirsk, 1974 (in Russian).; S.S. Goncharov, Constructive Boolean Algebras, Third All-Union Conference on Mathematical Logic, Novosibirsk, 1974 (in Russian). |
| [7] | Goncharov, S. S., Groups with a finite number of constructivizations, Soviet Math. Dokl., 23, 58-61 (1981) · Zbl 0496.20021 |
| [8] | S.S. Goncharov, Limit equivalent constructivizations, Mathematical Logic and Theory of Algorithms, “Nauka” Sibirsk. Otdel., Novosibirsk, 1982, pp. 4-12.; S.S. Goncharov, Limit equivalent constructivizations, Mathematical Logic and Theory of Algorithms, “Nauka” Sibirsk. Otdel., Novosibirsk, 1982, pp. 4-12. · Zbl 0543.03017 |
| [9] | Goncharov, S. S.; Molokov, A. V.; Romanovskii, N. S., Nilpotent groups of finite algorithmic dimension, Siberian Math. J., 30, 63-68 (1989) · Zbl 0684.20025 |
| [10] | Kokorin V. Kopytov, A., Fully Ordered Groups (1974), Halsted Press: Halsted Press New York |
| [11] | Larouche, P., Recursively presented Boolean algebras, Notices Amer. Math. Soc., 24, A-552 (1977), (research announcement) |
| [12] | Metakides, G.; Nerode, A., Effective content of field theory, Ann. Math. Logic, 17, 289-320 (1979) · Zbl 0469.03028 |
| [13] | Nurtazin, A. T., Strong and weak constructivizations and enumerable families, Algebra and Logic, 13, 177-184 (1974) · Zbl 0305.02061 |
| [14] | Rabin, M. O., Computable algebra, general theory and theory of computable fields, Trans. Amer. Math. Soc., 95, 341-360 (1960) · Zbl 0156.01201 |
| [15] | Remmel, J. B., Recursively categorical linear orderings, Proc. Amer. Math. Soc., 83, 387-391 (1981) · Zbl 0493.03022 |
| [16] | Soare, R. I., Recursively Enumerable Sets and Degrees (1989), Springer: Springer Berlin · Zbl 0401.03018 |
| [17] | Solomon, R., Reverse mathematics and ordered groups, Notre Dame J. Formal Logic, 39, 157-189 (1998) · Zbl 0973.03076 |
| [18] | Solomon, R., \(Π_1^0\) classes and orderable groups, Ann. Pure Appl. Logic., 115, 279-302 (2002) · Zbl 0998.03036 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
