Gödel-Rosser's incompleteness theorem, generalized and optimized for definable theories

DOI10.1093/LOGCOM/EXW025zbMATH Open1444.03166arXiv1506.02790OpenAlexW2261973988WikidataQ57533031 ScholiaQ57533031MaRDI QIDQ3133168FDOQ3133168

Authors: Saeed Salehi, Payam Seraji 

Publication date: 13 February 2018

Published in: Journal Of Logic And Computation (Search for Journal in Brave)

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 $P{i}_n$-sentences or equivalently the $Sigm{a}_n$-soundness of the theory, and the other is $n$-consistency the restriction of $omega$-consistency to the $Sigm{a}_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 $Sigm{a}_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$.

Full work available at URL: https://arxiv.org/abs/1506.02790

Recommendations

• Generalizations of Gödel's incompleteness theorems for \(\Sigma_n\)-definable theories of arithmetic
• Gödel's second incompleteness theorem for \(\Sigma_n\)-definable theories
• On constructivity and the Rosser property: a closer look at some Gödelean proofs
• scientific article; zbMATH DE number 1051668
• Finding the limit of incompleteness. I

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30) Gödel numberings and issues of incompleteness (03F40)

Cited In (6)

• Current research on Gödel's incompleteness theorems
• Hierarchical incompleteness results for arithmetically definable extensions of fragments of arithmetic
• Generalizations of Gödel's incompleteness theorems for \(\Sigma_n\)-definable theories of arithmetic
• Gödel's second incompleteness theorem: how it is derived and what it delivers
• Gödel's second incompleteness theorem for \(\Sigma_n\)-definable theories
• Rosser provability and the second incompleteness theorem

This page was built for publication: Gödel-Rosser's incompleteness theorem, generalized and optimized for definable theories

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3133168)