Complete, Recursively Enumerable Relations in Arithmetic

&
Mathematical Logic Quarterly 41 (1):65-72 (1995)
  Copy   BIBTEX

Abstract

Using only propositional connectives and the provability predicate of a Σ1-sound theory T containing Peano Arithmetic we define recursively enumerable relations that are complete for specific natural classes of relations, as the class of all r. e. relations, and the class of all strict partial orders. We apply these results to give representations of these classes in T by means of formulas

Categories

Keywords

Reprint years

DOI

10.1002/malq.19950410107

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: 106,894

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

Recursively Enumerable Equivalence Relations Modulo Finite Differences.André Nies - 1994 - Mathematical Logic Quarterly 40 (4):490-518.
Relatively Recursively Enumerable Versus Relatively Σ1 in Models of Peano Arithmetic.Grzegorz Michalski - 1995 - Mathematical Logic Quarterly 41 (4):515-522.
Arithmetical interpretations and Kripke frames of predicate modal logic of provability.Taishi Kurahashi - 2013 - Review of Symbolic Logic 6 (1):1-18.
The Index Set of Injectively Enumerable Classes of Recursively Enumerable Sets in ∑5‐Complete.Stephan Wehner - 1994 - Mathematical Logic Quarterly 40 (1):87-94.
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.
On recursive enumerability with finite repetitions.Stephan Wehner - 1999 - Journal of Symbolic Logic 64 (3):927-945.
The provability logics of recursively enumerable theories extending peano arithmetic at arbitrary theories extending peano arithmetic.Albert Visser - 1984 - Journal of Philosophical Logic 13 (1):97 - 113.
On the complexity of models of arithmetic.Kenneth McAloon - 1982 - Journal of Symbolic Logic 47 (2):403-415.
Satisfaction relations for proper classes: Applications in logic and set theory.Robert A. Van Wesep - 2013 - Journal of Symbolic Logic 78 (2):345-368.

Analytics

Added to PP
2013-12-01

Downloads
33 (#772,233)

6 months
5 (#875,022)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Fixed points and unfounded chains.Claudio Bernardi - 2001 - Annals of Pure and Applied Logic 109 (3):163-178.

Add more citations

References found in this work

Classical recursion theory: the theory of functions and sets of natural numbers.Piergiorgio Odifreddi - 1989 - New York, N.Y., USA: Sole distributors for the USA and Canada, Elsevier Science Pub. Co..

Add more references