Finitary reducibility on equivalence relations

DOI10.1017/JSL.2016.23MaRDI QIDQ2976331zbMATH OpenOpenAlexFDO

Authors Keng Meng Ng, Russell Miller

Publication date 28 April 2017

Published in Journal of Symbolic Logic (Search for Journal in Brave)

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

zbMATH Keywords

recursion theorycomputabilityequivalence relationscomputable reducibilityfinitary reducibility

Mathematics Subject Classification ID

Other degrees and reducibilities in computability and recursion theory (03D30)

Abstract: We introduce the notion of finitary computable reducibility on equivalence relations on the natural numbers. This is a weakening of the usual notion of computable reducibility, and we show it to be distinct in several ways. In particular, whereas no equivalence relation can be $P{i}_{n+2}$-complete under computable reducibility, we show that, for every $n$, there does exist a natural equivalence relation which is $P{i}_{n+2}$-complete under finitary reducibility. We also show that our hierarchy of finitary reducibilities does not collapse, and illustrate how it sharpens certain known results. Along the way, we present several new results which use computable reducibility to establish the complexity of various naturally defined equivalence relations in the arithmetical hierarchy.

Recommendations

• The hierarchy of equivalence relations on the natural numbers under computable reducibility
• Equivalence relations that are \(\Sigma^0_3\) complete for computable reducibility (extended abstract)
• Weakly precomplete equivalence relations in the Ershov hierarchy
• On the degree structure of equivalence relations under computable reducibility
• Complexity of equivalence relations and preorders from computability theory

Cites work

• Classification from a Computable Viewpoint
• Comparing Classes of Finite Structures
• Computably enumerable equivalence relations
• On Σ¹ ₁ equivalence relations over the natural numbers
• The effective theory of Borel equivalence relations

Cited in

(16)

• Complexity of equivalence relations and preorders from computability theory
• ON THE STRUCTURE OF COMPUTABLE REDUCIBILITY ON EQUIVALENCE RELATIONS OF NATURAL NUMBERS
• Fine hierarchies and m-reducibilities in theoretical computer science
• Agreement reducibility
• On polynomial-time relation reducibility
• On the reducibility of monadic equivalence relations
• scientific article; zbMATH DE number 1357400 (Why is no real title available?)
• scientific article; zbMATH DE number 2152232 (Why is no real title available?)
• Infinitary definitions of equivalence relations in models of PA
• ON RELATIVE COMPLETE REDUCIBILITY
• The hierarchy of equivalence relations on the natural numbers under computable reducibility
• Reducibility of equivalence relations arising from nonstationary ideals under large cardinal assumptions
• Equivalence relations that are \(\Sigma^0_3\) complete for computable reducibility (extended abstract)
• On the degree structure of equivalence relations under computable reducibility
• Computable transformations of structures
• Minimal equivalence relations in hyperarithmetical and analytical hierarchies

This page was built for publication: Finitary reducibility on equivalence relations

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