×

Uniform \(m\)-equivalencies and numberings of classical systems. (English) Zbl 07483032

Summary: The paper considers the representability of algebraic structures (groups, lattices, semigroups, etc.) over equivalence relations on natural numbers. The concept of a (uniform) \(m\)-equivalence is studied. It is proved that the numbering equivalence of any numbered group is a uniform \(m\)-equivalence. On the other hand, we construct an example of a uniform \(m\)-equivalence over which no group is representable. Additionally we show that there exists a positive equivalence over which no upper (lower) semilattice is representable.

MSC:

03D45 Theory of numerations, effectively presented structures
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A.I. Mal’tsev, Strongly related models and recursively complete algebras, Sov. Math., Dokl., 3 (1962), 987991. Zbl 0132.24702
[2] A.I. Mal’tsev, On recursive abelian groups, Sov. Math., Dokl., 32 (1962), 14311434. Zbl 0156.01105 · Zbl 0156.01105
[3] A.S. Morozov, Computable groups of automorphisms of models, Algebra Logic, 25 (1986), 261266. Zbl 0631.03019 · Zbl 0631.03019
[4] A.S. Morozov, Elementary properties of groups of recursive permutations, Sov. Math., Dokl., 39:2 (1989), 282284. Zbl 0692.03024 · Zbl 0692.03024
[5] A.S. Morozov, On the theories of classes of recursive permutations groups, Sib. Adv. Math., 1:1 (1991), 138153. Zbl 0717.03012
[6] A.S. Morozov, Groups of computable automorphisms, in: Yu.L. Ershov (ed.) et al., Handbook of recursive mathematics, vol. 1: Recursive model theory, Stud. Log. Found. Math., 138, Elsevier, Amsterdam, 1998, 311345. Zbl 0940.03047 · Zbl 0940.03047
[7] A.S. Morozov, J.K. Truss, On computable automorphisms of the rational numbers, J. Symb. Log., 66:3 (2001), 14581470. Zbl 0990.03034 · Zbl 0990.03034
[8] V. Harizanov, R. Miller, A.S. Morozov, Simple structures with complex symmetry, Algebra Logic, 49:1 (2010), 6890. Zbl 1195.03041 · Zbl 1195.03041
[9] A.S. Morozov, Higman’s question revisited, Algebra Logic, 39:2 (2000), 7883. Zbl 0956.20025 · Zbl 0956.20025
[10] N.G. Khisamiev, On positive and constructive groups, Sib. Math. J., 53:5 (2012), 906917. Zbl 1260.03084 · Zbl 1260.03084
[11] N.G. Khisamiev, Arithmetic hierarchy of abelian groups, Sib. Math. J., 29:6 (1988), 987999. Zbl 0679.20047 · Zbl 0679.20047
[12] S.S. Goncharov, Yu.L. Ershov, Constructive models, Siberian School of Algebra and Logic, Consultants Bureau, New York, 2000. Zbl 0954.03036 · Zbl 0954.03036
[13] Yu.L. Ershov, Theory of numerations, Nauka, Moscow, 1977. MR0506676
[14] S.S. Goncharov, Computability and computable models, in Gabbay, Dov M. (ed.) et al., Mathematical Problems from Applied Logic. II. Logics for the XXIst Century, Springer, New York, 2007, 99216. Zbl 1143.03017 · Zbl 1143.03017
[15] N.Kh. Kasymov, A.S. Morozov, Denability of linear orders over negative equivalences, Algebra Logic, 55:1 (2016), 2437. Zbl 1358.03043 · Zbl 1358.03043
[16] N.Kh. Kasymov, Recursively separable enumerated algebras, Russ. Math. Surv., 51:3 (1996), 509538. Zbl 0878.03034 · Zbl 0878.03034
[17] N.Kh. Kasymov, Homomorphisms onto eectively separable algebras, Sib. Math. J., 57:1 (2016), 3650. Zbl 1377.03035 · Zbl 1377.03035
[18] N.Kh. Kasymov, A.S. Morozov, I.A. Khodzhamuratova,T1-separable enumarations of subdirectly indecomposable algebras, Algebra Logika, 60:4 (2021), 400424. · Zbl 1515.03164
[19] B.M. Khoussainov, T. Slaman, P. Semukhin,Q01-presentasions of algebras, Arch. Math. Logic, 45:6 (2006), 769781. Zbl 1099.03025 · Zbl 1099.03025
[20] N.Kh. Kasymov, B.M. Khoussainov, Finitely generated, enumerable and absolutely locally nite algebras, Vychisl. Sist., 116 (1986), 315. Zbl 0646.03042
[21] N.Kh. Kasymov, R.N. Dadazhanov, Negative dense linear orders, Sib. Math. J., 58:6 (2017), 10151033. Zbl 1469.03124 · Zbl 1469.03124
[22] N.Kh. Kasymov, Algebras over negative equivalences, Algebra Logic, 33:1 (1994), 4648. Zbl 0820.03027 · Zbl 0820.03027
[23] N.Kh. Kasymov, F.N. Ibragimov, Separable enumerations of division rings and eective embeddability of rings therin, Sib. Math. J., 60:1 (2019), 6270. Zbl 7079960 · Zbl 1477.03146
[24] E.B. Fokina, B.M. Khoussainov, P. Semukhin, D. Turetskiy, Linear orders realized by c.e. equivalence relations, J. Symb. Log., 81:2 (2016), 463482. Zbl 1371 · Zbl 1371.03049
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.