×

Positive equivalences with finite classes and related algebras. (English. Russian original) Zbl 0781.03019

Sib. Math. J. 33, No. 5, 923-927 (1992); translation from Sib. Mat. Zh. 33, No. 5, 196-200 (1992).
Let \(\eta\) be an equivalence over \(\mathbb{N}\); \(\eta\) is called effectively infinite if there is an infinite recursively enumerable set of pairwise non \(\eta\)-equivalent numbers. An algebra is effectively infinite if its numerating equivalence is effectively infinite. It is proved that a positive equivalence is effectively infinite and there is a finitely generated algebra over it if the powers of its classes are bounded by some natural number. Some examples of non-effectively infinite positive algebras locally finite or finitely generated with finite classes of the numerating equivalences are given.

MSC:

03C57 Computable structure theory, computable model theory
03D45 Theory of numerations, effectively presented structures
Full Text: DOI

References:

[1] Yu. L. Ershov, Decision Problems and Constructive Models [in Russian], Nauka, Moscow (1980). · Zbl 0495.03009
[2] A. I. Mal’cev, ?Constructive Algebras. I,? Uspekhi Mat. Nauk, No. 3, 3-60 (1961).
[3] N. Kh. Kasymov and B. M. Khusainov, ?Finitely generated enumerable and absolutely locally finite algebras,? Vychisl. Sistemy,116, 3-15 (1986). · Zbl 0646.03042
[4] N. Kh. Kasymov, ?On algebras with residually finite positively presented extensions,? Algebra i Logika,26, No. 6, 715-730 (1987).
[5] N. Kh. Kasymov, ?On being nonspecifiable by positive formulas for effectively presented data,? Dokl. Akad. Nauk UzSSR,47, No. 6, 4-5 (1989).
[6] Yu. L. Ershov, The Theory of Enumerations [in Russian], Nauka, Moscow (1977).
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.