Godel-Rosser's Incompleteness Theorems for Non-Recursively Enumerable Theories

Abstract

Godel's First Incompleteness Theorem is generalized to definable theories, which are not necessarily recursively enumerable, by using a couple of syntactic-semantic notions, one is the consistency of a theory with the set of all true ${\Pi }_n$-sentences or equivalently the ${\Sigma }_n$-soundness of the theory, and the other is $n$-consistency the restriction of $\omega$-consistency to the ${\Sigma }_n$-formulas. It is also shown that Rosser's Incompleteness Theorem does not generally hold for definable non-recursively enumerable theories, whence Godel-Rosser's Incompleteness Theorem is optimal in a sense. Though the proof of the incompleteness theorem using the ${\Sigma }_n$-soundness assumption is constructive, it is shown that there is no constructive proof for the incompleteness theorem using the $n$-consistency assumption, for $n>2$.

Journal of Logic and Computation (2016) "Gödel-Rosser's Incompleteness Theorem, generalized and optimized for definable theories"

Cited by in corpus (4)

• Current research on Gödel's incompleteness theorems
• Hierarchical incompleteness results for arithmetically definable extensions of fragments of arithmetic
• Incompleteness for stably consistent formal systems
• Theorems of Tarski's Undefinability and Godel's Second Incompleteness-Computationally