Primitive recursive equivalence relations and their primitive recursive complexity

Computability (forthcoming)
  Copy   BIBTEX

Abstract

The complexity of equivalence relations has received much attention in the recent literature. The main tool for such endeavour is the following reducibility: given equivalence relations R and S on natural numbers, R is computably reducible to S if there is a computable function f:ω→ω that induces an injective map from R-equivalence classes to S-equivalence classes. In order to compare the complexity of equivalence relations which are computable, researchers considered also feasible variants of computable reducibility, such as the polynomial-time reducibility. In this work, we explore Peq, the degree structure generated by primitive recursive reducibility on primitive recursive equivalence relations with infinitely many equivalence classes. In contrast with all other known degree structures on equivalence relations, we show that Peq has much more structure: e.g., we show that it is a dense distributive lattice. On the other hand, we also offer evidence of the intricacy of Peq, proving, e.g., that the structure is neither rigid nor homogeneous.

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 99,445

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

On Polynomial-Time Relation Reducibility.Su Gao & Caleb Ziegler - 2017 - Notre Dame Journal of Formal Logic 58 (2):271-285.
Finitary reducibility on equivalence relations.Russell Miller & Keng Meng Ng - 2016 - Journal of Symbolic Logic 81 (4):1225-1254.
Investigating the Computable Friedman–Stanley Jump.Uri Andrews & Luca San Mauro - 2024 - Journal of Symbolic Logic 89 (2):918-944.

Analytics

Added to PP
2022-08-04

Downloads
31 (#602,820)

6 months
7 (#541,996)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Luca San Mauro
Università degli Studi di Roma La Sapienza

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references