I am not familiar with Robinson's construction as I do not have access to his text or to precise accounts of this, but I have come to understand that the proof predicate of Robinson arithmetic is non-standard e.g. in that it does not fulfill all of the Hilbert-Bernays-Löb derivability conditions. Can I rest assured that Q allows us to infer the thesishood of $Pr[A]$ from the thesishood of $A$, and the thesishood of $A$ from the thesishood of $Pr[A] and the omega-consistency of Q, so that the incompleteness of Q follows as with Gödel from the above plus the Diagonal Lemma?
$\begingroup$
$\endgroup$
2
asked Mar 15, 2016 at 2:51
-
$\begingroup$ The incompleteness of $Q$ is trivial since you can give many concrete examples of true in $\omega$ statements that $Q$ doesn't prove. $\endgroup$– Christian RemlingCommented Mar 15, 2016 at 3:01
-
$\begingroup$ My question concerns the behaviour of Q's provability predicate. $\endgroup$– Frode Alfson BjørdalCommented Mar 15, 2016 at 3:10
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
Robinson arithmetic is $\Sigma^0_1$ complete - every true $\Sigma^0_1$ sentence is provable in Q. If you are asking whether $Q \vdash A$ implies $Q \vdash \text{Pr}(A)$, that completeness results says that the answer is yes, because $\text{Pr}(A)$ is a true $\Sigma^0_1$ sentence.
If I remember correctly, Robinson investigated $Q$ precisely because $Q$ is strong enough for the usual proof of the first incompleteness theorem to go through.
On the other hand, $Q$ is not able to infer much about the $\text{Pr}$ predicate, and the second part of the question above seems to ask about using $Q$ as a metatheory. In particular, I suspect that $Q$ does not satisfy the Hilbert-Bernays conditions that are required for the usual proof of the second incompleteness theorem.
There are proofs that $Q$ does not prove its own consistency, but these use other methods.
A. Bezboruah and John C. Shepherdson, 1976. "Gödel's Second Incompleteness Theorem for Q". Journal of Symbolic Logic v. 41.
Pavel Pudlák, 1985. "Cuts, consistency statements and interpretations". Journal of Symbolic Logic v. 50.
Bezboruah and Shepherdson give a succinct description of the problem:
The paradoxical aspect of the situation is that for reasonably strong systems where the Gödel result is more surprising one can prove the unprovability of Con relatively easily by establishing the Hilbert-Bernays conditions. On the other hand for very weak systems where it is obvious that they are hopelessly inadequate to prove enough elementary number theory to manipulate g.n.'s of sequences with sufficient facility to get anywhere near a consistency proof, one can rely only on ad hoc proofs involving the construction of a model in which Con is false. ... Thus for such a weak system as Raphael Robinson's Q which cannot prove the commutativity of addition, it is apparently unknown whether the usual formulae expressing its consistency are unprovable.
For the last sentence of the quote, the authors cite R.G. Jeroslow, 1971, "Consistency statements in formal theories", Fundamenta Mathematicae v. 72. They cite page 14, but I believe they intended to refer to a remark of Jeroslow on p. 24.
answered Mar 17, 2016 at 13:42
-
$\begingroup$ Thanks! If "Robinson investigated Q precisely because Q is strong enough for the usual proof of the first incompleteness theorem to go through" does it not mean that we can infer "the thesishood of A from the thesishood of $Pr[A] and the omega-consistency of Q"? $\endgroup$ Commented Mar 17, 2016 at 15:45
-
$\begingroup$ It would seem so. As Q is also $\Sigma^0_0$-complete, all of $\vdash\lnot 0Prov[G]$, $\vdash\lnot 1Prov[G]$, $\vdash\lnot 2Prov[G]$ etc. hold. So $\nvdash\exists x(xProv[G]$ and thus $\nvdash\lnot G $ follow by omega consistencey. $\endgroup$ Commented Mar 17, 2016 at 16:59