2019/09/26 by Nikolay Bazhenov, Bazhenov, Nikolay, Manat Mustafa +5
Computer Science · #03D30 #03D55 #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO) #Logic, Reasoning, and Knowledge #Logic, programming, and type systems
paper · pdf · doi:10.48550/arxiv.1909.12247
openalex publication_date 2019/09/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A standard tool for classifying the complexity of equivalence relations on\n\ω is provided by computable reducibility. This reducibility gives rise\nto a rich degree structure. The paper studies equivalence relations, which\ninduce minimal degrees with respect to computable reducibility. Let \Γ be\none of the following classes: \Σ0\α, \Π0\α,\n\Σ1n, or \Π1n, where \α \≥ 2 is a computable ordinal and\nn is a non-zero natural number. We prove that there are infinitely many\npairwise incomparable minimal equivalence relations that are properly in\n\Γ.\n