Minimal Equivalence Relations in Hyperarithmetical and Analytical Hierarchies
| Autor: | L. San Mauro, Manat Mustafa, Nikolay Bazhenov, Mars M. Yamaleev |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
computable reducibility
General Mathematics 010102 general mathematics Natural number minimal degree 01 natural sciences 010305 fluids & plasmas analytical hierarchy equivalence relation hyperarithmetical hierarchy Combinatorics Degree structure 0103 physical sciences Analytical hierarchy Equivalence relation 0101 mathematics Algebra over a field Mathematics |
| Zdroj: | Lobachevskii Journal of Mathematics. 41:145-150 |
| ISSN: | 1818-9962 1995-0802 |
| DOI: | 10.1134/s199508022002002x |
| Popis: | 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$$ . |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink