Abstract
In this paper we study the reducibility order ⩽ m (defined in a natural way) over ∑ 0n -equivalence relations. In particular, for every n> 0 we exhibit ∑ 0n -equivalence relations which are complete with respect to ⩽m and investigate some consequences of this fact (see Introduction).
Article PDF
Similar content being viewed by others
References
C. Bernardi, On the relation provable equivalence and on partitions in effectively inseparable sets, Studio Logica 40 (1981), pp. 29–37.
C. Bernardi and A. Sorbi, Classifying positive equivalence relations, to appear in Journal of Symbolic Logic (1983).
Ju. L. Ersov, Theorie der Numerierungen I, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 19 (1973), pp. 289–388.
Ju. L. Ersov, Theorie der Numerierungen II, Zeitschrift für Mathematische Logik und Grudlagen der Mathematik 21 (1975), pp. 473–584.
Ju. L. Ersov, Positive equivalences (English, translation), Algebra and Logic, 10 (1973), pp. 378–394.
P. G. Hinman, Recursion-Theoretic Hierarchies, Springer-Verlag, Heidelberg.
C. F. Kent, The relation of A to Prov ⌈A⌉ in the Lindenbaum sentence algebra, Journal of Symbolic Logic 38 (1973), pp. 295–298.
H. Rogers, Theory of Recursive Functions and Effective Camputability, McGraw Hill, New York 1967.
A. Sorbi, Numerazioni positive, r. e. classi e formule, Bollettino del-Unione Matematica Italiana, Suppl. Vol. 1 (1982), pp. 79–88.
A. Visser, Numerations, λ-Calculus and Arithmetic, Fert. for H. B. Curry (Hindley, Seldin editors), Academic Press 1980, pp. 259–284.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Sorbi, A. ∑ n0 -equivalence relations. Stud Logica 41, 351–358 (1982). https://doi.org/10.1007/BF00403335
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF00403335