3
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ What are LN and A? $\endgroup$ Jul 17, 2012 at 21:37
  • 1
    $\begingroup$ Perhaps LN means the language of number theory? That is, $+,{\cdot},0,1,{\lt}$? $\endgroup$ Jul 17, 2012 at 21:42

4 Answers 4

5
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Joel: you are right, thanks to your comment, I modified my answer. $\endgroup$
    – Ali Enayat
    Jul 18, 2012 at 1:17
4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ And this works even if $\Sigma$ is empty, since $\Vdash\forall x(x=x)$. $\endgroup$ Jul 17, 2012 at 21:40
  • $\begingroup$ Whoops, that should be a $vdash$. $\endgroup$ Jul 17, 2012 at 21:40
2
$\begingroup$

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?

$\endgroup$
0
0
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ Dave, please register your user. We will then merge your accounts and you will be able to make comments and edit your question. $\endgroup$ Jul 17, 2012 at 23:21
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 17, 2012 at 23:30
  • $\begingroup$ 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. $\endgroup$
    – Dave
    Jul 18, 2012 at 0:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.