Finding the limit of incompleteness I

Abstract

In this paper, we examine the limit of applicability of Gödel's first incompleteness theorem ($G1$ for short). We first define the notion "$G1$ holds for the theory $T$". This paper is motivated by the following question: can we find a theory with a minimal degree of interpretation for which $G1$ holds. To approach this question, we first examine the following question: is there a theory $T$ such that Robinson's $\mathbf{R}$ interprets $T$ but $T$ does not interpret $\mathbf{R}$ (i.e. $T$ is weaker than $\mathbf{R}$ w.r.t. interpretation) and $G1$ holds for $T$? In this paper, we show that there are many such theories based on Jeřábek's work using some model theory. We prove that for each recursively inseparable pair $⟨A,B⟩$, we can construct a r.e. theory $U_{⟨A,B⟩}$ such that $U_{⟨A,B⟩}$ is weaker than $\mathbf{R}$ w.r.t. interpretation and $G1$ holds for $U_{⟨A,B⟩}$. As a corollary, we answer a question from Albert Visser. Moreover, we prove that for any Turing degree $0<\mathbf{d}<0^{\prime }$, there is a theory $T$ with Turing degree $\mathbf{d}$ such that $G1$ holds for $T$ and $T$ is weaker than $\mathbf{R}$ w.r.t. Turing reducibility. As a corollary, based on Shoenfield's work using some recursion theory, we show that there is no theory with a minimal degree of Turing reducibility for which $G1$ holds.

18 pages. Accepted and to appear in Bulletin of Symbolic Logic

References in corpus (2)

• Finding the limit of incompleteness I
• Recursive functions and existentially closed structures

Cited by in corpus (5)

• Finding the limit of incompleteness I
• Current research on Gödel's incompleteness theorems
• Effective inseparability and some applications in meta-mathematics
• On the depth of Gödel's incompleteness theorem
• The limitless First Incompleteness Theorem