Computable Component-wise Reducibility

2013/01/30 by Egor Ianovski, Ianovski, Egor
Computer Science · #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1301.7112

openalex publication_date 2013/01/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider equivalence relations and preorders complete for various levels of the arithmetical hierarchy under computable, component-wise reducibility. We show that implication in first order logic is a complete preorder for \SI 1, the ≤^P_m relation on EXPTIME sets for \SI 2 and the embeddability of computable subgroups of (\QQ,+) for \SI 3. In all cases, the symmetric fragment of the preorder is complete for equivalence relations on the same level. We present a characterisation of \PI 1 equivalence relations which allows us to establish that equality of polynomial time functions and inclusion of polynomial time sets are complete for \PI 1 equivalence relations and preorders respectively. We also show that this is the limit of the enquiry: for n≥ 2 there are no \PI n nor \DE n-complete equivalence relations.

Citations

• Coding Methods in Computability Theory and Complexity Theory
• On Computable Numbers, with an Application to the Entscheidungsproblem

Related

• Analogues of the countable Borel equivalence relations in the setting of computable reducibility
• The Theory of Ceers Computes True Arithmetic
• Minimal Equivalence Relations in Hyperarithmetical and Analytical\n Hierarchies
• Comparing the isomorphism types of equivalence structures and preorders
• There is no classification of the decidably presentable structures