Recursively Enumerable Equivalence Relations Modulo Finite Differences

Mathematical Logic Quarterly 40 (4):490-518 (1994)
  Copy   BIBTEX

Abstract

We investigate the upper semilattice Eq* of recursively enumerable equivalence relations modulo finite differences. Several natural subclasses are shown to be first-order definable in Eq*. Building on this we define a copy of the structure of recursively enumerable many-one degrees in Eq*, thereby showing that Th has the same computational complexity as the true first-order arithmetic

Categories

Keywords

Reprint years

DOI

10.1002/malq.19940400407

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 100,448

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

On Some Properties of Recursively Enumerable Equivalence Relations.Stefano Baratella - 1989 - Mathematical Logic Quarterly 35 (3):261-268.
The category of equivalence relations.Luca San Mauro, Valentino Delle Rose & Andrea Sorbi - 2021 - Algebra and Logic 5 (60):295-307.
The role of true finiteness in the admissible recursively enumerable degrees.Noam Greenberg - 2005 - Bulletin of Symbolic Logic 11 (3):398-410.
Interpreting true arithmetic in the theory of the r.e. truth table degrees.André Nies & Richard A. Shore - 1995 - Annals of Pure and Applied Logic 75 (3):269-311.
On recursive enumerability with finite repetitions.Stephan Wehner - 1999 - Journal of Symbolic Logic 64 (3):927-945.
Complete, Recursively Enumerable Relations in Arithmetic.Giovanna D'Agostino & Mario Magnago - 1995 - Mathematical Logic Quarterly 41 (1):65-72.
Definability of Recursively Enumerable Sets in Abstract Computational Complexity Theory.Robert E. Byerly - 1984 - Mathematical Logic Quarterly 30 (32-34):499-503.
On a Class of Recursively Enumerable Sets.Farzad Didehvar - 1999 - Mathematical Logic Quarterly 45 (4):467-470.
On a Class of Recursively Enumerable Sets.Farzad Didevhar - 1999 - Mathematical Logic Quarterly 45 (4):467-470.
The theory of the recursively enumerable weak truth-table degrees is undecidable.Klaus Ambos-Spies, André Nies & Richard A. Shore - 1992 - Journal of Symbolic Logic 57 (3):864-874.

Analytics

Added to PP
2013-11-03

Downloads
36 (#618,808)

6 months
4 (#1,232,162)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

The theory of ceers computes true arithmetic.Uri Andrews, Noah Schweber & Andrea Sorbi - 2020 - Annals of Pure and Applied Logic 171 (8):102811.
Σ 1 0 and Π 1 0 equivalence structures.Douglas Cenzer, Valentina Harizanov & Jeffrey B. Remmel - 2011 - Annals of Pure and Applied Logic 162 (7):490-503.

Add more citations

References found in this work

A survey of lattices of re substructures.Anil Nerode & Jeffrey Remmel - 1985 - In Anil Nerode & Richard A. Shore (eds.), Recursion theory. Providence, R.I.: American Mathematical Society. pp. 42--323.
Recursion theory.Anil Nerode & Richard A. Shore (eds.) - 1985 - Providence, R.I.: American Mathematical Society.

Add more references