Minimal equivalence relations in hyperarithmetical and analytical hierarchies

DOI10.1134/S199508022002002XMaRDI QIDQ2207013zbMATH OpenOpenAlexFDO

Authors Luca San Mauro, M. M. Yamaleev, Nikolay Bazhenov, Mustafa Manat

Publication date 27 October 2020

Published in Lobachevskii Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1909.12247

zbMATH Keywords

analytical hierarchycomputable reducibilityequivalence relationhyperarithmetical hierarchyminimal degree

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30) Theory of numerations, effectively presented structures (03D45)

Abstract: 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: $Sigm{a}_{alpha}^0$, $P{i}_{alpha}^0$, $Sigm{a}_n^1$, or $P{i}_n^1$, where $alphageq2$ 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$.

Recommendations

• Classifying equivalence relations in the Ershov hierarchy
• The hierarchy of equivalence relations on the natural numbers under computable reducibility
• Finitary reducibility on equivalence relations
• On Σ¹ ₁ equivalence relations over the natural numbers
• Weakly precomplete equivalence relations in the Ershov hierarchy

Cites work

• A survey on universal computably enumerable equivalence relations
• Classifying equivalence relations in the Ershov hierarchy
• Classifying positive equivalence relations
• Complexity of equivalence relations and preorders from computability theory
• Computable isomorphisms of distributive lattices
• Computably enumerable equivalence relations
• Equivalence relations that are ^0_3 complete for computable reducibility (extended abstract)
• scientific article; zbMATH DE number 4091484 (Why is no real title available?)
• scientific article; zbMATH DE number 194101 (Why is no real title available?)
• Isomorphism relations on computable structures
• Joins and meets in the structure of ceers
• Jumps of computably enumerable equivalence relations
• On the degree structure of equivalence relations under computable reducibility
• On the relation provable equivalence and on partitions in effectively inseparable sets
• Positive equivalences
• Weakly precomplete equivalence relations in the Ershov hierarchy

Cited in

(8)

• Jumps of computably enumerable equivalence relations
• Classifying equivalence relations in the Ershov hierarchy
• Degree-invariant, analytic equivalence relations without perfectly many classes
• Non-cuppable enumeration degrees via finite injury
• The hierarchy of equivalence relations on the natural numbers under computable reducibility
• Computable embeddability for algebraic structures
• ON THE STRUCTURE OF COMPUTABLE REDUCIBILITY ON EQUIVALENCE RELATIONS OF NATURAL NUMBERS
• Computably enumerable equivalence relations via primitive recursive reductions

This page was built for publication: Minimal equivalence relations in hyperarithmetical and analytical hierarchies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2207013)