Statement of consistency in Godel's second incompleteness theorem - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T19:17:33Z http://mathoverflow.net/feeds/question/102490 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/102490/statement-of-consistency-in-godels-second-incompleteness-theorem Statement of consistency in Godel's second incompleteness theorem Dave 2012-07-17T21:25:07Z 2012-07-18T01:16:34Z <p>This is a question from Stefan Bilaniuk's very good free online book <a href="http://onlinebooks.library.upenn.edu/webbin/book/lookupid?key=olbp12123" rel="nofollow">A Problem Course in Mathematical Logic</a>:</p> <p>Problem 18.6. Suppose $\Sigma$ is a recursive set of sentences of LN. Find a sentence of LN, which we'll denote by $Con(\Sigma)$, such that $\Sigma$ is consistent if and only if $A \vdash Con(\Sigma)$.</p> <p>By Godel's second incompleteness theorem isn't this impossible?</p> http://mathoverflow.net/questions/102490/statement-of-consistency-in-godels-second-incompleteness-theorem/102493#102493 Answer by Joel David Hamkins for Statement of consistency in Godel's second incompleteness theorem Joel David Hamkins 2012-07-17T21:35:25Z 2012-07-17T21:54:13Z <p>First, notice that one can have a somewhat cheating solution, like this: You didn't say what $A$ was, but let me assume that it is consistent. There are two cases. If $\Sigma$ happens to be consistent, then let Con(Sigma) be any statement that $A$ proves, such as a tautology. If $\Sigma$ happens to be inconsistent, then let Con(Sigma) be any statement that $A$ does not prove, such as the negation of a tautology. It then follows that $\Sigma$ is consistent if and only if $A\vdash$ Con(Sigma), as desired.</p> <p>Second, notice that in general there cannot be a non-cheating solution (Edit: provided $A$ is particularly simple: computably axiomatizable), since the consistency of a theory is a $\Pi^0_1$ assertion, and the provability of a sentence in an elementary theory is $\Sigma^0_1$, and there will be no way to surmount this. For example, if there is a sentence $\sigma$ such that PA proves ("PA is consistent" $\iff$ PA$\vdash\sigma$), then since PA really is consistent, it will follow that PA$\vdash\sigma$ and hence that PA proves that PA$\vdash\sigma$, since it proves all true existentials. Thus, PA will prove its own consistency, in contradiction to the incompleteness theorem. </p> http://mathoverflow.net/questions/102490/statement-of-consistency-in-godels-second-incompleteness-theorem/102494#102494 Answer by Noah S for Statement of consistency in Godel's second incompleteness theorem Noah S 2012-07-17T21:49:45Z 2012-07-17T21:49:45Z <p>What is $A$? When I read this question, I thought that $A$ might mean the theory of the natural numbers ("true arithmetic"); in this case, there is even a non-cheating solution. We can formulate, in the language of arithmetic, a formula which asserts that $\Sigma$ is consistent; this is the bulk of the proof of the incompleteness theorem. But this relies crucially on having a way to refer to $\Sigma$ inside the language of arithmetic; this is where the assumption that $\Sigma$ is recursive comes in. By contrast, true arithmetic is <em>not</em> recursive (indeed, not definable, by Tarski's Undefinability Theorem), so "$Con(A)$" can't be expressed. This means that there is no sense in which $A$ proves its own consistency.</p> <p>Is this along the lines of what you were asking?</p> http://mathoverflow.net/questions/102490/statement-of-consistency-in-godels-second-incompleteness-theorem/102501#102501 Answer by Dave for Statement of consistency in Godel's second incompleteness theorem Dave 2012-07-17T23:17:24Z 2012-07-17T23:17:24Z <p>Sorry folks - yes LN means the language of number theory and A is true arithmetic. Noah that is definitely along the lines I am looking for, but I am still confused - why am I wrong here?:</p> <p>if A|- Con(Sigma) </p> <p>and Sigma|- A </p> <p>and if A and Sigma are consistent</p> <p>then by a previous corollary:</p> <p>Corollary 17.17. Functions and relations which representable in Th(A) are also representable in Th(Sigma), for any consistent set of sentences such that Sigma |- A.</p> <p>so Sigma |-Con(Sigma)</p> <p>And apologies, I will immediately learn the math syntax, I'm just eager for an answer here.</p> http://mathoverflow.net/questions/102490/statement-of-consistency-in-godels-second-incompleteness-theorem/102502#102502 Answer by Ali Enayat for Statement of consistency in Godel's second incompleteness theorem Ali Enayat 2012-07-17T23:39:15Z 2012-07-18T01:16:34Z <p><strong>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 <a href="http://phil.gu.se/logic/books/Bilaniuk%3AA_problem_course_in_Mathematical_Logic.pdf" rel="nofollow">text</a> . Note that by Th($\mathcal{A}$) Belaniuk refers to the deductive closure of $\mathcal{A}$ (which is a rather unusual notation).</strong></p> <p><strong>0.</strong> 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".</p> <p><strong>1.</strong> 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$).</p> <p><strong>2.</strong> 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 <strong>1</strong>: <em>Next show that $\Sigma$ is consistent iff $\mathcal{A}\nvdash \lnot Con(\Sigma)$</em>.</p>