Robinson's theory R, which axiomatizes the true Sigma_1 sentences, is one of the weakest known essentially undecidable theories. It also has an interesting structural characterization due to Visser, being the strongest locally finite r.e. theory with respect to interpretation. The essential undecidability of R is a consequence of the fact that it can represent all recursive functions, and it is a natural question whether the converse also holds: i.e., does every r.e. theory that represents all (partial) recursive functions interpret R?
The answer is negative, and more generally, R is not interpretable in any consistent theory axiomatized by existential sentences. The explanation comes from model theory. Generalizing the theory of random relational structures (graphs), we will show that for an arbitrary language L (even with functions), the empty L-theory has a model completion EC_L: i.e., EC_L has quantifier elimination, and every L-structure extends to a model of EC_L, so that models of EC_L are exactly the existentially closed L-structures. Furthermore, EC_L is not entirely wild in terms of classification theory: it eliminates exists^infty, and it has the no strict order property, even NSOP_3. (However, unlike the theory of the random graph, it is neither simple nor omega-categorical, and it has the tree property TP_2.) Consequently, various locally finite theories, such as partial orders with arbitrarily long chains, are not interpretable in any consistent existentially axiomatized theory.
EN
