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

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 93,642

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.
The Index Set of Injectively Enumerable Classes of Recursively Enumerable Sets in ∑5‐Complete.Stephan Wehner - 1994 - Mathematical Logic Quarterly 40 (1):87-94.
Arithmetical interpretations and Kripke frames of predicate modal logic of provability.Taishi Kurahashi - 2013 - Review of Symbolic Logic 6 (1):1-18.
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.
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.

Analytics

Added to PP
2013-12-01

Downloads
5 (#1,562,871)

6 months
26 (#116,274)

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..
Classical Recursion Theory.Peter G. Hinman - 2001 - Bulletin of Symbolic Logic 7 (1):71-73.
The Unprovability of Consistency. An Essay in Modal Logic.C. Smoryński - 1979 - Journal of Symbolic Logic 46 (4):871-873.

Add more references