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).

Categories

Keywords

Reprint years

DOI

10.1017/jsl.2022.45

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,164

External links

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

Through your library

My notes

Similar books and articles

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.
On the Degree Structure of Equivalence Relations Under Computable Reducibility.Keng Meng Ng & Hongyuan Yu - 2019 - Notre Dame Journal of Formal Logic 60 (4):733-761.
On Σ1 1 equivalence relations over the natural numbers.Ekaterina B. Fokina & Sy-David Friedman - 2012 - Mathematical Logic Quarterly 58 (1-2):113-124.
Infinite Time Decidable Equivalence Relation Theory.Samuel Coskey & Joel David Hamkins - 2011 - Notre Dame Journal of Formal Logic 52 (2):203-228.
Complexity of equivalence relations and preorders from computability theory.Egor Ianovski, Russell Miller, Keng Meng Ng & André Nies - 2014 - Journal of Symbolic Logic 79 (3):859-881.
The effective theory of Borel equivalence relations.Ekaterina B. Fokina, Sy-David Friedman & Asger Törnquist - 2010 - Annals of Pure and Applied Logic 161 (7):837-850.
Classifying equivalence relations in the Ershov hierarchy.Nikolay Bazhenov, Manat Mustafa, Luca San Mauro, Andrea Sorbi & Mars Yamaleev - 2020 - Archive for Mathematical Logic 59 (7-8):835-864.
Constructive equivalence relations on computable probability measures.Laurent Bienvenu & Wolfgang Merkle - 2009 - Annals of Pure and Applied Logic 160 (3):238-254.
Realizing Levels of the Hyperarithmetic Hierarchy as Degree Spectra of Relations on Computable Structures.Walker M. White & Denis R. Hirschfeldt - 2002 - Notre Dame Journal of Formal Logic 43 (1):51-64.
On the Structure of Computable Reducibility on Equivalence Relations of Natural Numbers.Uri Andrews, Daniel F. Belin & Luca San Mauro - 2023 - Journal of Symbolic Logic 88 (3):1038-1063.
? 0 N -equivalence relations.Andrea Sorbi - 1982 - Studia Logica 41 (4):351-358.
Turing computable embeddings.Julia Knight, Sara Miller & M. Vanden Boom - 2007 - Journal of Symbolic Logic 72 (3):901-918.
Turing computable embeddings.F. Knight Julia, Miller Sara & M. Vanden Boom - 2007 - Journal of Symbolic Logic 72 (3):901-918.
Classifications of Computable Structures.Karen Lange, Russell Miller & Rebecca M. Steiner - 2018 - Notre Dame Journal of Formal Logic 59 (1):35-59.

Analytics

Added to PP
2022-06-15

Downloads
15 (#884,991)

6 months
9 (#235,983)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Add more citations

References found in this work

Classifying positive equivalence relations.Claudio Bernardi & Andrea Sorbi - 1983 - Journal of Symbolic Logic 48 (3):529-538.

View all 7 references / Add more references