Premium
Complete, Recursively Enumerable Relations in Arithmetic
Author(s) -
D'Agostino Giovanna,
Magnago Mario
Publication year - 1995
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.19950410107
Subject(s) - peano axioms , recursively enumerable language , mathematics , class (philosophy) , arithmetic , discrete mathematics , recursively enumerable set , predicate (mathematical logic) , algebra over a field , pure mathematics , computer science , artificial intelligence , programming language
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.