An Interpretation of Robinson Arithmetic in its Grzegorczyk's Weaker Variant

Issue title: Topics in Logic, Philosophy and Foundations of Mathematics and Computer Science. In Recognition of Professor Andrzej Grzegorczyk

Article type: Research Article

Authors: Švejdar, Vítězslav

Affiliations: Charles University, Praha, Czech Republic. E-mail: vitezslav.svejdar@cuni.cz

Abstract: Q^- is a weaker variant of Robinson arithmetic Q in which addition and multiplication are partial functions, i.e. ternary relations that are graphs of possibly non-total functions. We show that Q is interpretable in Q^-. This gives an alternative answer to a question of A. Grzegorczyk whether Q^- is essentially undecidable.

Journal: Fundamenta Informaticae, vol. 81, no. 1-3, pp. 347-354, 2007