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

DOI10.1093/LOGCOM/EXW025MaRDI QIDQ3133168zbMATH OpenOpenAlexWikidataFDO

Authors Saeed Salehi, Payam Seraji

Publication date 13 February 2018

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

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

Mathematics Subject Classification ID

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

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$.

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

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)