Finding the limit of incompleteness II

Yong Cheng

Published 2021-10-23, updated 2022-10-31Version 2

This work is motivated from finding the limit of the applicability of the first incompleteness theorem ($\sf G1$). A natural question is: can we find a minimal theory for which $\sf G1$ holds? The answer of this question depends on our definition of minimality. We first show that the Turing degree structure of recursively enumerable theories for which $\sf G1$ holds is as complex as the structure of recursively enumerable Turing degrees. Then we examine the interpretation degree structure of recursively enumerable theories weaker than the theory $\mathbf{R}$ with respect to interpretation for which $\sf G1$ holds, and answer all questions about this structure in our published paper. We have two general characterizations which tell us under what conditions there are no minimal recursively enumerable theories with some property with respect to interpretation. As an application, we propose the theory version of recursively inseparable theories, ${\sf tRI}$ theories, and show that there are no minimal ${\sf tRI}$ theories with respect to interpretation: for any ${\sf tRI}$ theory, we can effectively find a strictly weaker ${\sf tRI}$ theory with respect to interpretation.