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

    This entry is not archived by us. If you are the author and have permission from the publisher, we recommend that you archive it. Many publishers automatically grant permission to authors to archive pre-prints. By uploading a copy of your work, you will enable us to better index it, making it easier to find.

    Upload a copy of this work     Papers currently archived: 103,792

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.
Word problems and ceers.Valentino Delle Rose, Luca San Mauro & Andrea Sorbi - 2020 - Mathematical Logic Quarterly 66 (3):341-354.
On Polynomial-Time Relation Reducibility.Su Gao & Caleb Ziegler - 2017 - Notre Dame Journal of Formal Logic 58 (2):271-285.

Analytics

Added to PP
2022-06-15

Downloads
52 (#453,027)

6 months
10 (#359,270)

Historical graph of downloads
How can I increase my downloads?