Open induction, Tennenbaum phenomena, and complexity theory
Richard W. Kaye · 1993
Abstract This paper collects together several ideas concerning weak systems of arithmetic related to the theory !Open of Shepherdson (1964, 1965) and the theory I E1 of Wilmers (1985), and describes some of the author’s investigations in this area over the last few years. Its two main themes are encapsulated by the following questions: in what way do these theories relate to the computational complexity of natural problems? And: how might one go about proving independence results in this realm? To set the scene and to discuss these questions in more detail we must first give some definitions.