Classifying equivalence relations in the Ershov hierarchy
- PDF / 465,882 Bytes
- 30 Pages / 439.37 x 666.142 pts Page_size
- 72 Downloads / 235 Views
Mathematical Logic
Classifying equivalence relations in the Ershov hierarchy Nikolay Bazhenov1,2 · Manat Mustafa3 · Luca San Mauro4 Mars Yamaleev6
· Andrea Sorbi5 ·
Received: 8 October 2018 / Accepted: 10 January 2020 © The Author(s) 2020
Abstract Computably enumerable equivalence relations (ceers) received a lot of attention in the literature. The standard tool to classify ceers is provided by the computable reducibility c . This gives rise to a rich degree structure. In this paper, we lift the study of c-degrees to the 02 case. In doing so, we rely on the Ershov hierarchy. For any notation a for a non-zero computable ordinal, we prove several algebraic properties of the degree structure induced by c on the a−1 a−1 equivalence relations. A special focus of our work is on the (non)existence of infima and suprema of c-degrees. Keywords Computability theory · Ershov hierarchy · 02 equivalence relations · Computably enumerable equivalence relations Mathematics Subject Classification 03D55
1 Introduction Computable reducibility is a longstanding notion that allows classifying equivalence relations on natural numbers according to their complexity. Definition 1.1 Let R, S be equivalence relations with domain ω. R is computably reducible to S, denoted R c S, if there is a computable function f such that, for all x, y ∈ ω, x Ry ⇔ f (x) S f (y).
Bazhenov, Mustafa, and Yamaleev were supported by Nazarbayev University Faculty Development Competitive Research Grants N090118FD5342. Bazhenov was also supported by the Grant of the President of the Russian Federation (No. MK-1214.2019.1). Yamaleev was also supported by Russian Science Foundation Grant, Project 18-11-00028. San Mauro was supported by the Austrian Science Fund FWF, Project M 2461. Sorbi is a member of INDAM-GNSAGA; his research was partially supported by the PSR program of the University of Siena, by the PRIN 2017 Grant “Mathematical Logic: models, sets, computability”, and by the Grant AP05131579 of the Science Committee of the Republic of Kazakhstan. Extended author information available on the last page of the article
123
N. Bazhenov et al.
We write f : R c S to denote that f is a computable function that reduces R to S; c-degrees are introduced in the standard way. The history of computable reducibility has many roots, being often rediscovered and explored in connection with different fields. Its study dates back to the fundamental work of Ershov in the theory of numberings, where the reducibility is introduced in a category-theoretic fashion (see Ershov’s monograph [11] in Russian, or [12] for an English survey). In the 1980s, computable reducibility proved to be a fruitful tool for calibrating the complexity of provable equivalence of formal systems and scholars focused mostly on the 10 case (see, e.g., [5,19,26]). Following Gao and Gerdes [17], we adopt the acronym “ceers” to refer to computably enumerable equivalence relations. The interested reader can consult Andrews et al. [1] for a nice and up-to-date survey on ceers, with a special
Data Loading...
