Sign up ×

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?

share|cite|improve this question
What are LN and A? – Trevor Wilson Jul 17 '12 at 21:37
Perhaps LN means the language of number theory? That is, $+,{\cdot},0,1,{\lt}$? – Joel David Hamkins Jul 17 '12 at 21:42

4 Answers 4

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

share|cite|improve this answer
Joel: you are right, thanks to your comment, I modified my answer. – Ali Enayat Jul 18 '12 at 1:17

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.

share|cite|improve this answer
And this works even if $\Sigma$ is empty, since $\Vdash\forall x(x=x)$. – Noah Schweber Jul 17 '12 at 21:40
Whoops, that should be a $vdash$. – Noah Schweber Jul 17 '12 at 21:40

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?

share|cite|improve this answer

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.

share|cite|improve this answer
Dave, please register your user. We will then merge your accounts and you will be able to make comments and edit your question. – François G. Dorais Jul 17 '12 at 23:21
Dave, if $\Sigma$ is recursive and $A$ is the full theory of true arithmetic, then we will not have $\Sigma\vdash A$. Indeed, if $A$ is the theory of true arithmetic, then $A\vdash\sigma$ is just another way of saying that $\sigma$ is true. – Joel David Hamkins Jul 17 '12 at 23:30
Yet another apology Noah! I was unaware that A wasn't what you meant by true arithmetic. Ali has set me right. Thank you everyone, this one was ruining my week. – Dave Jul 18 '12 at 0:18

Your Answer


