“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 14498
School of Mathematics
  Title:   Godel-Rosser's incompleteness theorem, generalized and optimized for definable theories
  Author(s):  S. Salehi (Joint with P. Seraji)
  Status:   Published
  Journal: J. Logic Comput.
  Vol.:  27
  Year:  2017
  Pages:   1391-1397
  Supported by:  IPM
Gödel–Rosser's Incompleteness Theorem is generalized by showing Πn+1-incompleteness of any Σn+1-definable extension of Peano Arithmetic which is either Σn-sound or n-consistent. The optimality of this result is proved by presenting a complete, Σn+1-definable, Σn−1-sound, and (n−1)-consistent theory for any n>0⁠. Though the proof of the incompleteness theorem for Σn+1-definable theories using the Σn-soundness assumption is constructive, it is shown that there is no constructive proof for the Incompleteness Theorem for Σn+1-definable theories using the n-consistency assumption, when n>2⁠.

Download TeX format
back to top
scroll left or right