Skip to main content
2 of 2
added 120 characters in body
Ali Enayat
  • 17.7k
  • 2
  • 63
  • 105

I think there is a typo in Problem 18.6 of Belaniuk's text, because the $\mathcal{A}$ in the problem refers to a (rather weak) fragment of $PA$ (but strong enough to numeralwise represent all recursive functions). His $\mathcal{A}$ is defined on p.117 of his text . Note that by Th($\mathcal{A}$) Belaniuk refers to the deductive closure of $\mathcal{A}$ (which is a rather unusual notation).

0. As stated, the problem has a "cheating" solution as provided by Joel. While this solution does the job, it is most likely not what the author had in mind, since he (a) stipulates $\Sigma$ to be r.e., and (b) wishes to prove the incompleteness theorem in the same section with the "honest" arithmetical formulation of the statement "$\Sigma$ is consistent".

1. I suspect (along with Noah) that the author's intended problem is obtained by replacing $\mathcal{A}$ by the true theory of arithmetic (often denoted $TA$).

2. Another variation of the problem (which takes advantage of the fact that $\mathcal{A}$ is "smart enough" to prove all true existential sentences of arithmetic) is to add a second part to the version in 1: Next show that $\Sigma $ is consistent iff $\mathcal{A}\nvdash \lnot Con(\Sigma) $.

Ali Enayat
  • 17.7k
  • 2
  • 63
  • 105