Finitary reducibility on equivalence relations

DOI10.1017/JSL.2016.23zbMATH Open1403.03070arXiv1406.3646OpenAlexW2963890953MaRDI QIDQ2976331FDOQ2976331

Authors: Keng Meng Ng, Russell Miller 

Publication date: 28 April 2017

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

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.

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

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

zbMATH Keywords

recursion theorycomputabilityequivalence relationscomputable reducibilityfinitary reducibility

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (10)

• Agreement reducibility
• Fine hierarchies and m-reducibilities in theoretical computer science
• On the reducibility of monadic equivalence relations
• Title not available (Why is that?)
• Title not available (Why is that?)
• Infinitary definitions of equivalence relations in models of PA
• ON RELATIVE COMPLETE REDUCIBILITY
• Reducibility of equivalence relations arising from nonstationary ideals under large cardinal assumptions
• On the degree structure of equivalence relations under computable reducibility
• Computable transformations of structures

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)