Recursive functions and existentially closed structures

Abstract

The purpose of this paper is to clarify the relationship between various conditions implying essential undecidability: our main result is that there exists a theory $T$ in which all partially recursive functions are representable, yet $T$ does not interpret Robinson's theory $R$. To this end, we borrow tools from model theory--specifically, we investigate model-theoretic properties of the model completion of the empty theory in a language with function symbols. We obtain a certain characterization of $\exists \forall$ theories interpretable in existential theories in the process.

42 pages; to appear in Journal of Mathematical Logic

References in corpus (1)

• Generic expansion and Skolemization in NSOP${}_1$ theories

Cited by in corpus (3)

• Finding the limit of incompleteness I
• Current research on Gödel's incompleteness theorems
• Effective inseparability and some applications in meta-mathematics