zbMATH — the first resource for mathematics

Generalized semilattices and $$m$$-degrees of index sets. II. (English. Russian original) Zbl 0781.06007
Algebra Logic 30, No. 2, 110-119 (1991); translation from Algebra Logika 30, No. 2, 168-180 (1991).
[For part I see Algebra Logika 28, No. 5, 555-569 (1989; Zbl 0708.06005).]
Let $$L$$ be a semilattice. A congruence $$\theta\subseteq L\times L$$ is called distributive if $$\theta(a)\leq \theta(b)\Rightarrow(\exists c\in \theta(a))(c\leq b)$$, and is called countable if for each $$a\in L$$ the class $$\theta(a)$$ is at most countable. Theorem 1. Let $$L$$ be a $$c$$- universal semilattice and $$\theta$$ a countable congruence on $$L$$. Then $$L/\theta$$ is pseudo-$$c$$-universal. This result is applied to the generalized semilattice of the $$m$$-degrees of families of partial recursive functions or of their index sets.
MSC:
 06A12 Semilattices 03D30 Other degrees and reducibilities in computability and recursion theory
Full Text:
References:
 [1] T. M. Kuz’mina, ”On generalized semilattices andm-degrees of index sets,” Algebra Logika,28, No. 5, 555–569 (1989). [2] Yu. L. Ershov, Theory of Numerations [in Russian], Nauka, Moscow (1977). [3] T. M. Kuz’mina, ”Relations between reducibilities of index sets,” Izv. Vyssh. Uchebn. Zaved. Mat., No. 1, 60–69 (1989). · Zbl 0682.03028 [4] T. M. Kuz’mina, ”The structure ofm-degrees of index sets of families of partially recursive functions,” Algebra Logika,20, No. 1, 55–68 (1981). [5] An. A. Mal’tsev, ”Upper semilattices of numerations,” Preprint, Novosibirsk (1980). [6] T. M. Kuz’mina, ”Some remarks on complete numerations and index sets,” in: Second All-Union Conference on Applied Logic, Novosibirsk (1988), pp. 122–124. [7] T. M. Kuz’mina, ”Reducibility by morphisms,” in: Probabilistic Methods and Cybernetics [in Russian], Kazan’ (1983), pp. 29–38. [8] V. L. Selivanov, ”On the structure of degrees of generalized index sets,” Algebra Logika,21, No. 4, 472–491 (1982). [9] V. L. Selivanov, ”On index sets in the Kleene-Mostowski hierarchy,” in: Mathematical Logic and the Theory of Algorithms, Tr. Inst. Mat., Nauka, Sib. Otdel., Novosibirsk (1982), pp. 135–158.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.