I (think) that I once heard it said that from Tarski's Theorem on the undecidability of truth, Gödel's Second Incompleteness Theorem follows. Is this right?
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
Tarski's theorem is on the unDEFINability of truth, but yes, Goedel's results follow (and in some sense are the same thing): provability (in some particular system of interest) is definable, therefore truth cannot match provability, therefore (supposing the system of interest is consistent, and therefore sound for the relevant sentences) there is a sentence which is true but not provable. This is the first completeness theorem.
What would it mean for a predicate T to actually define truth? Just that T(s) and s are equivalent for each sentence s. Thus, Tarski's undefinability theorem tells us more specifically that, for any definable T, there is some sentence G such that T(G) and G are equivalent to each other's negation. The above is just what happens when we take T to define provability; we thus see more specifically that incompleteness arises from a sentence G equivalent to the negation of its provability, which is therefore (supposing the system of interest is consistent) true but not provable.
One can then argue, in the usual way, that our proof of the first incompleteness theorem, suitably internalized in the system of interest, yields the second incompleteness theorem. [Our argument shows that the consistency of the system of interest entails the non-provability of G. But this conclusion is just what it means for G to be true! Thus, if the system of interest proves its own consistency, it proves G, contra its own consistency.]
-
$\begingroup$ But all that really shows is that some of the ideas used in Tarski's result are also used in a proof of the 2nd incompleteness theorem, which is a pretty modest claim. The question, I take it, is rather whether given the truth of Tarski's theorem, the truth of the 2nd incompleteness theorem follows by some clever argument or other. $\endgroup$ Nov 17, 2012 at 16:49
-
$\begingroup$ I've modified the word of the second paragraph to alleviate this concern. The second incompleteness theorem follows from the simultaneous "external" and "internal" truth of Tarski's theorem (by which I mean, the fact that Tarski's theorem is both true and provable (or, just as well, true inside every model)). $\endgroup$ Nov 17, 2012 at 18:54
-
$\begingroup$ Well, one caveat: One needs that Tarski's result is constructive enough that we have not just "For every T, for every model, there is a G such that...", but in fact "For every T, there is a G such that for every model...". But, basically, were Tarski's result phrased as strongly as its proof actually warranted, it would give us everything. $\endgroup$ Nov 17, 2012 at 19:23
$\begingroup$
$\endgroup$
I got some very exciting new ideas from the reply of Sridhar Ramesh, for which I am very thankful. The question has a negative answer:
(i) Tarski's Undefinability Theorem is not about any (particular) theory; it says that there is no formula $\Psi(x)$ such that for any formula $\varphi$ can $\mathbb{N}\models \varphi \leftrightarrow \Psi(\overline{\varphi})$ hold. While Gödel's Second Incompleteness Theorem is about some theory $T$ for which
(A) $\qquad T\nvdash\textsf{Con}(T)$
holds for some "consistency predicate" $\textsf{Con}(-)$.
(ii) To make more sense of the question, let me formalize Tarski's Undefinability Theorem for a theory $T$ as follows:
(B) $\qquad \neg \exists \Psi\; \forall \varphi\; T\vdash \varphi\leftrightarrow \Psi(\overline{\varphi})$
Now, "some clever argument or other" should prove (B)$\Longrightarrow$(A), right?
The negative answer comes from a result of Dan E. Willard (http://dx.doi.org/10.1016/j.apal.2005.12.010 or http://www.jstor.org/stable/2695030) that for some (very weak and) consistent theory $S$ we can have $S\vdash\textsf{Con}(S)$.
Proof (of our claim): So, the theory $S$ does not satisfy (A). But it satisfies (B) since for an extension of $S$, say $\textsf{PA}$, the Diagonal Lemma holds. Thus, for any $\Psi(x)$ there exists some $\theta$ such that $\textsf{PA}\vdash \theta\leftrightarrow\neg\Psi(\overline{\theta})$ or equivalently $\textsf{PA}\vdash\neg\big[\theta\leftrightarrow\Psi(\overline{\theta})\big]$ (noting the propositional tautology $\neg(p\leftrightarrow q)\equiv p\leftrightarrow\neg q$) which implies that $S\nvdash\theta\leftrightarrow\Psi(\overline{\theta})$. $\texttt{QED}$
Therefore, Tarski's Undefinability Theorem does not imply Gödel's Second Incompleteness Theorem. Even though, as was noted in the replies, there are some vivid connections between the two. For some computational connections I invite consulting (https://arxiv.org/abs/1509.00164).
