Independence in computable algebra. (English) Zbl 1386.03051
Summary: We give a sufficient condition for an algebraic structure to have a computable presentation with a computable basis and a computable presentation with no computable basis. We apply the condition to differentially closed, real closed, and difference closed fields with the relevant notions of independence. To cover these classes of structures we introduce a new technique of safe extensions that was not necessary for the previously known results of this kind. We will then apply our techniques to derive new corollaries on the number of computable presentations of these structures. The condition also implies classical and new results on vector spaces, algebraically closed fields, torsion-free abelian groups and Archimedean ordered abelian groups.
MSC:
| 03D45 | Theory of numerations, effectively presented structures |
| 03C57 | Computable structure theory, computable model theory |
| 12Y05 | Computational aspects of field theory and polynomials (MSC2010) |
References:
| [1] | Aliprantis, C. D.; Burkinshaw, O., Principles of Real Analysis (1998), Academic Press · Zbl 1006.28001 |
| [2] | Ash, C. J.; Knight, J., Computable Structures and the Hyperarithmetical Hierarchy, Stud. Logic Found. Math., vol. 144 (2000), North-Holland Publishing Co.: North-Holland Publishing Co. Amsterdam · Zbl 0960.03001 |
| [3] | Ash, Chris; Knight, Julia; Manasse, Mark; Slaman, Theodore, Generic copies of countable structures, Ann. Pure Appl. Logic, 42, 3, 195-205 (1989) · Zbl 0678.03012 |
| [4] | Blum, Lenore, Generalized Algebraic Structures: A Model Theoretic Approach (1968), Massachussetts Institute of Technology: Massachussetts Institute of Technology Cambridge, MA, PhD thesis · Zbl 0368.12013 |
| [5] | Chatzidakis, Zoé; Hrushovski, Ehud, Model theory of difference fields, Trans. Amer. Math. Soc., 351, 8, 2997-3071 (1999) · Zbl 0922.03054 |
| [6] | Chisholm, John, Effective model theory vs. recursive model theory, J. Symbolic Logic, 55, 3, 1168-1191 (1990) · Zbl 0722.03030 |
| [7] | Cohn, Richard M., Difference Algebra (1965), Interscience Publishers John Wiley & Sons: Interscience Publishers John Wiley & Sons New York, London, Sydney · Zbl 0127.26402 |
| [8] | Conidis, Chris J.; Shore, Richard A., The complexity of ascendant sequences in locally nilpotent groups, Internat. J. Algebra Comput., 24, 2, 189-205 (2014) · Zbl 1350.03035 |
| [9] | Dekker, J. C.E., Countable vector spaces with recursive operations. I, J. Symbolic Logic, 34, 363-387 (1969) · Zbl 0185.02003 |
| [10] | Dekker, J. C.E., Countable vector spaces with recursive operations. II, J. Symbolic Logic, 36, 477-493 (1971) · Zbl 0231.02052 |
| [11] | Dekker, J. C.E., Two notes on vector spaces with recursive operations, Notre Dame J. Form. Log., 12, 329-334 (1971) · Zbl 0205.30802 |
| [12] | Downey, Rodney; Melnikov, Alexander G., Computable completely decomposable groups, Trans. Amer. Math. Soc., 366, 8, 4243-4266 (2014) · Zbl 1341.03056 |
| [13] | Dobritsa, V. P., Some constructivizations of abelian groups, Sibirsk. Mat. Zh., 24, 2, 18-25 (1983) · Zbl 0528.20038 |
| [14] | Downey, Rod, Bases of supermaximal subspaces and Steinitz systems. I, J. Symbolic Logic, 49, 4, 1146-1159 (1984) · Zbl 0585.03017 |
| [15] | Downey, R. G.; Remmel, J. B., Computable algebras and closure systems: coding properties, (Handbook of Recursive Mathematics, vol. 2. Handbook of Recursive Mathematics, vol. 2, Stud. Logic Found. Math., vol. 139 (1998), North-Holland: North-Holland Amsterdam), 977-1039 · Zbl 0939.03046 |
| [16] | Ershov, Yuri L.; Goncharov, Sergei S., Constructive Models (2000), Siberian School of Algebra and Logic, Consultants Bureau: Siberian School of Algebra and Logic, Consultants Bureau New York · Zbl 0954.03036 |
| [17] | Fröhlich, A.; Shepherdson, J. C., Effective procedures in field theory, Philos. Trans. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci., 248, 407-432 (1956) · Zbl 0070.03502 |
| [18] | Fuchs, L., Partially Ordered Algebraic Systems (1963), Pergamon Press, Addison-Wesley Publishing Co., Inc.: Pergamon Press, Addison-Wesley Publishing Co., Inc. Oxford, London, New York, Paris, Reading, MA, Palo Alto, CA, London · Zbl 0137.02001 |
| [19] | Fuchs, László, Infinite Abelian Groups, Pure Appl. Math., vol. 36 (1970), Academic Press: Academic Press New York, London, vol. I · Zbl 0209.05503 |
| [20] | Fuchs, László, Infinite Abelian Groups, Pure Appl. Math., vol. 36 (1973), Academic Press: Academic Press New York, London, vol. II · Zbl 0257.20035 |
| [21] | Goncharov, Sergey S.; Lempp, Steffen; Solomon, Reed, The computable dimension of ordered abelian groups, Adv. Math., 175, 1, 102-143 (2003) · Zbl 1031.03058 |
| [22] | Gončarov, S. S., Autostability of models and abelian groups, Algebra Logika, 19, 1, 23-44 (1980), 132 · Zbl 0468.03022 |
| [23] | Goncharov, S. S., Limit equivalent constructivizations, (Mathematical Logic and the Theory of Algorithms. Mathematical Logic and the Theory of Algorithms, Tr. Inst. Mat., vol. 2 (1982), “Nauka” Sibirsk. Otdel: “Nauka” Sibirsk. Otdel Novosibirsk), 4-12 · Zbl 0543.03017 |
| [24] | Harrington, Leo, Recursively presentable prime models, J. Symbolic Logic, 39, 305-309 (1974) · Zbl 0332.02055 |
| [25] | Haskell, Deirdre; Hrushovski, Ehud; Macpherson, Dugald, Stable Domination and Independence in Algebraically Closed Valued Fields, Lect. Notes Log., vol. 30 (2008), Association for Symbolic Logic, Cambridge University Press: Association for Symbolic Logic, Cambridge University Press Chicago, IL, Cambridge · Zbl 1149.03027 |
| [26] | Higman, G., Subgroups of finitely presented groups, Proc. R. Soc. Lond. Ser. A, 262, 455-475 (1961) · Zbl 0104.02101 |
| [27] | Hölder, Otto, The axioms of quantity and the theory of measurement, J. Math. Psych., 40, 3, 235-252 (1996), Translated from the 1901 German original and with notes by Joel Michell and Catherine Ernst. With an introduction by Michell · Zbl 0889.92035 |
| [28] | Jones, Gareth; Servi, Tamara, On the decidability of the real field with a generic power function, J. Symbolic Logic, 76, 4, 1418-1428 (2011) · Zbl 1261.03123 |
| [29] | Kaplansky, Irving, Infinite Abelian Groups (1969), The University of Michigan Press: The University of Michigan Press Ann Arbor, MI · Zbl 0194.04402 |
| [30] | Khisamiev, N. G., Constructive abelian groups, (Handbook of Recursive Mathematics, vol. 2. Handbook of Recursive Mathematics, vol. 2, Stud. Logic Found. Math., vol. 139 (1998), North-Holland: North-Holland Amsterdam), 1177-1231 · Zbl 0940.03044 |
| [31] | Khisamiev, N. G., On a class of strongly decomposable abelian groups, Algebra Logika, 41, 4, 493-509 (2002), 511-512 · Zbl 1018.03031 |
| [32] | Ivanovič Kokorin, Ali; Matveevič Kopytov, Valeriī, Fully Ordered Groups (1974), Halsted Press [John Wiley & Sons], Israel Program for Scientific Translations: Halsted Press [John Wiley & Sons], Israel Program for Scientific Translations New York, Toronto, ON, Jerusalem, London, Translated from Russian by D. Louvish |
| [33] | Knight, Julia F.; Lange, Karen, Complexity of structures associated with real closed fields, Proc. Lond. Math. Soc. (3), 107, 1, 177-197 (2013) · Zbl 1294.03029 |
| [34] | Knight, Julia F.; Pillay, Anand; Steinhorn, Charles, Definable sets in ordered structures. II, Trans. Amer. Math. Soc., 295, 2, 593-605 (1986) · Zbl 0662.03024 |
| [36] | Mal’cev, A. I., Constructive algebras. I, Uspekhi Mat. Nauk, 16, 3 (99), 3-60 (1961) · Zbl 0129.25903 |
| [37] | Mal’cev, A. I., On recursive Abelian groups, Dokl. Akad. Nauk SSSR, 146, 1009-1012 (1962) · Zbl 0156.01105 |
| [38] | Marker, D., Model Theory: An Introduction, Grad. Texts in Math. (2002), Springer · Zbl 1003.03034 |
| [39] | Melnikov, Alexander G., Computable abelian groups, Bull. Symbolic Logic, 20, 3, 315-356 (2014) · Zbl 1345.03065 |
| [42] | Marker, David; Messmer, Margit; Pillay, Anand, Model Theory of Fields, Lect. Notes Log., vol. 5 (2006), Association for Symbolic Logic, A.K. Peters, Ltd.: Association for Symbolic Logic, A.K. Peters, Ltd. La Jolla, CA, Wellesley, MA · Zbl 1104.12006 |
| [43] | Metakides, G.; Nerode, A., Recursively enumerable vector spaces, Ann. Math. Logic, 11, 2, 147-171 (1977) · Zbl 0389.03019 |
| [44] | Metakides, G.; Nerode, A., Effective content of field theory, Ann. Math. Logic, 17, 3, 289-320 (1979) · Zbl 0469.03028 |
| [45] | Montalbán, Antonio, Rice sequences of relations, Philos. Trans. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci., 370, 3464-3487 (1971), 2012 · Zbl 1329.03072 |
| [46] | Macintyre, Angus; Wilkie, A. J., On the decidability of the real exponential field, (Kreiseliana (1996), A.K. Peters: A.K. Peters Wellesley, MA), 441-467 · Zbl 0896.03012 |
| [47] | Nurtazin, A. T., Computable classes and algebraic criteria of autostability (1974), Novosibirsk |
| [48] | Pillay, Anand, Geometric Stability Theory, Oxford Logic Guides, vol. 32 (1996), The Clarendon Press, Oxford University Press: The Clarendon Press, Oxford University Press New York, Oxford Science Publications · Zbl 0871.03023 |
| [49] | Pillay, Anand; Steinhorn, Charles, Definable sets in ordered structures. I, Trans. Amer. Math. Soc., 295, 2, 565-592 (1986) · Zbl 0662.03023 |
| [50] | Pila, J.; Wilkie, A. J., The rational points of a definable set, Duke Math. J., 133, 3, 591-616 (2006) · Zbl 1217.11066 |
| [51] | Rabin, Michael O., Computable algebra, general theory and theory of computable fields, Trans. Amer. Math. Soc., 95, 341-360 (1960) · Zbl 0156.01201 |
| [52] | Fels Ritt, Joseph, Differential Algebra, Amer. Math. Soc. Colloq. Publ., vol. XXXIII (1950), American Mathematical Society: American Mathematical Society New York, NY · Zbl 0037.18402 |
| [53] | Robinson, Abraham, On the concept of a differentially closed field, Bull. Res. Council Israel Sect. F, 8, 113-128 (1959) · Zbl 0221.12054 |
| [54] | Shore, Richard A., Controlling the dependence degree of a recursively enumerable vector space, J. Symbolic Logic, 43, 1, 13-22 (1978) · Zbl 0399.03032 |
| [55] | Simpson, Stephen G., Subsystems of Second Order Arithmetic, Perspect. Math. Logic (1999), Springer-Verlag: Springer-Verlag Berlin · Zbl 0909.03048 |
| [56] | Tarski, Alfred, A Decision Method for Elementary Algebra and Geometry (1948), RAND Corporation: RAND Corporation Santa Monica, CA · Zbl 0035.00602 |
| [57] | van den Dries, Lou, Tame Topology and o-Minimal Structures, London Math. Soc. Lecture Note Ser., vol. 248 (1998), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0953.03045 |
| [58] | van der Waerden, Bartel L., Eine Bemerkung über die Unzerlegbarkeit von Polynomen, Math. Ann., 102, 1, 738-739 (1930) · JFM 56.0825.05 |
| [59] | Whitney, Hassler, On the abstract properties of linear dependence, Amer. J. Math., 57, 3, 509-533 (1935) · Zbl 0012.00404 |
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.
