×

Minimal equivalence relations in hyperarithmetical and analytical hierarchies. (English) Zbl 1469.03116

Summary: A standard tool for classifying the complexity of equivalence relations on \(\omega\) is provided by computable reducibility. This reducibility gives rise to a rich degree structure. The paper studies equivalence relations, which induce minimal degrees with respect to computable reducibility. Let \(\Gamma\) be one of the following classes: \( \Sigma^0_{\alpha}\), \(\Pi^0_{\alpha}\), \(\Sigma^1_n\), or \(\Pi^1_n\), where \(\alpha\geq 2\) is a computable ordinal and \(n\) is a non-zero natural number. We prove that there are infinitely many pairwise incomparable minimal equivalence relations that are properly in \(\Gamma \).

MSC:

03D25 Recursively (computably) enumerable sets and degrees
03D30 Other degrees and reducibilities in computability and recursion theory
03D45 Theory of numerations, effectively presented structures
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ershov, Yu. L., Positive equivalences, Algebra Logic, 10, 378-394 (1971) · Zbl 0276.02024 · doi:10.1007/BF02218645
[2] Ershov, Yu. L., Theory of Numberings (1977), Moscow: Nauka, Moscow
[3] Bernardi, C., On the relation provable equivalence and on partitions in effectively inseparable sets, Stud. Log., 40, 29-37 (1981) · Zbl 0468.03020 · doi:10.1007/BF01837553
[4] Bernardi, C.; Sorbi, A., Classifying positive equivalence relations, J. Symb. Logic, 48, 529-538 (1983) · Zbl 0528.03030 · doi:10.2307/2273443
[5] Gao, S.; Gerdes, P., Computably enumerable equivalence relations, Stud. Log., 67, 27-59 (2001) · Zbl 0981.03046 · doi:10.1023/A:1010521410739
[6] Andrews, U.; Sorbi, A., Joins and meets in the structure of ceers, Computability, 8, 193-241 (2019) · Zbl 1454.03048 · doi:10.3233/COM-180098
[7] Andrews, U.; Badaev, S.; Sorbi, A., A survey on universal computably enumerable equivalence relations, Lect. Notes Comput. Sci., 10010, 418-451 (2017) · Zbl 1485.03146 · doi:10.1007/978-3-319-50062-1_25
[8] Andrews, U.; Sorbi, A., Jumps of computably enumerable equivalence relations, Ann. Pure Appl. Logic, 169, 243-259 (2018) · Zbl 1406.03055 · doi:10.1016/j.apal.2017.12.001
[9] Ng, K. M.; Yu, H., On the degree structure of equivalence relations under computable reducibility, Notre Dame J. Formal Logic, 60, 733-761 (2019) · Zbl 1472.03039 · doi:10.1215/00294527-2019-0028
[10] N. Bazhenov, M. Mustafa, L. San Mauro, A. Sorbi, and M. Yamaleev, ‘‘Classifying equivalence relations in the Ershov hierarchy,’’ Arch. Math. Logic (in press). · Zbl 1461.03041
[11] Bazhenov, N. A.; Kalmurzaev, B. S., Weakly precomplete equivalence relations in the Ershov hierarchy, Algebra Logic, 58, 199-213 (2019) · Zbl 1485.03170 · doi:10.1007/s10469-019-09538-y
[12] Fokina, E.; Friedman, S.; Nies, A., Equivalence relations that are \(\Sigma^0_3\), Lect. Notes Comput. Sci., 7456, 26-33 (2012) · Zbl 1362.03032 · doi:10.1007/978-3-642-32621-9_2
[13] Ianovski, E.; Miller, R.; Ng, K. M.; Nies, A., Complexity of equivalence relations and preorders from computability theory, J. Symb. Logic, 79, 859-881 (2014) · Zbl 1353.03043 · doi:10.1017/jsl.2013.33
[14] Bazhenov, N.; Mustafa, M.; Yamaleev, M., Computable isomorphisms of distributive lattices, Lect. Notes Comput. Sci., 11436, 28-41 (2019) · Zbl 1528.03184 · doi:10.1007/978-3-030-14812-6_3
[15] Fokina, E. B.; Friedman, S.; Harizanov, V.; Knight, J. F.; McCoy, C.; Montalbn, A., Isomorphism relations on computable structures, J. Symb. Logic, 77, 122-132 (2012) · Zbl 1255.03040 · doi:10.2178/jsl/1327068695
[16] Soare, R. I., Recursively Enumerable Sets and Degrees (1987), Berlin: Springer, Berlin · Zbl 0667.03030
[17] Sacks, G. E., Higher Recursion Theory (1990), Berlin: Springer, Berlin · Zbl 0716.03043
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.