Statement of consistency in Godel's second incompleteness theorem - MathOverflow

Statement of consistency in Godel's second incompleteness theorem

2012-07-17T21:25:07Z

This is a question from Stefan Bilaniuk's very good free online book A Problem Course in Mathematical Logic:

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

By Godel's second incompleteness theorem isn't this impossible?

Answer by Joel David Hamkins for Statement of consistency in Godel's second incompleteness theorem

2012-07-17T21:35:25Z

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.

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.

Answer by Noah S for Statement of consistency in Godel's second incompleteness theorem

2012-07-17T21:49:45Z

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

Is this along the lines of what you were asking?

Answer by Dave for Statement of consistency in Godel's second incompleteness theorem

2012-07-17T23:17:24Z

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?:

if A|- Con(Sigma)

and Sigma|- A

and if A and Sigma are consistent

then by a previous corollary:

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.

so Sigma |-Con(Sigma)

And apologies, I will immediately learn the math syntax, I'm just eager for an answer here.

Answer by Ali Enayat for Statement of consistency in Godel's second incompleteness theorem

2012-07-17T23:39:15Z

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