Computable Reducibility of Equivalence Relations and an Effective Jump Operator

Journal of Symbolic Logic:1-22 (forthcoming)
  Copy   BIBTEX

Abstract

We introduce the computable FS-jump, an analog of the classical Friedman–Stanley jump in the context of equivalence relations on the natural numbers. We prove that the computable FS-jump is proper with respect to computable reducibility. We then study the effect of the computable FS-jump on computably enumerable equivalence relations (ceers).

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 101,795

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

Investigating the Computable Friedman–Stanley Jump.Uri Andrews & Luca San Mauro - 2024 - Journal of Symbolic Logic 89 (2):918-944.
Finitary reducibility on equivalence relations.Russell Miller & Keng Meng Ng - 2016 - Journal of Symbolic Logic 81 (4):1225-1254.
On Polynomial-Time Relation Reducibility.Su Gao & Caleb Ziegler - 2017 - Notre Dame Journal of Formal Logic 58 (2):271-285.
Word problems and ceers.Valentino Delle Rose, Luca San Mauro & Andrea Sorbi - 2020 - Mathematical Logic Quarterly 66 (3):341-354.

Analytics

Added to PP
2022-06-15

Downloads
51 (#432,153)

6 months
15 (#215,221)

Historical graph of downloads
How can I increase my downloads?